Imperative pointer type data structures in OCAML

Question

I have a type of two-way pointer list. What I have to do is to write a procedure, that given a list, should return a list which contain only elements on the odd indexes. I'm new into OCaml, and its pointer type data structures, this is what i`ve written so far, but it doesnt work.

Error: This expression has type 'a elem option but an expression was expected of type 'b elem

type 'a elem = 
  {
    v : 'a;
    mutable next: 'a lista;
    mutable prev: 'a lista;
  }
and 'a lista = 'a elem option

exception NOT_FOUND

let x = ref None;;

let value e =
  match e with
  | Some x -> x.v
  | None -> raise NOT_FOUND;;

let generuj n x = 
  x := Some {v = 0; next = None; prev = None};
  for i = 1 to n do
    match !x with
    | None -> assert false
    | Some y ->
        let z = ref { v = i; next = None; prev = None } in
        y.next <- Some !z;
        !z.prev <- Some y;
        x := Some !z
  done

let second l x =
  let i = ref 0 in
  while !l <> None do
    let z = ref !x in
    if (!i mod 2 = 0) then
      x := {v = value !l; next = None; prev = Some !z}
    else ();
    let y = !l.next in
    l := {v = value y; next = y.next; prev = None};
    i := !i + 1
  done;;

Can anybody help me to understand why it doesnt work?

You have NOT_FOUND. Is that correct? Should it be Not_found? — G4143
I've posted full code, and the signatures. "Generuj" is not important — a_man_with_no_name

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2019-12-01T18:02:18

From the expression value !l you can conclude that l is of type 'a elem option ref. But in the expression !l.next you aren't handling l as an option type. You need to test whether !l is None or is Some ('a elem).

Note that you do compare l against None at the beginning of the function.

Also note that the next line has the same type error. You need to set l to Some ....

Imperative pointer type data structures in OCAML

1 Answers