Fold / Recursion over Multiway Tree in f#

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

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.