Ocaml的遞歸

Question

我是Ocaml的新手，我試圖編寫一個遞歸函數。

功能採取對的列表，並返回一個對列表，例如

[(1, 4); (2, 3); (5, 9); (6, 10)]) -> ([1; 2; 5; 6], [4; 3; 9; 10]) 

但是編譯器說：Error: This expression has type 'a list * 'b list but an expression was expected of type 'a list

在該行

(unzip (List.tl m))

有人能解釋爲什麼我有這個錯誤嗎？無論如何要解決這個問題嗎？非常感謝你！

let rec unzip m = 
    if List.length m = 0 then 
     ([], []) 
    else 
     ((fst (List.hd m)) :: (unzip (List.tl m)), (snd (List.hd m)) :: (unzip (List.tl m))) 
in 
    unzip m;; 

Answer 1

對於任何遞歸，您必須注意輸出類型將始終相同。

讓我們來看看你的unzip函數。

[(1, 4); (2, 3); (5, 9); (6, 10)]) -> ([1; 2; 5; 6], [4; 3; 9; 10])

簡單的說，的unzip返回類型是DEF 一對（元組），每個元素是一個列表，正確？

---

那麼讓我們來看看你的代碼

let rec unzip m = 
    if List.length m = 0 then 
     ([], []) 
    else 
     ((fst (List.hd m)) :: (unzip (List.tl m)), (snd (List.hd m)) :: (unzip (List.tl m))) 
in 
    unzip m;; 

你有兩個分支。第一個分支返回([], [])。好的，就返回類型而言，它是正確的，因爲它是一對具有兩個空列表並匹配上述返回類型的對。

---

第二分支

((fst (List.hd m)) :: (unzip (List.tl m)), (snd (List.hd m)) :: (unzip (List.tl m)))

是正確的嗎？

這是一個有兩個元素，沒有問題的一對，那麼讓我們來看看第一個元素：

(fst (List.hd m)) :: (unzip (List.tl m))

您嘗試添加(fst (List.hd m))到(unzip (List.tl m))頭。

但是，你只能使用::添加一些東西到一個列表，所以ocaml假設(unzip (List.tl m))是一個列表，對不對？

但是它是一個unzip函數應用程序，在開始時顯然描述過，您的unzip不是返回一個列表，而是一對（元組）。

因此ocaml不理解，因此抱怨。

---

以上只是爲了回答有關類型問題的問題。但是你的代碼有更多的問題。

1.不正確使用的in

假設你有一個函數f1。您可以將其作爲母函數進行映像，這意味着它可以直接使用。同樣在f1中，您可以聲明另一個函數或變量（或更正式地說是一個綁定）。只有當你在一個函數中聲明一個綁定時，你才使用let...in...。如果您只有母親功能，您不使用in，因爲in where？

在你的unzip中，你只有一個函數或綁定，它本身是unzip，它在頂層。所以in是沒有必要的。

2.遞歸

的不正確的邏輯，我不知道該如何向你解釋這裏約遞歸，因爲它需要你閱讀越來越多練習。

但你的想法正確的代碼是

let rec unzip = function 
    | [] -> ([], []) 
    | (x,y)::tl -> 
    let l1, l2 = unzip tl in 
    x::l1, y::l2 

如果你追逐更好或尾遞歸版本，那就是：

let unzip l = 
    let rec unzip_aux (l1,l2) = function 
    | [] -> List.rev l1, List.rev l2 
    | (x,y)::tl -> unzip_aux (x::l1, y::l2) tl 
    in 
    unzip_aux ([],[]) l 

Answer 2

這個錯誤來自一個事實，即(unzip ...)返回兩個列表（'a list * 'b list），你試圖當你寫(fst ..) :: (unzip ...)操作的列表。

如果您使用模式匹配，這將全部寫得更好。骷髏：

let rec unzip = function 
    | [] -> ... 
    | (x,y) :: rest -> 
    let (xs, ys) = unzip rest in ...