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.