type ('a, 'b) t=
| Leaf of 'b
| Node of 'a * ('a, 'b) t* ('a, 'b) t
I want to implement a map f g t function with signature: val map: (('a -> unit) * ('b -> unit)) -> ('a,'b) t -> unit
where:
f to all node data
g to all leaf data
and it should iterate via preorder traversal (root-left-right)
This is what I have tried:
let rec map f g t =
match t with
| Leaf(w) -> Leaf(g w)
| Node (v, l, r) -> Node (f v, map f g l, map f g r)
But I don’t know how to get that signature matched, any ideas?
>Solution :
If you want f and g to each have a return type of unit, then this isn’t really map at all. It’s more of an iter function, and you might write it more like:
let rec iter f g =
function
| Leaf v -> let () = g v in ()
| Node (v, l, r) ->
let () = f v in
let () = iter f g l in
iter f g r
This function has the following type because we have provided enough information to the compiler to infer that f and g return unit.
('a -> unit) -> ('b -> unit) -> ('a, 'b) t -> unit
Note that this also guarantees that the recursive call on the left branch will occur first, whereas evaluation order in Node (f v, map f g l, map f g r) may change between implementations.