Haskell transforming fuction to use foldr or foldl

Question

I am struggling understanding foldr and foldl, what are main benefits of using either, foldl is supposed to be tail recursive, but then what is foldr, normally recursive?

I have simple function which takes list of int and returns sum of squares between first and last element.

sumSquare :: [Int] -> Int
sumSquare xs = if length xs == 2 then  sum $  map (^2) [head xs..last xs] else error "bad input"

What I want to do is implement this function using foldr or foldl, I've looked through few examples, but sadly got nowhere with it.

If someone could demonstrate how to transform this function to one using either foldr or foldl and explain process I would be grateful

Answer 1

@Luis Casillas gave good advice, but for your sumSquares:

If you look at the type foldr :: (a -> b -> b) -> b -> [a] -> b you see that it takes a function (that takes an element, the accumulator, and returns a new accumulator), the initial accumulator, and a list and returns the resulting accumulator. For foldl :: (b -> a -> b) -> b -> [a] -> b, the order of the arguments is reversed.

So sumSquares can be written (I took the liberty of changing it slightly to remove the length check)

sumSquare' a b = foldl (\x y -> x + (y^2)) 0 [a..b]

sumSquare'' a b = foldr (\y x -> x + (y^2)) 0 [a..b]

regarding how they are recursive, let's look at how they are defined: (for more on this, there are good explanations at http://en.wikibooks.org/wiki/Haskell/List_processing and https://wiki.haskell.org/Foldr_Foldl_Foldl')

foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f acc []     =  acc
foldl f acc (x:xs) =  foldl f (f acc x) xs

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f acc []     = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

So, the evaluation of sumSquare' 1 3 will be (with f denoting the lambda)

foldl f 0 [1,2,3]
foldl f (f 0 1) [2,3]
foldl f (f (f 0 1) 2) [3]
foldl f (f (f (f 0 1) 2 ) 3) []
f (f (f 0 1) 2 ) 3

and for sumSquare'' 1 3:

foldr f 0 [1,2,3]
f 1 (foldr f 0 [2,3])
f 1 (f 2 (foldr f 0 [3]))
f 1 (f 2 (f 3 (foldr f 0 []))
f 1 (f 2 (f 3 0))

Answer 2

A few imperfect rules of thumb:

1. Don't use foldl.
2. If you're constructing a result that can be constructed lazily, use foldr.
3. If your're constructing a result cannot be constructed lazily, use foldl' from the Data.List module.
4. Try not to use either directly. Think of the folds as relatively low-level functions that you use to build reusable functions that are easier to understand.

Example of point #4: which is easier to understand? Example 1:

example1 = foldr step [] [0..]
    where step n ns = if even n then n:ns else ns

Example 2:

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr step []
    where step a as = if p a then a:as else as

example2 = filter even [0..]

The second one, of course! You want to solve problems by splitting them into smaller problems, and splitting those into smaller problems. This process is easiest to understand when folds occur at the bottom of the splitting.

Points #2 and #3: think of the difference between sum :: Num a => [a] -> a and filter :: (a -> Bool) -> [a] -> [a]. The result of sum is a number, and the result of filter is a list. In Haskell lists can be produced and consumed lazily, but the standard numeric types cannot.

If the result you're constructing is a list, you want to use foldr because what will actually happen is that the result will be constructed lazily, as the list is demanded. This is for example true of the filter definition above; the list produced by filter will be constructed lazily as its consumer demands. Example (with step as in the definition above):

head (filter even [0..])
    = head (foldr step [] [0..])
    = head (step 0 (foldr step [] [1..]))
    = head (if even 0 then 0 : foldr step [] [1..] else foldr step [] [1..])
    = head (if True then 0 : foldr step [] [1..] else foldr step [] [1..])
    = head (0 : foldr step [] [1..])
    = 0

Laziness here means that the evaluation of the foldr stops as soon as enough of its result is produced to figure out the result of head.

But if you're doing sum, most likely you want want to use foldl':

import Data.List (foldl')

sum :: Num a => [a] -> a
sum = foldl' (+) 0

Since there is no way to consume a number lazily, you want to exploit the tail recursion of foldl' instead. Example:

sum [1..3] * 2
    = foldl' (+) 0 [1..3] * 2
    = foldl' (+) 1 [2..3] * 2
    = foldl' (+) 3 [3..3] * 2
    = foldl' (+) 6 [] * 2
    = 6 * 2
    = 12

But on the flip side, foldl' cannot exploit laziness like foldr can. foldl' must traverse the whole list all at once.

---

Answer to the comment: well, let's try this again. First point I'd make is that what you're trying to do is a bad idea. You don't want to do "3-4 things" in one fold. It produces code that's hard to read and hard to modify.

But there is a way to turn it into a good example. Let's write your function this way:

sumSquares (lo, hi) = sum $ map (^2) [lo..hi]

Note that I changed the argument to a pair. Your original expects the list to have length of exactly two, which really says that you shouldn't be using a list, but a pair (or just two arguments).

So how to turn this into a set of folds? First step: let's write sum and map in terms of folds:

sum = foldr (+) 0
map f = foldr (\a bs -> f a : bs) []

So now we can manually inline these into the definition:

sumSquares (lo, hi) = foldr (+) 0 $ foldr (\a bs -> a^2 : bs) [] [lo..hi]

Now, here's a very useful fact: if foldr consumes a list produced by another foldr, it's often possible to fuse the two folds into one. In this case they fuse to this:

sumSquares (lo, hi) = foldr (\a bs -> a^2 + bs) 0 [lo..hi]

So for example:

sumSquares (1, 3)
    = foldr (\a bs -> a^2 + bs) 0 [1..3]
    = 1^2 + foldr (\a bs -> a^2 + bs) 0 [2..3]
    = 1^2 + 2^2 + foldr (\a bs -> a^2 + bs) 0 [3..3]
    = 1^2 + 2^2 + + 3^2 + foldr (\a bs -> a^2 + bs) 0 []
    = 1^2 + 2^2 + + 3^2 + 0
    = 1 + 4 + 9 + 0
    = 14

As a side point, you use head and last in your code, note that these can also be written as folds:

safeHead, safeLast :: [a] -> Maybe a

safeHead = foldr step Nothing
    where step a _ = Just a

safeLast = foldr step Nothing
    where step a Nothing = Just a
          step _ justA = justA

So to solve these problems in the messy, all-in-one function way, you want to write out the clean, multi-function solution, translate the individual pieces into folds, and then figure out if and how you can fuse those folds together.

But it's not really worth it as a beginner's exercise. First of all, GHC has list fusion optimizations built in already. So the compiler knows already how to fuse this code and turn it into a nice, tight loop:

foldr (+) 0 $ map (^2) [lo..hi]