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
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: