Work with a tree?

Question

I take a class in Haskell, and we need to define a bend operation for the tree defined by:

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

I can not find any information about the operation "tfold" or really about what it should do. Any help would be greatly appreciated.

Answer 1

I always think of folds as a way to systematically replace constructors with other functions. So, for example, if you have your own List type (defined as data List a = Nil | Cons a (List a) ), the corresponding fold can be written as:

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

or, perhaps more briefly, as:

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

Type listfold - b -> (a -> b -> b) -> List a -> b . In other words, two “replacement constructors" are required; one of which indicates how the Nil value should be converted to b , the other is a replacement constructor for the Cons constructor, telling how the first value of the Cons constructor (type a ) should be combined with a value of type b (why b ? because addition was already applied recursively !) to get a new b and finally a List a apply all she-bang to - with the result of b .

In your case, the type tfold should be (a -> b) -> (b -> b -> b) -> Tree a -> b same way; hope you can take it from there!

Answer 2

Imagine that you have determined that the tree should be displayed as follows, for example:

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

Folding such a tree means replacing each branch node with the actual provided operation, which must be performed with the results of a recursive bend performed for data type components (here, for example, the node of two child nodes, which themselves are each tree), for example, with + , producing

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

Thus, for the leaves, you just need to take the values ​​inside them, and for the branches recursively apply a fold for each of the two child nodes and combine the two results with the provided function, the one with which the tree is collapsed. ( edit :) When "taking" values ​​from leaves, you can further transform them by applying a unary function. Thus, in general, your collapse will need two user-defined functions: one for the leaves, Lf , and the other for combining the results of the recursive folding of the tree-like components (i.e. branches) of the branch nodes, Br .

Your tree data type could be defined differently, for example, with possibly empty leaves, and with internal nodes that also carry values. Then you will need to specify a default value that will be used instead of empty end nodes, and a three-way combination. However, you must have a fold defined by two functions corresponding to the two cases of determining the data type.

Another difference that needs to be realized is what you add up and how you add it up. Those. you can stack the tree linearly, (1+(2+(3+(4+5)))) == ((1+). (2+). (3+). (4+). (5+)) 0 , or you can add a linear list in the form of a tree, ((1+2)+((3+4)+5)) == (((1+2)+(3+4))+5) . The thing is how to bracket the final "expression" in parentheses. Of course, in the classical approach, the convolution of the structure of an expression follows the structure of the convolution of data; but variations exist . Also note that the union operation may not be strict, and the type of “result” that it consumes / produces can express compound (lists and the like), as well as atomic (numbers and the like) values.

(update 2019-01-26) This repeated bracket is possible if the join operation is associative, for example + : (a 1 +a 2 )+a 3 == a 1 +(a 2 +a 3 ) . The data type, together with such an associative operation and the element "zero" ( a+0 == 0+a == a ) is known as the "monoid", and the concept of folding into a "monoid" is fixed by the Foldable type class.

Answer 3

Dropping a list is the abbreviation of a list in one element. It takes a function and then applies this function to the elements, two at a time, until there is only one element. For example:

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

... found by performing operations one by one:

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

Folds can be recorded

 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) 

The tree will do this, but move up or down the branches of the tree. To do this, you first need to map the template to see if you are working in a Sheet or Branch.

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

The rest is yours, as this is homework. If you are stuck, try to think about what type should be first.

Answer 4

A bend is an operation that “brings together” a data structure into a single value using an operation. There are different options if you have an initial value and execution order (for example, for lists you have foldl , foldr , foldl1 and foldr1 ), so the correct implementation depends on your purpose.

I think your tfold should just replace all sheets with its values ​​and all branches with applications of this operation. Draw an example tree with some numbers, the "collapse" gave him an operation like (+) . After that, it should be easy to write a function that does the same thing.