Working with Lists

Reversing a list using a foldl can be done by prepending each new element to the front of the new list. Since foldl is left-associative, we’ll start with the first element of our old list. Adding each new element to the beginning of the reversed list means we’ll finish by adding the final element of the original list to the beginning of the new list. Following the pattern from the earlier hint, we could a solution like this:

reverseLeft = foldl insertElem []
  where insertElem reversed a = a : reversed

Alternatively, we can use the flip function to make this a bit more compact. Remember that flip just flips the arguments of a function:

flip f b a = f a b

Our foldl version of insertElem is just a flipped version of (:), so we can rewrite our reverse function as:

reverseLeft = foldl (flip (:)) []

We can also reverse a list using foldr but this will be less efficient. Since foldr is right associative, we start adding elements from the end of the input list. That means each new element we process needs to be added to the end of our accumulated list:

reverseRight = foldr insertElem []
  where
    insertElem a reversed = reversed <> [a]

This is less efficient because we have to walk through the entire reversed list for every item we add, so that we can insert new items at the end.

As you might expect, it’s possible to implement zipWith with manual recursion, foldl, or using a list comprehension. In fact, there are several different options, all with their own tradeoffs.

Let’s start by looking at the manual recursive definition. We’ll use pattern matching to decide whether we have enough data to create a new value. Naively, we could check if either list is empty, and otherwise return a value:

exampleZipWith f [] bs = []
exampleZipWith f as [] = []
exampleZipWith f (a:as) (b:bs) = f a b : exampleZipWith f as bs

Although it works, this approach is a bit more verbose than necessary. If either list is empty, or if both of them are, then we’re returning an empty list. We’re only applying f when both lists are non-empty. If we put that pattern first, then we can use a wildcard pattern for all other cases:

exampleZipWith f (a:as) (b:bs) = f a b : exampleZipWith f as bs
exampleZipWith _f _as _bs = []

Alternatively, you could use a case expression to implement this function. The logic is the same, but we’ll use a single implementation of our function:

exampleZipWithCase f a b =
  case (a,b) of
    (a':as, b':bs) -> f a' b' : exampleZipWith f as bs
    _ -> []

Another option for implementing our function with manual recursion would be to use a guard. Naively you might want to use null and head to implement this function using a guard:

exampleGuard f as bs
  | null as || null bs = []
  | otherwise = f (head as) (head bs) : exampleGuard f (tail as) (tail bs)

Although technically safe and correct, since we’re testing for empty lists before using the partial head function, it’s common practice to avoid partial functions like head in general, even when we know them to be safe. In that case, we can use pattern guards to pattern match inside of a guard clause:

examplePatternGuard f as bs
  | (a:as') <- as, (b:bs') <- bs = f a b : examplePatternGuard f as' bs'
  | otherwise = []

You’ll notice that the syntax here is the same as the syntax when working with a list comprehension. We use the left arrow (<-) to pattern match on a value. If any of the patterns fail , then the guard clause fails and we move onto the next one.

Now that you’ve seen how to implement zipWith using manual recursion, can you do it using foldl or a list comprehension? Try it yourself, or click below to see the next part of the solution.

Now that you’ve implemented a manually recursive version of zipWith, let’s move our attention to a version that uses foldl. If we’re willing to cheat a little bit, our implementation is pretty straightforward:

zipWithFoldl f as bs = reverse $ foldl applyFunction [] zipped
  where
    zipped = zip as bs
    applyFunction accumulator (a,b) = f a b : accumulator

In this solution we’re using zip to handle combining each pair of elements in the two lists. Afterwards, we take one trip through the list with foldl and apply f to each pair of arguments. You’ll notice that we’re prepending each new value to the beginning of our accumulator, and then reversing the whole list at the end. Doing a single call to reverse at the end of our fold lets us avoid having to update the entire list every time we add a new element. Alternatively, we could use foldr and save ourselves the call to reverse:

zipWithFoldr f as bs = foldr applyFunction [] zipped
  where
    zipped = zip as bs
    applyFunction (a,b) accumulator = f a b : accumulator

Since the exercise asked us to solve this with foldl let’s stick with that. If we don’t want to cheat by using zip, we can still solve the problem with foldl, but we need to do a bit more work to keep track of our two lists.

