Max Value of a Multiway Tree in OCaml

Posted by Trigork on Stack Overflow See other posts from Stack Overflow or by Trigork
Published on 2013-06-28T17:52:56Z Indexed on 2013/06/29 10:21 UTC
Read the original article Hit count: 738

Filed under:
|
|

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

© Stack Overflow or respective owner

Related posts about tree

Related posts about ocaml