как foldr работает с этим деревом данных? - PullRequest
3 голосов
/ 28 мая 2019

Я знаю, как foldr работает на Leaf, но я не знаю, как foldr работает на Node. Что такое параметр \ x z ', если у нас уже есть f и z в качестве параметра. предположим, у нас есть

tree = Node [Leaf 1, Leaf 2, Node [Leaf 1, Leaf 3]]

как работает этот код

foldr (+) 0 tree
data RoseTree a =  Leaf a | Node [RoseTree a] 
instance Foldable RoseTree where 
    foldr f z (Leaf x) = f x z
    foldr f z (Node ns) = 
        foldr (\x z' -> foldr f z' x) z ns 

Ответы [ 2 ]

6 голосов
/ 28 мая 2019

Определение foldr для Node вызовов foldr в списке RoseTree с.Затем внутри этого foldr он вызывает foldr для каждого поддерева, используя текущий аккумулятор в качестве начального параметра.

По сути, даже если функция выглядит как вызовы foldr дважды, этокаждый раз вызывая его для разных типов, и поэтому только один является рекурсивным.Другой foldr определен для [a].

4 голосов
/ 28 мая 2019

Мы можем обсудить реализацию с вашими примерами данных:

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 приведет к складыванию значений вместе, где результатскладка хвостовых элементов используется в качестве начального значения сгиба с головным элементом.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...