Как работают foldr и zipWith (:)?

Question

Я новичок в Haskell, и я наткнулся на следующий код, который сбивает меня с толку:

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

Это дает следующий результат, который после игры с ним, я не совсем уверен, почему:

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

У меня сложилось впечатление, что (:) добавляет элементы в список, и что (repeat []) создает бесконечное количество пустых списков [], а foldr принимает функцию, элемент и список и сокращает список, последовательно применяя функцию к каждому элементу списка вместе с результатами.

То есть я интуитивно понимаю, как следующий код дает результат 10:

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

Но я не совсем уверен, почему foldr (zipWith (:)) (repeat []) берет список списков и создает другой список списков с элементами, сгруппированными по их исходным внутренним индексам.

Любое объяснение было бы поучительным.

Answer 1

Это очень просто. foldr определяется так, чтобы

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

Таким образом,

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

Или вот,

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]] 

И это все.

_{(Далее в меню, traverse ZipList [[1,2,3],[4,5,6],[7,8,9,10]] ... :) или, может быть, позже.)}

---

Что касается другого примера, это

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

потому что + является строгим в обоих аргументах.

zipWith не является строгим в обоих аргументах, как и (:), поэтому первая последовательность должна рассматриваться только как иллюстрация. Фактическое форсирование будет происходить в порядке сверху вниз, а не снизу вверх. Например,

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

полностью в соответствии с

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]]

Answer 2

Таким образом, используя интуицию, которая foldr сворачивает список справа (что не является рекурсивным определением), вы получаете следующее в простом случае:

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

Давайте сделаем то же самое в вашем примереи с учетом начального элемента 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]] 

подождите мин.Давайте разработаем 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]]

Отсюда мы можем легко следовать остальной части кода

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]]

Обратите внимание, что это не правильное определение foldr, и мы оцениваемрезультаты немедленно, а не лениво (как это делает haskell), но это только для понимания.