OCaml converting functional arrays as binary tree to list-CodePudding

I have to convert a functional array to a list on OCaml and this is what I have so far but it isn't passing the tests, can anyone help with what's wrong with my code and what method I should use instead?

I first wrote a function to return the tree except for the first value, then take the heads and cons it to the heads of the rest to create a list. Have I made a mistake?

exception Subscript

let top = function
  | Lf -> raise Subscript
  | Br (v,_,_) -> v

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

let rec listofarray = function
  | Br (v, t1, t2) -> v :: (listofarray (pop (Br(v, t1, t2))))
  | Lf -> []

CodePudding user response：

You don't say whether the trees have extra invariants. Unless there are limits on the possible trees, your pop function doesn't work for all of them:

# pop (Br (0, Br (1, Lf, Lf), Lf));;
- : tree = Br (1, Lf, Lf)
# pop (Br (0, Lf, Br (1, Lf, Lf)));;
Exception: Subscript.

CodePudding user response：

As Jeffrey Scofield has suggested, you may wish to modify your implementation of pop to handle situations where the left tree or right tee are Lf but not both.

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, Lf, rt) -> ...
  | Br (_, lt, Lf) -> ...
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

Now the question is what pop should do in each of those cases. Consider the first scenario.

   0
  / \
 /   \
Lf    1
     / \
    /   \
   Lf   Lf

It seems fairly obvious that after pop we should have:

   1
  / \
 /   \
Lf   Lf

We can get this by simply returning the right tree.

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, Lf, rt) -> rt
  | Br (_, lt, Lf) -> ...
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

Likewise, if we consider the other scenario, we can see that the solution will be just as simple.

         0              1
        / \            / \ 
       /   \          /   \
      1    Lf   ->   Lf   Lf
     / \
    /   \
   Lf   Lf

We can implement this by just returning the left tree.

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, Lf, rt) -> rt
  | Br (_, lt, Lf) -> lt
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

Now, without changing listofarray we do get a correct result when evaluating the example Jeffrey Scofield provided.

utop # listofarray (Br (0, Lf, Br (1, Lf, Lf)));;
- : int list = [0; 1]
utop # listofarray (Br (0, Br (1, Lf, Lf), Lf));;
- : int list = [0; 1]