OCaml option value tree

2
votes

I've a task to write a function with type ‘a btree -> ‘a option list that stores the given tree in a list of elements of type ‘a option in postfix order (postorder).

Internal nodes will be represented by None, external nodes (leaves) with value x will be represented by Some x.

So far it's easy to do for leaves, but how to put it in an 'a option list?

type 'a btree = L of 'a | N of 'a btree * 'a btree ;;

let rec store t =
    match t with
        | L x -> Some x
        | N (a,b) -> None ???   
;;

The second match case I know is incorrect, but how to solve it?

2
treeocaml
By the way, is this homework? It's not a bad thing if it is, but it's considered polite to say so. - Asherah
Yes it is , and hopefully will be the last one :D. It's good that I've some notions of Ocaml but honestly its something that I'll never use in the future. - João Oliveira
You might be surprised; I've used it in my job a bunch of times, and it's not what you'd call an academic setting. Sometimes it just is the right tool for the job. - Asherah
I'd recommend you check out @gasche's answer; using an accumulator will make this much faster, and avoids the list appends, which are O(n) in the length of each list. - Asherah
Uhm? That would be a preorder traversal, not postorder. For reference, I'm using the definitions from the Wikipedia page on tree traversal. Additionally, your change wouldn't help the fact that it allows you to start at a leaf; that's just the nature of the function as defined. You could try to further restrict it to not allow you to start at a leaf, but it would be unnecessarily ugly. - Asherah

2 Answers

3
votes

If you look at your first case, you'll see it's also not quite there; it's returning 'a option, but you want the function to return an 'a option list.

Clearly you'll be returning a list, so fix that first:

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> [None] (* ??? *)

Now let's fix the second case; we want to append None to our output, but before that, we want the nodes of our subtrees:

let rec store = function
  | L x -> [Some x]
  | N (a,b) -> (store a) @ (store b) @ [None]

@ has the type

'a list -> 'a list -> 'a list

i.e. it joins lists together. We want to join the list of results from the left subtree, then the right, and then finally the result for this internal node.

3
votes

In case someone is interested by this refinement, it is possible to do a bit better, performance-wise, than Len's solution by threading an additional accumulator parameter.

The idea is to move from a function store : 'a btree -> 'a option list that takes a tree and produce a list to a function store' : 'a btree -> 'a option list -> 'a option list, that adds the element of the tree to an existing list passed as parameter.

let rec store' t acc = match t with
  | L x -> Some x :: acc
  | N (a, b) ->
    store' a (store' b (None :: acc))

With this definition, elements are only added once in the final result list, instead of first being used to build a temporary store a list, then appended a second time to the final result through the (@) operator.

The parameter order is important because writing t before acc gives an intuition of the final element order in the list: the elements of t will be before the elements already present in acc. This allows the N case to read quite naturally: it is easy to see that the result will first have the elements of a, then b, then None, then acc.

Finally, you can of course define store in terms of store':

let store t = store' t []

It is customary to wrap the first definition inside the second one (if you don't want to expose this "lower-level" function to the users), and to give it the same name as the outer definition (which doesn't conflict as it is not recursive, so does not enter the inner scope):

let store t =
  let rec store t acc = match t with
    | L x -> Some x :: acc
    | N (a, b) ->
      store a (store b (None :: acc))
  in store t []

Of course, whether this definition is "better" than Len's one depends on what your evaluation criterion are. Len's solution is shorter, easier to read, and maps the original problem more closely.

(You may get the best of both world by using lazy enumerations instead of strict lists, but that's yet another story.)