How do foldr and zipWith (:) work together?

Question

I'm new to Haskell, and I've come across the following code that baffles me:

foldr (zipWith (:)) (repeat []) [[1,2,3],[4,5,6],[7,8,9,10]]

It produces the following result, which after playing around with it, I'm not entirely sure why:

[[1,4,7],[2,5,8],[3,6,9]]

I'm under the impression that (:) prepends items to a list, and that (repeat []) produces an endless amount of empty lists [], and that foldr takes a function, an item, and a list, and condenses the list by consecutively applying the function to each item in the list along with the results.

That is to say, I intuitively understand how the following code produces a result of 10:

foldr (+) 1 [2,3,4]

But, I'm not at all sure why foldr (zipWith (:)) (repeat []) takes a list of lists and produces another list of lists with items grouped by their original inner indices.

Any explanation would be enlightening.

In your `(+)` example, which element gets added to 1? Similarly in your full example, which element gets zipped with `repeat []`? — Micha Wiedenmann, Mar 17 '19 at 09:54
Hopefully the answers given have explained this for you, but I want to add that the "magic" here is the `zipWith (:)`, which takes a list of elements and a list of lists and prepends each element to the corresponding list. Eg. `zipWith (:) [1,2,3] [[4],[5],[6]]` is `[[1,4],[2,5],[3,6]]` — Robin Zigmond, Mar 17 '19 at 10:33

Will Ness · Accepted Answer · 2019-03-17T12:41:25.227

This is very simple. foldr is defined so that

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

thus,

foldr f z [a,b,c,...,n] = f a (f b (f c (...(f n z)...)))

Or, here,

foldr (zipWith (:)) (repeat []) [[1,2,3],[4,5,6],[7,8,9,10]]
=
zipWith (:) [1,2,3] 
  ( foldr (zipWith (:)) (repeat []) [[4,5,6],[7,8,9,10]] )
=
...
=
zipWith (:) [1,2,3] 
  ( zipWith (:) [4,5,6]
      ( zipWith (:) [7,8,9,10] 
          ( foldr (zipWith (:)) (repeat []) [] )))
=
zipWith (:) [1,2,3] 
  ( zipWith (:) [4,5,6]
      ( zipWith (:) [7,8,9,10] 
          ( repeat [] )))
=
zipWith (:) [1,2,3] 
  ( zipWith (:) [4,5,6]
      ( zipWith (:) [ 7, 8, 9,10] 
                    [[],[],[],[],[],[],....] ))
=
zipWith (:) [1,2,3] 
  ( zipWith (:) [ 4,  5,  6 ]
                [[7],[8],[9],[10]] )
=
zipWith (:) [ 1   , 2   , 3   ] 
            [[4,7],[5,8],[6,9]]

And that's that.

_{(Next on the menu, traverse ZipList [[1,2,3],[4,5,6],[7,8,9,10]]... :) or maybe later.)}

As for the other example, it is

foldr (+) 1 [2,3,4] 
= 2 + foldr (+) 1 [3,4] 
= 2 + (3 + foldr (+) 1 [4]) 
= 2 + (3 + (4 + foldr (+) 1 [])) 
= 2 + (3 + (4 + 1))
= 2 + (3 + 5)
= 2 + 8
= 10

because + is strict in both of its arguments.

zipWith is not strict in both arguments, nor is the (:), so the first sequence should be taken as an illustration only. The actual forcing will occur in the top-down order, not bottom-up. For instance,

> map (take 1) . take 1 $ zipWith (:) (1 : undefined) (repeat undefined)
[[1]]

fully in accordance with

map (take 1) . take 1 $ zipWith (:) (1 : undefined) (repeat undefined)
=
map (take 1) . take 1 $ zipWith (:) (1 : undefined) (undefined : repeat undefined)
=
map (take 1) . take 1 $ (1 : undefined) : zipWith (:) undefined (repeat undefined)
=
map (take 1) $ (1 : undefined) : take 0 (zipWith (:) undefined (repeat undefined))
=
map (take 1) $ (1 : undefined) : []
=
map (take 1) [(1 : undefined)]
=
[take 1 (1 : undefined)]
=
[1 : take 0 undefined]
=
[1 : []]
=
[[1]]

score 2 · Answer 2 · answered Mar 17 '19 at 09:20

So using the intuition that foldr folds the list from the right (which is not the recursive definition) you get the following in the easy case:

foldr (+) 1 [2,3,4]
foldr (+) (4 + 1) [2,3]
foldr (+) (3 + 4 + 1) [2]
foldr (+) (2 + 3 + 4 + 1) []
(2 + 3 + 4 + 1)
10

Let's do the same in your example and considering the initial element repeat [] == [[],[],[],[], …]

foldr (zipWith (:)) ([[],[],[],[], ...]) [[1,2,3],[4,5,6],[7,8,9,10]] 
foldr (zipWith (:)) (zipWith (:) [7,8,9,10] [[],[],[],[], ...]) [[1,2,3],[4,5,6]]

wait a min. Lets develop zipWith (:) [7,8,9,10] [[],[],[],[], ...]

zipWith (:) [7,8,9,10] [[],[],[],[], ...] -- apply the funciton (:) pairwise
[7:[], 8:[], 9:[], 10:[]]                 -- we get rid of the infinite list at this point.
[[7],[8],[9],[10]]

From here we can easily follow the rest of the code

foldr (zipWith (:)) ([[],[],[],[], ...]) [[1,2,3],[4,5,6],[7,8,9,10]] 
foldr (zipWith (:)) (zipWith (:) [7,8,9,10] [[],[],[],[], ...]) [[1,2,3],[4,5,6]]
foldr (zipWith (:)) ([[7],[8],[9],[10]]) [[1,2,3],[4,5,6]]
foldr (zipWith (:)) (zipWith (:) [4,5,6] [[7],[8],[9],[10]]) [[1,2,3]]
foldr (zipWith (:)) (zipWith (:) [1,2,3] [[4:7],[5:8],[6:9]) []
zipWith (:) [1,2,3] [[4:7],[5:8],[6:9]
[[1,4,7],[2,5,8],[3,6,9]]

Notice that this is not the proper definition of foldr and we are evaluating the results inmediately instead of lazily (as haskell does), but this is only for the sake of understanding.

I don't think this is correct. it must follow `foldr f z (x:xs) = f x (foldr f z xs)`. — Will Ness, Mar 17 '19 at 10:15
It is not correct, and I say It in the very first ans last line. My purpose was to give the intuition more than the actual definition which I think It can be missleading. But your answer was approved which doesn't prove my point at all hahaha — lsmor, Mar 17 '19 at 20:40

How do foldr and zipWith (:) work together?

2 Answers2