Fold / Recursion over a multi-track tree in f #

Question

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

To summarize 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 function fold

 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 xlr -> x + l + r) 0 tree7 let Tree6to0 = FoldTree (fun xlr -> 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

Does not work

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

I originally thought that MFoldTree needed map.something somewhere, but I got it to work with the @ operator.

Any help on the second example and fixing what I did in the MFoldTree function would be great!

Greetings

dusiod

Answer 1

Another solution might be

 let rec mfold fa (MNode(x,s)) = f (List.fold (fun at -> mfold fat) as) x 

indeed, we can consider the tree as a string structure (to collapse it).

Use case

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

The filter matches the normal fold (because mfold is the normal fold):

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

This function may be generic (since List.fold , Array.fold , ... may be generics).

"but the intention of the second is to return the entire tree, modified so that any nodes that have a value of 6, for example, now have a value of 0"

But this is not a calculation of fold , it is map !

You can do easilly (considering, again, as a linear structure)

 let rec mmap f (MNode(x,s)) = MNode(fx, 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 doing this for every possible list container ( Seq , List , Array , ...), it allows the user to choose the best strategy in context.

Notes:

• I'm new to F #, sorry if someone is wrong.
• stack size should not be a problem; stack level is equal to tree depth.

Answer 2

The trick is that you need to pass one extra function to discard cards.

In Brian's version, the fold function simply accepts nodeF , which is called with a value in node and two values ​​obtained from the left and right subtrees.

This is not enough for multi-track trees. Here we need the nodeF function, which is called with the value in node and the result obtained by aggregating all the values ​​of the subtrees. But you also need a function - say combineF , which combines the value obtained from several subtrees of the node.

Your bend function is a good start - you just need to add another recursive call to handle 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) 

The hack is simple because we just use the + operator for both functions:

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

Tree filtering is more complicated. The nodeF function will receive an element in node and a list of child nodes (that is, the result of aggregation) and return a single node. The combineF function will receive the result from the first node (this is the MultiTree value) and a list of children created from the remaining nodes. The initial value obtained from the 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