如何將整數插入排序列表

Question

我試圖在正確的位置插入一個整數到排序的整數列表中。

insert :: Int -> [Int] -> [Int] 
insert x [] = [x] 
insert x [y:ys] = if x <= y 
        then [x:y:ys] 
        else y insert x [ys] 

有誰能告訴我這裏有什麼問題，以及如何解決它？下面是我所遇到的錯誤：

Answer 1

你是治療y的功能，而不是元素。您需要使用:構建一個新列表。此外，對於列表，您可以使用[...]或x:xs，而不是兩者。 [x,y]是語法糖x:y:[]。

insert x [] = x 
insert x (y:ys) = if x <= y 
        then x:y:ys 
        else y : insert x ys 

Answer 2

另一種解決方案，可能不是最有效的，但應該還是不錯的（W/O明確的遞歸和模式匹配的列表）：

insert :: Int -> [Int] -> [Int] 
insert x l = let (lower, greater) = span (< x) l in lower ++ x : greater 

而且這個解決方案也懶的，你可以看到：

λ: insert 3 [1,2,4] 
[1,2,3,4] 
λ: take 10 $ insert 5 $ repeat 1 
[1,1,1,1,1,1,1,1,1,1] 

Answer 3

這裏有幾個錯誤。

• 在參數列表，y:ys已經是一個列表，有再次包裝它像[y:ys]沒有必要， - 這有型[[Int]]，那就是，一個列表的列表。請注意，我們仍然需要在這裏放置括號，以告訴Haskell這是一個單一函數庫：(y:ys)。

• 在你的「then」子句中，x:y:ys又是一個列表， - 不要將它包裝到[x:y:ys]中。

• 在你的「別人」的條款，y insert x [ys]是功能應用 - 哈斯克爾認爲y是你所申請的論點insert，x和[ys]功能。您需要運營商:這裏，像y : insert ...

• 同樣，在「其他」條款，你重複的第一個錯誤：ys已經是一個列表，請不要把它包裝成[ys]。

所以，一個固定的解決辦法是：

insert :: Int -> [Int] -> [Int] 
insert x [] = [x] 
insert x (y:ys) = if x <= y 
        then x:y:ys 
        else y : insert x ys