Instead of zipping both lists together, then applying our function, we can do both in a single step:

zipWithFoldl' f as bs =
  reverse $ fst results
  where
    results = foldl applyFunction ([], as) bs
    applyFunction (zipped, []) _ = (zipped, [])
    applyFunction (zipped, x:xs) val = (f x val : zipped, xs)

This function isn’t too different from our original version. We’re still starting with an empty list in our accumulator, and we’re still calling f for each item in our fold. What’s different is that our accumulator value is now keeping track of both the new list that we’re building up, and also the second list that we’re slowly breaking down. If as is shorter than bs we’ll start ignoring any new values in the fold and return the list that we were able to build up as long as we had values in each list.

Once we’re finished with the fold, we’re left with a tuple that contains both the new list, as well as any remainder of as that we weren’t able to process. We discard the leftover as and return the reversed list just like we did with our earlier foldl implementation.

Now that you’ve seen how to implement zipWith using both manual recursion and foldl, you can try to implement it with a list comprehension yourself, or expand the solution below.

Now that you’ve written zipWith using both foldl and with manual recursion, the last task in this exercise is to build a version that uses list comprehensions. This is the most challenging of the three parts of this problem, because we’re working against the language. This part of the example shows that just because you can use a feature to do something doesn’t mean it’s the best way to do it.

The problem with using a list comprehension to implement zipWith is, as you may recall from the chapter, a list comprehension returns a value for each pairing of our two lists. That means the naive approach won’t work. Let’s try it and see why:

exampleZipWithComprehensionBad f as bs = [f a b | a <- as, b <- bs]

Let’s load this up in ghci and compare the behavior of this function with the real zipWith:

λ zipWith (,) [1,2] [3,4]
[(1,3),(2,4)]

λ exampleZipWithComprehensionBad (,) [1,2] [3,4]
[(1,3),(1,4),(2,3),(2,4)]

As you can see, the real definition of zipWith pairs the first element of the first list with the first element of the second list, and so on, until it reaches the end of one of the lists. Our list comprehension version pairs the first element of the first list with each element of the second list, and so on, until it’s gone through every pairing. That’s a significantly different behavior.

So, how can work work around this? Just like with our earlier foldl example, the easiest option is to cheat by using zip:

exampleZipWithComprehension f as bs = [f a b | (a,b) <- zip as bs]

Not only does using zip mean that we don’t need to worry about one list being longer than the other, it also combines our two lists so that we don’t need to worry about the fact that list comprehensions don’t combine elements the way we want for zipWith.

If we don’t want to cheat by using zip, then we need to be a bit creative in how we approach the problem. Using two lists won’t work, but how can we get a single list out of our two lists if we’re not combining them with zip? Let’s think again about the nature of our problem: We want to combine the first element of as with the first element of bs, then we want to combine the second element of as with the second element of bs and so on until we reach the end of one of our two lists. Although we have two lists, at each step we’re combining the values at the same index. All we need to do is to step through the list of indexes.

exampleZipWithComprehensionIndex f as bs =
  [f (as !! idx) (bs !! idx) | idx <- [0 .. len - 1]]
  where
    len = min (length as) (length bs)

As you can see, moving to an index based approach to using a list comprehension lets get an implementation that’s fairly easy to read, and doesn’t require that we use zip.

Thinking about how to implement something like zipWith using list comprehensions is a great way to stretch your mind and think about the different ways you can apply the features of Haskell creatively, but in practice this isn’t the way we’d normally implement something like this. Although the (!!) operator should be safe in this example since we’re checking the length of our inputs, it’s still an unsafe operation. Indexing into the lists repeatedly is also much less efficient than even using a foldl and reversing the output. Indexing into a list requires that we traverse the whole list up to the element we want, and so repeated indexing ends up being more work than walking through the list twice (once for the foldl and again for the reverse).

We can write concatMap easily using either foldl or foldr. Let’s take a look at a foldr based version first:

concatMapFoldr f = foldr (\x acc -> f x <> acc) []

Like the other examples where we’ve used foldr, this version of concatMap is lazy and well-behaved when we need to deal with infinite lists. The most obvious example of this is directly passing an infinite list to concatMapFoldr:

