Fold / Recursion over Multiway Tree in f#

Question

I am trying to adapt Brian's Fold for Binary Trees (http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/) to apply for Multiway trees.

Summarizing from Brian's Blog:

Data structure:

type Tree<'a> =  
    | Node of (*data*)'a * (*left*)Tree<'a> * (*right*)Tree<'a>  
    | Leaf 

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),  
                    Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

Binary Tree Fold function

let FoldTree nodeF leafV tree =   
    let rec Loop t cont =   
        match t with   
        | Node(x,left,right) -> Loop left  (fun lacc ->    
                                Loop right (fun racc ->   
                                cont (nodeF x lacc racc)))   
        | Leaf -> cont leafV   
    Loop tree (fun x -> x) 

examples

let SumNodes = FoldTree (fun x l r -> x + l + r) 0 tree7
let Tree6to0 = FoldTree (fun x l r -> Node((if x=6 then 0 else x), l, r)) Leaf tree7

Multiway Tree version [not (fully) working]:

Data Structure

type MultiTree = | MNode of int * list<MultiTree>

let Mtree7 = MNode(4, [MNode(2, [MNode(1,[]); MNode(3, [])]);  
                    MNode(6, [MNode(5, []); MNode(7, [])])])

Fold function

let MFoldTree nodeF leafV tree = 
    let rec Loop  tree cont =   
        match tree with   
        | MNode(x,sub)::tail -> Loop (sub@tail) (fun acc -> cont(nodeF x acc))
        | [] -> cont leafV
    Loop  [tree] (fun x -> x) 

Example 1 Returns 28 - seems to work

let MSumNodes = MFoldTree (fun x acc -> x + acc) 0 Mtree7

Example 2

Doesn't Run

let MTree6to0 = MFoldTree (fun x acc -> MNode((if x=6 then 0 else x), [acc])) Mtree7

Initially I thought the MFoldTree needed a map.something somewhere but I got it to work with the @ operator instead.

Any help on the second example and or correcting what I've done in the MFoldTree function would be great!

Cheers

dusiod

Henton

Answer 1

Another solution could be

let rec mfold f a (MNode(x,s)) = f (List.fold (fun a t -> mfold f a t) a s) x

really, we can treat tree as a lineal struct (to fold it).

Use case

> mfold (+) 0 Mtree7;;
val it : int = 28

Filter is the same with normal fold (because mfold is a normal fold):

> mfold (fun a x -> if x = 6 then a else x + a) 0 Mtree7;;
val it : int = 22

That function could be generic (as List.fold, Array.fold, ... could be generics).

"but the intention of the second is to return the whole tree modified so that any nodes which had the value 6 for example now have value 0"

But that is not a fold computation, is a map!

You can do easilly (treating, again, as a lineal struct)

let rec mmap f (MNode(x,s)) = MNode(f x, List.map (mmap f) s)

Use case

> mmap (fun x -> if x=6 then 0 else x) Mtree7;;
val it : MultiTree =
  MNode
    (4,
     [MNode (2,[MNode (1,[]); MNode (3,[])]);
      MNode (0,[MNode (5,[]); MNode (7,[])])])

Again, I suggest to do it for each possible list container (Seq, List, Array, ...), it enable to user select best strategy in context.

Notes:

• I'm new in F#, excuse me if some is wrong.
• stack size should not be a problem, stack level is equal to tree's deep.

Indefeasible

Hi josejuan, that solution works for the first case, but the intention of the second is to return the whole tree modified so that any nodes which had the value 6 for example now have value 0. Another alternative to Example 1 is: let MFoldTree2 tree = let rec Loop trees = match trees with | MNode(x,sub)::tail -> x + (Loop sub) + (Loop tail) | [] -> 0 Loop tree – Henton

@dusiod that is not a fold! is a map! :D (I have updated solution) – Indefeasible

Answer 2

The trick is that you need to pass one additional function to fold.

In Brian's version, the fold function just takes nodeF that is called with the value in the node and the two values produced from the left and right sub-trees.

That is not sufficient for multiway trees. Here, we need a function nodeF that is called with the value in the node and the result produced by aggregating all values of the sub-trees. But you also need a function - say combineF that combines value produced from multiple sub-trees of a node.

Your fold function is a good start - you just need to add one more recursive call to process tail:

let MFoldTree nodeF combineF leafV tree = 
    let rec Loop trees cont =   
        match trees with   
        | MNode(x,sub)::tail -> 
            // First, process the sub-trees of the current node and get 
            // a single value called 'accSub' representing (aggregated)
            // folding of the sub-trees.
            Loop sub (fun accSub -> 
              // Now we can call 'nodeF' on the current value & folded sub-tree
              let resNode = nodeF x accSub
              // But now we also need to fold all remaining trees that were
              // passed to us in the parameter 'trees'..
              Loop tail (fun accTail ->
                // This produces a value 'accTail' and now we need to combine the
                // result from the tail with the one for the first node 
                // (which is where we need 'combineF')
                cont(combineF resNode accTail) ))
        | [] -> cont leafV
    Loop  [tree] (fun x -> x) 

Summing is easy, because we just use the + operator for both functions:

let MSumNodes = MFoldTree (+) (+) 0 Mtree7

Filtering the tree is more tricky. The nodeF function will get the element in the node and a list of child nodes (that is the result of aggregation) and produces a single node. The combineF function will get the result from a first node (that is a MultiTree value) and a list of children produced from the remaining nodes. The initial value produced from an empty tree is an empty list:

let MTree6to0 = 
  MFoldTree (fun x children -> MNode((if x=6 then 0 else x), children)) 
            (fun head tail -> head::tail) [] Mtree7

Agnesagnese

Amazing - You are a F# Legend!! =P Thank you so much! – Henton

BTW: It is probably much easier to understand the problem when you first try writing the function without continuations. Continuations help you avoid stack overflow, but that is not that often a problem for reasonably sized trees. Once you have non-continuation version, it is not too hard to turn it into continuation-based one. – Agnesagnese

Tried that & don't even want to admit how much time i spent trying to get it that way... now brain hurts too much to step through & properly understand your solution but it will get some proper attention v.soon. Thanks again for your help! – Henton

@TomasPetricek that whole CPS wrinkle in Brian's code sure makes it a bit trickier to master. But once you do master it, it is a very useful technique to have in your toolbox. – Cermet

Could someone add the type signature to this? – Contractile