Операция Fold Tree?

Question

Я беру класс в Haskell, и нам нужно определить операцию сгиба для дерева, определенного как:

data Tree a = Lf a | Br (Tree a) (Tree a)

Кажется, я не могу найти какую-либо информацию об операции tfold или о том, что она должна делать. Любая помощь будет принята с благодарностью.

Answer 1

Я всегда думаю о сгибах как о способе систематической замены конструкторов другими функциями. Так, например, если у вас есть самодельный тип List (определенный как data List a = Nil | Cons a (List a)), соответствующий фолд можно записать как:

listfold nil cons Nil = nil
listfold nil cons (Cons a b) = cons a (listfold nil cons b)

или, может быть, более кратко, как:

listfold nil cons = go where
    go Nil = nil
    go (Cons a b) = cons a (go b)

Тип listfold равен b -> (a -> b -> b) -> List a -> b. То есть требуется два «конструктора замены»; один рассказывает, как значение Nil должно быть преобразовано в b, другой конструктор замены для конструктора Cons, рассказывает, как первое значение конструктора Cons (типа a) должно быть объединено с значение типа b (почему b? потому что сгиб уже был применен рекурсивно!), чтобы получить новый b, и, наконец, List a, чтобы применить к ней целую челки - с результатом b.

В вашем случае тип tfold должен быть (a -> b) -> (b -> b -> b) -> Tree a -> b по аналогии; надеюсь, вы сможете взять его оттуда!

Answer 2

Представьте, что вы определили, что дерево должно отображаться следующим образом:

<1 # <<2#3> # <4#5>>>

Складывание такого дерева означает замену каждого узла ветви фактической предоставленной операцией, которую нужно выполнить по результатамрекурсивно выполнено свертывание для составляющих типа данных (здесь два дочерних узла узла, каждый из которых представляет собой дерево), например, с +, с получением

(1 + ((2+3) + (4+5)))

Итак, дляоставляет, вы должны просто взять значения внутри них, а для ветвей, рекурсивно применить складку для каждого из двух дочерних узлов, и объединить два результата с предоставленной функцией, с которой дерево свернуто,( edit: ) При «взятии» значений из листьев вы можете дополнительно преобразовать их, применив унарную функцию.Таким образом, в целом, вашему свёртыванию понадобятся две функции, предоставленные пользователем, одна для листьев , Lf, а другая для объединения r результатов r эвристическое свертывание древовидных составляющих (то есть ветвей) узлов ветвления , Br.

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

Еще одно отличие, которое следует здесь осознать, это что вы сбросите, а как сложите.Т.е. вы можете сложить свое дерево линейным способом, (1+(2+(3+(4+5)))) == ((1+) . (2+) . (3+) . (4+) . (5+)) 0, или вы можете сложить линейный список древовидным способом, ((1+2)+((3+4)+5)) == (((1+2)+(3+4))+5).Все дело в том, как заключить в скобки итоговое «выражение».Конечно, в классическом взгляде на сворачивание структура выражения соответствует структуре сворачиваемой структуры данных;но вариации существуют .Также обратите внимание, что операция объединения может быть не строгой, и тип " r esult", который он потребляет / производит, может выражать составной (списки и тому подобное), а также атомарный (числаи т. д.), значения.

(обновление 2019-01-26) Это повторное заключение в скобки возможно, если операция объединения является ассоциативной, например +: (a<sub>1</sub>+a<sub>2</sub>)+a<sub>3</sub> == a<sub>1</sub>+(a<sub>2</sub>+a<sub>3</sub>).Тип данных вместе с такой ассоциативной операцией и элементом «ноль» (a+0 == 0+a == a) известен как «Monoid», а понятие сворачивания в «Monoid» захватывается классом типа Foldable.

Answer 3

Сгиб - это операция, которая «уплотняет» структуру данных в одно значение с помощью операции. Существуют различия в зависимости от того, есть ли у вас начальное значение и порядок выполнения (например, для списков у вас есть foldl, foldr, foldl1 и foldr1), поэтому правильная реализация зависит от вашего назначения.

Полагаю, ваш tfold должен просто заменить все листья своими значениями, а все ветви приложениями данной операции. Нарисуйте пример дерева с несколькими числами, «сверните» его с помощью операции типа (+). После этого должно быть легко написать функцию, выполняющую то же самое.

Answer 4

Сгиб в списке - это сокращение от списка в один элемент.Она берет функцию и затем применяет эту функцию к элементам, по два за один раз, пока у нее не будет только одного элемента.Например:

Prelude> foldl1 (+) [3,5,6,7]
21

... определяется путем выполнения операций один за другим:

3 + 5 == 8
8 + 6 == 14
14 + 7 == 21

Можно написать сгиб

ourFold :: (a -> a -> a) -> [a] -> a
ourFold _         [a]        = a -- pattern-match for a single-element list. Our work is done.
ourFold aFunction (x0:x1:xs) = ourFold aFunction ((aFunction x0 x1):xs)

Aсгиб дерева сделал бы это, но двигался вверх или вниз по ветвям дерева.Для этого сначала нужно сопоставить с шаблоном, чтобы увидеть, работаете ли вы на Листе или на Ветке.

treeFold _ (Lf a)   = Lf a -- You can't do much to a one-leaf tree
treeFold f (Br a b) = -- ...

Остальное остается на ваше усмотрение, так как это домашняя работа.Если вы застряли, попробуйте сначала подумать, каким должен быть тип.