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

Answer 1

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

Answer 2

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.