λ take 10 $ concatMapFoldr (\x -> [x,x]) [1..]
[1,1,2,2,3,3,4,4,5,5]

We can also handle cases where the input is a finite list, but our function outputs infinite lists that we we want to concatenate together. You’ll notice in this example we’re using a new function: repeat. This function takes a value and generates a list of that value repeated indefinitely:

-- When we return an infinite list for each finite input element
λ take 10 $ concatMapFoldr (\x -> repeat x) [1,2,3]
[1,1,1,1,1,1,1,1,1,1]

As you might expect, we can also handle both cases at the same time. Even with an infinitely long input, and a function that generates infinitely long lists from each input, we’re still able to get a finite result:

-- When we return an infinite list for each of infinite inputs
λ take 10 $ concatMapFoldr (\x -> repeat x) [1..]
[1,1,1,1,1,1,1,1,1,1]

We can implement a foldl based version of concatMap just as easily as our foldr version, we just need to flip around the order of some of our operations:

concatMapFoldl f = foldl (\acc x -> acc <> f x) []

As you might expect, this version of concatMap doesn’t do well with infinite lists. Whether you pass in an finitely list, generate one with the function you pass in, or both, concatMapFoldl will hang and ever complete.

So, Which One Is Better?

In most cases, concatMapFoldr is the version of this function that we’d want. If we look at the behavior of the concatMap defined for us in Prelude you’ll notice it’s behavior with infinite lists matches our foldr based implementation:

λ take 10 $ concatMap repeat [1..]
[1,1,1,1,1,1,1,1,1,1]

It turns out that these two examples should always behave exactly the same. In the first example, we first use map f to transform every element of our list, and then fold over the resulting values. In the second example, each time we’d apply our fold function we first transform the element we’re about to fold, again using f. Since Haskell is pure lazy language, it turns out that these should always return the same value.

To help make things a little bit more clear, let’s walk through a short example. Imagine that we wanted to double a list of numbers, and then add them up.

Let’s start by giving names to our two different possible functions:

composeMapFoldr f g = foldr g 0 . map f
composeFandGFoldr f g = foldr (g . f) 0

If we call them in ghci we can see that with some casual testing they do in fact seem to return the same thing:

λ double a = a * 2
λ add a b = a + b

λ composeMapFoldr double add [1..10]
110

λ composeFandGFoldr double add [1..10]
110

Let’s use a smaller list and step through each of these and see how they work. We’ll start with composeMapFoldr:

composeMapFoldr double add = foldr add 0 . map double

-- If we apply [1,2,3] we'll get
composeMapFoldr double add [1,2,3] = foldr add 0 (map double [1,2,3])

-- Next, let's apply `map double` manually
composeMapFoldr double add [1,2,3] = foldr add 0 [double 1, double 2, double 3]

-- Now we can apply foldr. Refer to the chapter for a definition of foldr
foldr add 0 [double 1, double 2, double 3] =
  if null [double 1, double 2, double 3] -- false
  then 0
  else add (double 1) $ foldr add 0 [double 2, double 3]

-- Expanding another step
foldr add 0 [double 1, double 2, double 3] =
  add (double 1) $
    if null [double 2, double 3] -- false
    then 0
    else add (double 2) $ foldr add 0 [double 3]

-- Expanding one more time
foldr add 0 [double 1, double 2, double 3] =
  add (double 1) $
    add (double 2) $
     add (double 3) $
       if null [] then 0 else ...

-- Simplifying
foldr add 0 [double 1, double 2, double 3] =
  add (double 1) (add (double 2) (add (double 3) 0))

= 12

Next, let’s do the same exercise with composeFandGFoldr:

composeFandGFoldr double add [1,2,3] = foldr (add . double) 0 [1,2,3]

-- No need to apply map first, let's go to the first step of foldr
foldr (add . double) 0 [1,2,3] =
  if null [1,2,3]
  then 0
  else add (double 1) $ foldr (add . double) 0 [2,3]

-- Expanding another step
foldr (add . double) 0 [1,2,3] =
  add (double 1) $
    add (double 2) $ foldr (add . double) 0 [3]

-- Expanding one more time
foldr (add . double) 0 [1,2,3] =
  add (double 1) $
    add (double 2) $
      add (double 3) $
        if null [] then 0 else ...

