Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do foldr and zipWith (:) work together?

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.

like image 899
bug_spray Avatar asked Mar 17 '19 07:03

bug_spray


Video Answer


2 Answers

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]]
like image 98
Will Ness Avatar answered Oct 24 '22 08:10

Will Ness


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.

like image 41
lsmor Avatar answered Oct 24 '22 07:10

lsmor