OCaml strange behavior in pattern matching

Question

I am trying to implement a queue structure in OCaml, and now writing a function that tests whether a value is in the queue. I originally wrote a correct--or at least I think it was a correct--implementation of the function. But when I tested it, I would get unexpected test failures. Namely, it would return false when the queue was empty (a good thing) but would also return false in every other cases, whether the queue was empty or not, and whether the queue contained the value or not. So I re-wrote the function in this kind of dumb way (where Some h -> true) in order to try to figure out what the problem is. Even with this dumb function, it's still returning false when I pass it any queue and any value, so clearly it's reading the head of every queue as a None, whether it is a None or not.

Contains:

let contains (v: 'a) (q: 'a queue) : bool =
    if not (valid q) then failwith "contains: given invalid queue";
    let rec loop (value: 'a) (qn: 'a qnode option) : bool =
      begin match qn with
      | None -> false
      | Some h -> true
      end
    in loop elt q.head

Tests

   let test () : bool =
    let q = create () in
    not (contains 1 q)
  ;; run_test "contains empty" test

  let test () : bool =
    let q = from_list [2; 3] in
    contains 3 q
  ;; run_test "contains non-empty true" test

  let test () : bool =
    let q = from_list [2; 3] in
    not (contains 4 q)
  ;; run_test "contains non-empty false" test

The other functions written here have been tested and come out as expected. The type declaration for the queue type is

  type 'a qnode = { v: 'a;
                    mutable next: 'a qnode option }

  type 'a queue = { mutable head: 'a qnode option;
                     mutable tail: 'a qnode option }

Any thoughts about why it's taking every q.head to be None would be appreciated.

from_list

A helper function that walks through a list turning each value into a qnode and linking it to the next, returning the resulting list.

  let rec vals_to_qnodes (l: 'a list) : 'a qnode list =
    begin match l with
    | [] -> []
    | [h] -> [{v = h; next = None}]
    | h1::h2::t -> let sofar = vals_to_qnodes (h2::t) in
                    begin match sofar with
                    | [] -> []
                    | x::y -> {v = h1; next = Some x}::x::y
                    end
    end

Make the list of qnodes, find its first and last elements, and assign them as the head and tail of the queue.

  let from_list (l: 'a list) : 'a queue =
    let qsList = vals_to_qnodes l in
    begin match qsList with
    | [] -> create ()
    | h::t -> begin match t with
              | [] -> {head = Some h; tail = Some h}
              | h2::t2 -> let x = List.rev t2 in
                          begin match x with
                          | [] -> {head = None; tail = None;}
                          | h3::t3 -> {head = Some h; tail = Some h3}
                          end
              end
    end

Here's what I originally had for the contains function before I tried to simplify it to narrow in on the strange behavior.

let contains (v: 'a) (q: 'a queue) : bool = 
  if not (valid q) then failwith "contains: given invalid queue";
  let rec loop (value: 'a) (qn: 'a qnode option) : bool = 
    begin match qn with 
    | None -> false
    | Some h -> if v == value then true 
                else loop value h.next
    end
  in loop v q.head

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2017-10-10T16:26:05

When I try your code it doesn't behave as you describe:

# let n = { v = 1; next = None };;
val n : int qnode = {v = 1; next = None}
# let q = { head = Some n; tail = Some n };;
val q : int queue =
  {head = Some {v = 1; next = None}; tail = Some {v = 1; next = None}}
# contains 3 q;;
- : bool = true

So, I'd say the answer depends on what from_list is actually returning.

As a side comment, your definition of contains has a reference to elt, which isn't defined anywhere that I can see.

Update

Your new code doesn't define create. I supplied this definition for create:

let create () = { head = None; tail = None }

If I run from_list [1;2], this is what I see:

# from_list [1;2];;
- : int queue = {head = None; tail = None}

This would explain why the head appears to be None :-)

OCaml strange behavior in pattern matching

1 Answers