Работа с сгибом дерева?

Question

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

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

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

Answer 1

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

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) 

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

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

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

Answer 2

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

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

Answer 3

Я всегда думаю о складках как способ систематической замены конструкторов другими функциями. Так, например, если у вас есть сделай сам 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? потому что fold уже было применено рекурсивно!), чтобы получить новый b и, наконец, List a, чтобы применить всю привязку к - с результатом b.

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

Answer 4

Представьте, что вы определяете, что дерево должно отображаться следующим образом, например: "<1#<<2#3>#<4#5>>>". Складывание такого дерева означает замену каждого узла ветви фактической поставленной операцией, которая должна быть выполнена по результатам рекурсивно выполненной складки на составляющих типа данных (здесь два дочерних узла узла, которые сами по себе, каждое дерево) например, с +, производя (1+((2+3)+(4+5))).

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

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

Другое различие реализовать здесь, , что вы сложите и как вы сложите его. То есть вы могли бы сложить свое дерево в линейном моде, (1+(2+(3+(4+5)))), или вы могли бы свернуть линейный список в древовидный моды. Это все о том, как вы вставляете в скобки результат «выражение». Конечно, в классическом исполнении складывается структура exression следует за структурой структуры, которая складывается; но variations do exist. Заметим также, что операция объединения может быть не строгой, и она может потреблять/производить состав, а также атомные значения.