Can you explain the differences between ’foldl’, ’foldr’, and ’foldl1’ functions in Haskell?

‘foldl‘, ‘foldr‘, and ‘foldl1‘ are all higher-order functions in Haskell used for reducing lists. They are defined in the ‘Data.List‘ module as a part of the standard library.

1. ‘foldl‘ (left fold): It takes a binary function, an initial accumulator value, and a list. It reduces the list by applying the function to the current accumulator and an element in the list, starting from the left (head of the list) until the end (tail of the list). This function is tail recursive and can cause a stack overflow for long lists.

The type signature of ‘foldl‘ is:

foldl :: (b -> a -> b) -> b -> [a] -> b

Here is an example of calculating the sum of a list of numbers using ‘foldl‘:

sumList :: [Int] -> Int
sumList xs = foldl (acc x -> acc + x) 0 xs

2. ‘foldr‘ (right fold): It takes a binary function, an initial accumulator value, and a list. It reduces the list by applying the function to an element in the list and the current accumulator, starting from the right end (tail of the list) until the beginning (head of the list). It is not tail recursive but is lazy and can work with infinite lists.

The type signature of ‘foldr‘ is:

foldr :: (a -> b -> b) -> b -> [a] -> b

Here is an example of calculating the product of a list of numbers using ‘foldr‘:

productList :: [Int] -> Int
productList xs = foldr (*) 1 xs

3. ‘foldl1‘: It is a variant of ‘foldl‘ that assumes the list is non-empty and uses the first element of the list as the initial accumulator value. It can produce an error if called on an empty list.

The type signature of ‘foldl1‘ is:

foldl1 :: (a -> a -> a) -> [a] -> a

Here is an example of calculating the minimum element of a list using ‘foldl1‘:

minList :: [Int] -> Int
minList xs = foldl1 min xs

In summary, the main differences between ‘foldl‘, ‘foldr‘, and ‘foldl1‘ are:

- ‘foldl‘: Applies the function from left to right and is tail recursive.

- ‘foldr‘: Applies the function from right to left and is lazy.

- ‘foldl1‘: A variant of ‘foldl‘ that operates on non-empty lists with the first element as the initial accumulator value.

Here’s a visual representation of the folding process using LaTeX using the function ‘f‘ and the list ‘[1, 2, 3]‘. The initial accumulator values (if applicable) are denoted as ‘z‘ and the final results as ‘r‘.

- ‘foldl‘:

$$\underbrace{f(\cdots (f(f(z, 1), 2), 3)}\_{\text{foldl}} \to r$$

- ‘foldr‘:

$$\underbrace{f(1, f(2, \cdots (f(3, z) )))}\_{\text{foldr}} \to r$$

- ‘foldl1‘ (using the first element, ‘1‘, as the initial accumulator value):

$$\underbrace{f(\cdots (f(f(1, 2), 3))}\_{\text{foldl1}} \to r$$