CODEWITHSUNDEEP
ocamlnested-lists
user2352241
user2352241

Reputation: 81

nested lists in ocaml

I am new to Ocaml and have defined nested lists as follows:

    type 'a node = Empty | One of 'a | Many of 'a node list

Now I want to define a wrapping function that wraps square brackets around the first order members of a nested list. For ex. wrap( Many [ one a; Many[ c; d]; one b; one e;] ) returns Many [Many[one a; Empty]; Many[Many[c;d]; Empty]; Many[b; Empty]; Many[e; Empty]]. Here's my code for the same:

    let rec wrap list = function
         Empty -> []
        | Many[x; y] -> Many [ Many[x; Empty]; wrap y;];;

But I am getting an error in the last expression : This expression has the type 'a node but an expression was expected of the type 'b list. Please help.

Upvotes: 2

Views: 3053

Answers (1)

Charles Marsh
Charles Marsh

Reputation: 1917

Your two matches are not returning values of the same type. The first statement returns a b' list; the second statement returns an 'a node. To get past the type checker, you'll need to change the first statement to read as: Empty -> Empty.

A second issue (which you will run into next) is that your recursive call is not being fed a value of the correct type. wrap : 'a node -> 'a node, but y : 'a node list. One way to address this would be to replace the expression with wrap (Many y).

There will also be in issue in that your current function assumes the Many list only has two elements. I think what you want to do is Many (x::y). This matches x as the head of the list and y as the tail. However, you will then need a case to handle Many ([]) so as to avoid infinite recursion.

Finally, the overall form of your function strikes me as a bit unusual. I would replace function Empty -> ... with match list with | Empty -> ....

Upvotes: 2

Related Questions