OCaml, lazy list into lazy tree

Question

I have two types:

type 'a llist = 
      LNil 
    | LCons of 'a * (unit -> 'a llist);;

type 'a lBT = 
      LEmpty 
    | LNode of 'a * (unit -> 'a lBT) * (unit -> 'a lBT);;

I need to write function that gets lazy list and returns lazy BST. I currently have two functions, first (add, which gets element and a tree and returns a tree with this element) seems ok, but with the second one (which iterates through list and creates a new tree adding all the elements from list) I get error. For me it looks ok, but I probably just don't understand something. And I have no idea what.

let rec add (elem, tree) = 
    match (elem, tree) with
      (None, _) -> LEmpty
        | (x, LEmpty) -> LNode (x, (function() -> add (None, LEmpty)), (function() -> add (None, LEmpty)))
        | (x, LNode (y, l, r)) when x < y -> LNode(y, (function () -> add (x, l())), r)
        | (x, LNode (y, l, r)) -> LNode(y, l, (function () -> add (x, r())));;

let toLBST listal = 
    let rec toLBST_rec listal tree =
        match listal with
          LNil -> tree
            | LCons(x, xs) -> toLBST_rec (xs()) add(x, tree)
    in toLBST_rec (listal, LEmpty);;

I get:

Characters 141-145:
    | LCons(x, xs) -> toLBST_rec (xs()) add(x, tree)
                                               ^^^^
Error: This expression has type 'a option * 'a option lBT -> 'a option lBT
    but an expression was expected of type 'a option lBT

I have no idea what should I do, for it to work properly. I tried a few things but every time I get some error.

in add, instead of (None, _) -> LEmpty it should be (Nil, _) -> tree. -- as gasche said, either have a definition with pair, let rec fun (a,b) = ... in fun (x,y) or with two arguments, let rec fun a b = ... in fun (x) (y), but the call and the definition should be consistent. — Will Ness

gasche gasche · Accepted Answer · 2014-01-25T12:34:53

Here are the various mistakes you made in your code:

  (None, _) -> LEmpty

This is wrong, there is no reason for elem to be an option type. In the LEmpty case, simply use LEmpty to define the children of the lazy tree returned.

        | LCons(x, xs) -> toLBST_rec (xs()) add(x, tree)

You forgot parentheses around add(x, tree).

in toLBST_rec (listal, LEmpty);;

You defined toLBST_rec to take two parameters, now you're passing it only one, of the wrong type (a pair of a list and a tree ,while the parameter expects only a list). You seem to be confused about the syntax of multi-parameter (currified) functions in OCaml. You should avoid (.. , ..) in function declarations and calls, and define instead let rec add elem tree =, etc.

OCaml, lazy list into lazy tree

1 Answers