-- Simplifying
foldr add 0 [double 1, double 2, double 3] =
  add (double 1) (add (double 2) (add (double 3) 0))

= 12

As you can see, these two functions end up behaving exactly the same.

Unfortunately, the story with foldl turns out to be a little bit more complicated. In theory, thanks to laziness and purity, we ought to be able to get the same easy substitution with foldl, but the the implementation details mean we have to work a bit harder. Let’s start by recreating our two original functions, this time using foldl

double a = a * 2
add a b = a + b

composeMapFoldl f g = foldl g 0 . map f
composeFandGFoldl f g = foldl (g . f) 0

Like before, let’s load these up in ghci and see what happens:

λ composeMapFoldl double add [1..10]
110

λ composeFandGFoldl double add [1..10]
2036

That last result is certainly surprising! Let’s try to expand composeFandGFoldl manually and see if we can spot the problem.

composeFandGFoldl double add [1,2,3] = foldl (g . f) 0

-- This time we start by doubling our carry value, then adding
foldl (add . double) 0 [1,2,3] =
  if null [1,2,3]
  then 0
  else foldl (add (double 0) 1) [2,3]

-- Simplifying our recursive call to foldl
foldl (add . double) 0 [1,2,3] =
  if null [1,2,3]
  then 0
  else foldl 1 [2,3]

-- Expanding another step
foldl (add . double) 0 [1,2,3] =
  if null [2,3]
  then 1
  else foldl (add (double 1) 2) [3]

-- Expanding again
foldl (add . double) 0 [1,2,3] =
  if null [3]
  then 4
  else foldl (add (double 3) 4) []

-- Expanding one last time
foldl (add . double) 0 [1,2,3] =
  if null []
  then (add (double 3) 4)
  else ...

-- Simplifying
foldl (add . double) 0 [1,2,3] =
  if null []
  then 11
  else ...

= 11

As you walk through this code, you can see how the behavior of foldl and foldr differs. With foldl we’re starting with our accumulator value, and doubling it each time before we add the next element in the list.

What About Infinite Lists?

Hopefully by now you are convinced that our two foldr examples behave the same way for some finite length list, but what about cases where the list we’re mapping and folding over is infinite? You’ve already seen an example in the chapter of how foldl and foldr behave differently when working with infinite lists thanks to laziness; now let’s see if foldr will behave the same way with and without map when working with infinite lists.

Before we dive into the mechanics, let’s try testing the behavior experimentally. We’ll need to a function that will let us get a result when we’re folding over an infinite list. Luckily, we already defined one earlier in the chapter: findFirst. Let’s review the definition quickly:

findFirst predicate =
  foldr findHelper []
  where
    findHelper listElement maybeFound
      | predicate listElement = [listElement]
      | otherwise = maybeFound

You’ve already seen this work with infinite lists. For example, we can find the first even number in an infinite list:

λ findFirst even [1..]
[2]

Let’s try running a version of this that won’t return at all. First, we’ll make an infinite list of odd numbers. Remember that you can start a range with two numbers to specify the step size:

odds = [1,3..]

Next, let’s try finding the first even number in our list of odd numbers. Obviously this won’t even return a value, so you can press control+c to stop trying once you are satisfied:

λ findFirst even odds
Interrupted.

Next, let’s add two new versions of findFirst that each take another function. findFirstCompose will apply the function using composition, and findFirstMap will use map:

findFirstCompose predicate g =
  foldr (findHelper . g) []
  where
    findHelper listElement maybeFound
      | predicate listElement = [listElement]
      | otherwise = maybeFound

findFirstMap predicate g =
  foldr findHelper [] . map g
  where
    findHelper listElement maybeFound
      | predicate listElement = [listElement]
      | otherwise = maybeFound

Let’s load these up into ghci and test them by once again looking for even numbers- but this time we’ll turn any even number greater than 9 into an odd number:

λ incrementOverNine n = if n > 9 then n + 1 else n
λ odds = [1,3..]
λ> findFirstCompose even incrementOverNine odds
[12]
λ> findFirstMap even incrementOverNine odds
[12]

