Ocaml插入排序

Question

輸入：未排序列表/輸出：排序列表

我的基本想法是在排序列表中插入一個整數。

（I可以對列表進行排序，如果我能插入所述第一元件到排序尾巴。）

我使用的「插入」，這是thehelper功能。

但是，它會溢出。有人告訴我問題是什麼？

let rec sort (l: int list) : int list = 
    match l with 
     []->[] 
     | x::[]->[x] 
     | x1::x2::xs->let rec insert (n,dest) = 
          match dest with 
           []->[n] 
           | y::[]-> if n<y then [n;y] else [y;n] 
           | y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs) 
        in insert(x1,sort(x2::xs)) ;; 

Answer 1

這行看起來相當錯誤的對我說：

| y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs) 

在我看來，你知道你的ys排序（由歸納假設）。所以你應該比較n與你的ys，而不是你的ys對方。如果你弄清了這條線，事情可能會改善。

對於它的價值，我懷疑你只需要在你的match有兩個案例。我不明白你爲什麼需要將1元素列表與其他非空列表區分開來。

Answer 2

再有，我有風情的建議：

• 你應該分開兩個功能sort和insert因爲這將使其更具可讀性，還因爲insert功能本身也可能是有用的。
• 爲什麼你給一個元組作爲insert函數的參數？在OCaml中，人們會使用咖喱並編寫insert x l而不是insert(x,l)。這將允許您執行部分應用程序。
• 爲什麼要限制您的功能類型爲int list -> int list。 OCaml中的函數可以是多態的，所以你的函數應該有更通用的類型'a ist -> 'a list。

這裏是你與所有這些修正獲得代碼：

let rec insert x l = 
    match l with 
    | [] -> [x] 
    | y::ys -> if x < y then x::y::ys else y::insert x ys 

let rec sort l = 
    match l with 
    | [] -> [] 
    | x::xs -> insert x (sort xs) 

Answer 3

總是問這樣的問題時，很難對人們閱讀這樣的代碼和他們大多會忽略的職位。 就像@Thomash說的，首先嚐試分成更小的函數，這樣可以更容易地看出它失敗的位置。

你可以在 「調試你的眼睛」 這樣的：

let rec insertion_sort el = function 
    | [] -> [el] 
    | h::t as ls -> if el > h then h :: insert el t else (el :: ls) 

let sorted_list ls = List.fold_right insertion_sort ls []