CODEWITHSUNDEEP
haskelltreefold
Сергей Кузминский
Сергей Кузминский

Reputation: 367

Recursion in treeFold function

I have tree data type:

data Tree a = Node
  { rootLabel :: a,        -- label value
    subForest :: [Tree a]  -- zero or more child trees
  }

{-- Node (a) [] ..or...  Node (a1) [ Node (a2) [..], Node (a3) [..] ] --}

and i need to write treeFold function, i think that i need first function that make something with label value and second function that takes two results of func1 and make some final result and so on. I start writing the recursion function treeFold, write function for minimal Tree with 0 child trees, but i can't finish my function for not empty list of child's trees.

I need to take 1st child and rest of child's list and make new tree from it to use this new tree for recursive calls or not? 

treeFold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
treeFold func1 _ (Node a1 []) = func1 a1   
treeFold func1 func2 (Node a1 [y]) = func2 (func1 a1) (treeFold func1 func2 y) 
treeFold func1 func2 (Node a1 [y1,y2]) = func2 (func1 a1) (treeFold func1 func2 (y1

Upvotes: 2

Views: 746

Answers (1)

Stefan Holdermans
Stefan Holdermans

Reputation: 8050

Unfortunately, the term "fold" is a bit overloaded.

Structural recursion

If you want your fold function to capture some notion of structural recursion, I don't think, for this type of trees, you want it to take two arguments (in addition to the tree argument).

Type

The type of such a fold function follows from the types of the constructors of your datatype.

In your case, your datatype

data Tree a = Node {rootLabel :: a, subForest :: [Tree a]}

has only one constructor:

Node :: a -> [Tree a] -> Tree a

Hence, in addition to the tree you are folding, your fold function will only take one argument. The type of this argument is obtained by replacing all occurrences of Tree a in the constructor type by a fresh type variable, say b:

           a  -> [Tree a] -> Tree a

           |        |          |
           |        |          |
          \ /      \ /        \ /
           -        -          -

           a  -> [   b  ] ->   b

The type variable b also constitutes the return type of your function. That is, you get

treeFold :: (a -> [b] -> b) -> Tree a -> b

Implementation

The implementation of this function follows from the definition of your datatype as well. You obtain the b-typed values that you have to pass to the first argument of your fold by recursively applying your fold function to the Tree a-typed parts of a Node. What is a bit tricky here is that those parts are stored in a list, so you also need to map over that list:

treeFold f (Node x xss) = f x (map (treeFold f) xss)

or, arguably a bit nicer:

treeFold f = h
  where
    h (Node x xss) = f x (map h xss)

The key idea is that you replace all applications of the constructor Node in your tree value by applications of the function f that is passed as the first argument to treeFold.

Examples

For example, you can now use treeFold to define a function that sums all elements in a tree:

total :: Num a => Tree a -> a
total =  treeFold (\n ns -> n + sum ns)

Or a function that simply returns how many elements a tree contains:

size :: Tree a -> Int
size =  treeFold (\_ ns -> 1 + sum ns)

Reductions

Another brand of folds are those that perform a (left- or right-biased) reduction of a data structure. Those folds indeed typically take two additional arguments:

treeFoldr :: (a -> b -> b) -> b -> Tree a -> b
treeFoldl :: (b -> a -> b) -> b -> Tree a -> b

These functions you can for example implement in terms of an auxiliary function flatten

flatten :: Tree a       -> [a]
flatten    (Node x xss) =  x : concatMap flatten xss

and by reusing the list functions foldr and foldl from the Prelude:

treeFoldr :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr    op               e =  foldr op e . flatten

treeFoldl :: (b -> a -> b) -> b -> Tree a -> b
treeFoldl    op               e =  foldl op e . flatten

For example:

total = treeFoldl (+) 0
size  = treeFoldr (const succ) 0

More variations

Depending on what concept you want to generalise, there are more variations. One could argue, for instance, that for capturing structural recursion, mapping over the subforest is not needed/desirable and wind up with something like

treeFold' :: (a -> c -> b) -> (c, b -> c -> c) -> Tree a -> b
treeFold' node (nil, cons) = h
  where
    h (Node x xss) = node x (foldr (cons . h) nil xss)

and then

total = treeFold' (+) (0, (+))
size  = treeFold' (const succ) (0, (+))

Upvotes: 7

Related Questions