It appears that, even when working with infinite lists, both the composition and mapping versions of our function remain identical. In a way this might not be surprising- we’ve shown that they should behave the same way when we manually stepped through each version, but it might still be unintuitive that we can apply map to an infinite list to get back a new infinite list, and then use foldr on that infinite list and get back a regular value.

To understand why that works, let’s revisit on of our earlier examples and refine it a bit. Earlier, when we were looking at how we could manually expand \f g -> foldr g 0 . map f you’ll recall that we made a substitution like this:

map double [1,2,3] = [double 1, double 2, double 3]

This kind of substitution is fine as long as we’re working with some small finite list, but once we’re dealing with an infinite list you’ll be wondering: how can we safely replace a call to map with a list where every element has a function applied, when the list itself never ends. The answer is that we can’t, but we don’t have to!

Instead of imagining map as transforming the entire list at once, we can think of it in terms of a transformation to the head and tail of a list. In other words, if we can imagine a list as a head and tail:

list = head list : tail list

Then we can think of map f as applying f to the head and map f to the tail:

map f list = f (head list) : map f (tail list)

More concretely:

map double [1,2,3] = double 1 : map double [2,3]
                   = double 1 : (double 2 : map double [3])
                   = double 1 : (double 2 : (double 3 : map double []))
                   = double 1 : (double 2 : (double 3 : []))
                   = [double 1, double 2, double 3]

The thing that makes this all work is that we never need to evaluate any further than the head of the list. Let’s take a look at how this works with one last step through a problem. This time, we’ll look at using foldr and map over our infinite list of odds.

incrementOverTwo = if n > 2 then n + 1 else n

findFirstMap predicate g =
  foldr findHelper [] . map g
  where
    findHelper listElement maybeFound
      | predicate listElement = [listElement]
      | otherwise = maybeFound

findFirstMap even incrementOverTwo odds =

-- Replace incrementOverTwo and odds with their definitions
findFirstMap even (\n -> if n > 2 then n + 1 else n) [1,3,..] =

-- expand findFirstMap
foldr findHelper [] . map (\n -> if n > 2 then n + 1 else n) [1,3,..] =
  if null (map (\n -> if n > 2 then n + 1 else n) [1,3,..])
  then []
  else findHelper ((\n -> if n > 2 then n + 1 else n) 1) $ foldr findHelper [] $ map (\n -> if n > 2 then n + 1 else n) [3,5..]

-- simplify
foldr findHelper [] . map (\n -> if n > 2 then n + 1 else n) [1,3,..] =
  findHelper (if 1 > 2 then 2 else 1) $ foldr findHelper [] $ map (\n -> if n > 2 then n + 1 else n) [3,5..]

-- simplify
foldr findHelper [] . map (\n -> if n > 2 then n + 1 else n) [1,3,..] =
  findHelper 1 (foldr findHelper [] $ map (\n -> if n > 2 then n + 1 else n) [3,5..])

-- expand findHelper
findHelper 1 (foldr findHelper [] $ map (\n -> if n > 2 then n + 1 else n) [3,5..])
  | even 1 = [1]
  | otherwise = foldr findHelper [] $ map (\n -> if n > 2 then n + 1 else n) [3,5..]

-- 'even 1' is false, so simplify the 'otherwise' branch
foldr findHelper [] $ map (\n -> if n > 2 then n + 1 else n) [3,5..]

-- expand foldr again
if null (map (\n -> if n > 2 then n + 1 else n) [3,5..])
then []
else findHelper ((\n -> if n > 2 then n + 1 else n) 3) $ (map (\n -> if n > 2 then n + 1 else n) [5,7..])

-- simplify
if null (map (\n -> if n > 2 then n + 1 else n) [3,5..])
then []
else findHelper 4 $ map (\n -> if n > 2 then n + 1 else n) [5,7..]

-- expand findHelper again
findHelper 4 $ map (\n -> if n > 2 then n + 1 else n) [5,7..]
  | even 4 = 4
  | otherwise = ... -- we wont' get here

As you can see in this example, each time we step through another call to foldr we first apply the function that we’re mapping, then we continue with the fold. Since the recursive call is passed in as the second argument to findHelper, we stop recursively walking through our list as soon as we find a number that’s even after mapping. Thanks to laziness and the way map and foldr work, we’re able to map and fold over an infinite list and still get out a normal value.