5

I'm an IT Student and kind of a newbie to OCaml

Recently, studying for an exam I found this exercise.

Given: type 'a tree = Tree of 'a * 'a tree list

Define a function mtree : 'a tree ->'a, that returns the greatest value of all the nodes in a multiway tree, following the usual order relation in OCaml (<=)

I've come to do something like this below, which, of course, is not working.

let rec mtree (Tree (r, sub)) =
        let max_node (Tree(a, l1)) (Tree(b, l2)) =
            if a >= b then (Tree(a, l1)) else (Tree(b, l2)) in
        List.fold_left max_node r sub;;

After reading an answer to this I'm posting the fixed code.

let rec mtree (Tree(r,sub)) =
    let max_node (Tree(a, l1)) (Tree(b, l2)) =
        if a >= b then a else b in
    List.fold_left (max_node) r (List.map mtree sub);;

The idea is the same, fold the list comparing the nodes making use of my local function to do so and travel through the tree by calling the function itself over the nodes lists of the consecutive levels.

Is still not working, though. Now complains about max_node in the fold_left part.

Error: This expression has type 'a tree -> 'a tree -> 'a
       but an expression was expected of type 'a tree -> 'a tree -> 'a tree

And here I'm definitely lost because I can't see why does it expects to return an 'a tree

Joel
  • 4,732
  • 9
  • 39
  • 54
Trigork
  • 177
  • 1
  • 16
  • Can you explain what you expect to happen and what is actually happening? – Abizern Jun 28 '13 at 18:13
  • What I expect is nothing else that what the exercise asks for. What is happening is that OCaml top level complains about the type of sub being 'a tree tree list. – Trigork Jun 28 '13 at 18:15
  • Hint: try to write a recursive function that takes two arguments (a value `v : 'a` and a tree `t : 'a tree`) and computes the maximum of `v` and the maximum of `t` – Thomash Jun 30 '13 at 10:51

2 Answers2

4

This code is pretty credible (IMHO). The key thing missing is that it doesn't traverse subtrees of the subtrees. Note that you define your function as recursive (which is very reasonable), but it never calls itself.

Another issue to point out is that the problem statement calls for a "value" from the tree, but your code is returning a whole tree node.

Jeffrey Scofield
  • 65,646
  • 2
  • 72
  • 108
2

Answering my own question is kind of lame but with the hints received here I could finish it I'm leaving my code here for anyone facing similar problems.

let maxt (Tree(r,b)) =
    let rec aux (Tree(r,b)) =
        match b with
        [] -> [r]
        |l -> [r]@( List.fold_right (@) (List.map aux b) [])
    in List.fold_left max r (aux (Tree(r,b)));;
barti_ddu
  • 10,179
  • 1
  • 45
  • 53
Trigork
  • 177
  • 1
  • 16
  • What do you think is the complexity of this answer? It is actually very bad, I'm sure you can improve it. Why didn't you kept your first idea of simply traversing the tree? – Thomash Jun 30 '13 at 10:46