Мы можем обсудить реализацию с вашими примерами данных:
foldr (+) 0 (Node [Leaf 1, Leaf 2, Node [Leaf 1, Leaf 3]])
Таким образом, здесь у нас есть Node
, поэтому мы берем второе предложение, поэтому заменим его на:
foldr (\x z' -> foldr (+) z' x) 0 [Leaf 1, Leaf 2, Node [Leaf 1, Leaf 3]]
Таким образом, внешний foldr
работает в списке, что означает, что документация :
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
Так что это означает, что выше foldr
заменяется на:
foldr (+) (foldr (+) (foldr (+) 0 (Node [Leaf 1, Leaf 3])) (Leaf 2)) (Leaf 1)
Итак, внешняя функция теперь foldr (+) (...) (Leaf 1)
, это первое предложение нашего определения foldr
, так что оно равно:
(+) 1 (foldr (+) (foldr (+) 0 (Node [Leaf 1, Leaf 3])) (Leaf 2))
Затем мы можем оценить выражение foldr (+) (...) (Leaf 2)
, которое обрабатывается таким же образом:
(+) 1 ((+) 2 (foldr (+) 0 (Node [Leaf 1, Leaf 3])))
или менее многословно:
1 + 2 + foldr (+) 0 (Node [Leaf 1, Leaf 3])
Тогда, наконец, мы снова имеем foldr (+) 0
который работает на Node
, таким образом, это снова приводит к оценке, как обсуждалось выше:
1 + 2 + foldr (+) (foldr (+) 0 (Leaf 3)) (Leaf 1)
Таким образом, мы можем снова оценить внешнее foldr (+)
до:
1 + 2 + (+) 1 (foldr (+) 0 (Leaf 3))
и внутреннее foldr (+)
до:
1 + 2 + (+) 1 ((+) 3 0)
или менее подробное:
1 + 2 + 1 + 3 + 0
, что эквивалентно:
7
, которое является суммой thУзлы в Leaf
s.
Важно отметить, что внешний foldr
(здесь обозначается курсивом ), не является тем же foldr
функционирует как внутренняя foldr
(здесь обозначается полужирный ) в реализации: внешний работает со списком как функтор, тогда как внутренний - тот, который мы определяемв instance Foldable RoseTree
:
instance Foldable RoseTree where
<b>foldr</b> f z (Leaf x) = f x z
<b>foldr</b> f z (Node ns) = <i>foldr</i> (\x z' -> <b>foldr</b> f z' x) z ns
Если мы, таким образом, выполним foldr
для Tree
с функцией f
и начальным значением z
, мы заменим все листья на f x z
, (то есть для foldr (+) 0
, то есть (+) x 0
, или x + 0
).
* Node
s приведет к складыванию значений вместе, где результатскладка хвостовых элементов используется в качестве начального значения сгиба с головным элементом.