CODEWITHSUNDEEP
haskelltreefold
Sniper
Sniper

Reputation: 418

How this Fold Tree Function works in Haskell

Here i am trying to understand this function which folds a tree to one value. It shows that foldTree takes two functions as arguments, it applies first function to the element of the Tree a and then passes the result to second function (b->b->b) which again performs some operation and produces final result. 

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)

I am trying following input to see how it works. 

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))

It returns 

Output 1 : 12
Output 2 : 14

The problem i am facing in understanding is where the second function argument operation is performed? and how it actually passes the values to the second function, apparently second function takes two values as arguments but first function only returns one value... from where the second value is passed? Can i say it took result of first function twice so that x and y values are same? because second function (\x y -> x + y) takes two arguments? but then result would not be same as mentioned in output 1 and 2.

Secondly does it return the final result after performing second function or it returns the result after applying only the first function because i am confused even i removed second function it produces the same results.

Thirdly what is the purpose of g here outside of two curly brackets? ***g*** (foldTree f g tl) (foldTree f g tr) it took it as a Data constructor from the start or what? I know data constructor can be constructed as smart constructors but here how it treated.

I am so confused understanding this, may be i am complicating a lot of concepts in this one? Please don't hesitate to go into details.

Upvotes: 2

Views: 1118

Answers (1)

chi
chi

Reputation: 116139

To understand the result of foldTree f g tree you can use this technique:

  • Write down the value of tree using the constructors, e.g. in your example we have (Node (Node (Leaf 1) (Leaf 2)) (Leaf 4)).
  • Syntactically replace Leaf with f and Node with g. For the previous example, we get (g (g (f 1) (f 2)) (f 4)).
  • Use the definitions of functions f and g to compute the result of the last expression. For the example, we get ((+) ((+) ((*2) 1) ((*2) 2)) ((*2) 4)) which is ((+) ((+) (1*2) (2*2)) (4*2)) which is ((1*2) + (2*2)) + (4*2) which is (2+4)+8 = 14.

Note how we replace Leaf a unary constructor with f, a unary function, and Node, a binary constructor with g, a binary function. So, we always have the right number of arguments for our functions. More in general, the types will match just fine.

Upvotes: 4

Related Questions