CODEWITHSUNDEEP
ocaml
gregor vojvoda
gregor vojvoda

Reputation: 139

Ocaml change type 'a tree to 'b tree

I have defined 

type 'a tree =
| Tree of 'a tree * 'a * 'a tree
| Leaf of 'a
| Null;;

Now I have to define a function that will change the whole 'a tree in to an 'b tree.

I have searched on google and tried to solve it myself but I'm stucked. Any tips?

Upvotes: 2

Views: 960

Answers (1)

hnefatl
hnefatl

Reputation: 6037

One possibility is an analog to the map function but over trees. For example:

let rec treemap f t = match t with
    Null           -> Null
 |  Leaf x         -> Leaf (f x)
 |  Tree (l, x, r) -> Tree (treemap f l, f x, treemap f r)

Here t : 'a tree, f : 'a -> 'b, and treemap : 'a tree -> ('a -> 'b) -> 'b tree, which produces a 'b tree as desired.

This is the most "natural" way of making such a function: you have a tree with values of type 'a, and you want to get a new tree with values of type 'b - so you just need a tree and some way of mapping a value of one type to a value of the other.

I think it's worth pointing out that this isn't the only such function. You could make a function treereplace : 'a tree -> 'b -> 'b tree, which just creates an identically structured tree but replacing every value with the one given, or a function which does the same but flips the left/right branches of each Tree node. There's an infinite number of functions taking an 'a tree and producing a 'b tree that you could make, the above is just arguably the most natural and useful.

Edit: Improvements/critique welcome - I don't know OCaml, I hacked this example together from an understanding of SML.

Upvotes: 9

Related Questions