Как работает эта функция Fold Tree в Haskell - PullRequest
Новая
       41

Как работает эта функция Fold Tree в Haskell

1 голос
/ 11 марта 2019

Здесь я пытаюсь понять эту функцию, которая сворачивает дерево в одно значение.Он показывает, что foldTree принимает две функции в качестве аргументов, он применяет первую функцию к элементу Tree a, а затем передает результат второй функции (b->b->b), которая снова выполняет некоторую операцию и выдает окончательный результат.

foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f g (Leaf x) = f x
foldTree f g (Node tl tr) = g (foldTree f g tl) (foldTree f g tr)

Я пытаюсь ввести данные, чтобы увидеть, как они работают.

Input 1:  foldTree (*2) (\x y -> x + y) (Leaf 6)
Input 2:  foldTree (*2) (\x y -> x + y) (Node (Node (Leaf 1) (Leaf 2)) (Leaf 4))

Возвращает 

Output 1 : 12
Output 2 : 14

Проблема, с которой я сталкиваюсь в понимании, заключается в том, где выполняется операция второго аргумента функции?и как он фактически передает значения второй функции, очевидно, вторая функция принимает два значения в качестве аргументов, но первая функция возвращает только одно значение ... откуда передается второе значение?Могу ли я сказать, что результат первой функции удвоился , поэтому значения x и y совпадают?потому что вторая функция (\x y -> x + y) принимает два аргумента?но тогда результат не будет таким, как указано в выходных данных 1 и 2.

Во-вторых, возвращает ли он окончательный результат после выполнения второй функции, или возвращает результат после применения только первой функции, потому что я запутался, даже если меня удалилиВторая функция дает те же результаты.

В-третьих, какова цель g здесь, кроме двух фигурных скобок?***g*** (foldTree f g tl) (foldTree f g tr) с самого начала он воспринимался как конструктор данных или как?Я знаю, конструктор данных может быть построен как умные конструкторы, но вот как это лечить.

Я так растерялся, понимая это, может быть, я усложняю многие концепции в этом?Пожалуйста, не стесняйтесь вдаваться в детали.

1 Ответ

3 голосов
/ 12 марта 2019

Чтобы понять результат foldTree f g tree, вы можете использовать эту технику:

  • Запишите значение tree, используя конструкторы, например, в вашем примере мы имеем (Node (Node (Leaf 1) (Leaf 2)) (Leaf 4)).
  • Синтаксически заменить Leaf на f и Node на g. Для предыдущего примера мы получаем (g (g (f 1) (f 2)) (f 4)).
  • Используйте определения функций f и g для вычисления результата последнего выражения. Например, мы получаем ((+) ((+) ((*2) 1) ((*2) 2)) ((*2) 4)), который ((+) ((+) (1*2) (2*2)) (4*2)), что ((1*2) + (2*2)) + (4*2), что (2+4)+8 = 14.

Обратите внимание, как мы заменяем Leaf унарный конструктор на f, унарную функцию и Node, бинарный конструктор на g, бинарную функцию. Таким образом, у нас всегда есть правильное количество аргументов для наших функций. В общем, типы будут соответствовать просто отлично.

...