haskell - 如何将整数插入排序列表

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:ys 已经是一个列表，没有必要像[y:ys]那样再次包装它，- this具有类型 [[Int]]，即列表的列表。请注意，我们仍然必须在此处放置方括号，以告诉 Haskell 这是一个单函数参数:(y:ys)。

• 在您的“then”子句中，x:y:ys 已经是一个列表，- 不要将其包装到 [x:y:ys].

• 在您的“else”子句中，y insert x [ys] 是函数应用 - Haskell 认为y 是一个您应用于参数 insert、x 和 [ys] 的函数。你需要运算符 : 在这里，比如 y : insert ...

• 同样，在您的“else”子句中，您重复了第一个错误: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