OCaml在模式匹配中的奇怪行爲

Question

我想在OCaml中實現一個隊列結構，現在正在編寫一個測試值是否在隊列中的函數。我原本寫了一個正確的 - 或者至少我認爲這是一個正確的 - 實現的功能。但是當我測試它時，我會得到意想不到的測試失敗。也就是說，當隊列是空的時候它會返回false（一件好事），但在其他情況下也會返回false，無論隊列是否爲空，以及隊列是否包含該值。所以我用這種愚蠢的方式重新編寫了這個函數（其中Some h -> true），以試圖找出問題所在。即使有這個愚蠢的函數，當我傳遞任何隊列和任何值時它仍然返回錯誤，所以很明顯，它將每個隊列的頭部讀取爲None，不管它是否爲None。

包含：

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 

測試

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 

寫到這裏已經過測試，並獲得預期的其他職能。隊列類型的類型聲明是

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

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

，爲什麼它走的每q.head爲None，將不勝感激的任何想法。

---

from_list

通過車削每個值成qnode並將其鏈接到下一個，並返回所生成的列表的列表行走輔助函數。

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 

創建qnodes列表，找到它的第一個和最後一個元素，並將它們分配爲隊列的頭部和尾部。

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 

---

這裏是我本來的功能，包含之前我試圖簡化它縮小的奇怪行爲。

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 

Answer 1

當我嘗試你的代碼它不表現爲你描述：

# 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 

所以，我想說的答案取決於什麼from_list實際上返回。

作爲一方的意見，您的定義contains有elt，這是我沒有定義的任何地方，我可以看到。

更新

你的新代碼沒有定義create。我提供的這個定義爲create：

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

如果我運行from_list [1;2]，這是我所看到的：

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

這可以解釋爲什麼頭部似乎是None :-)