haskell - Haskell 中的插入排序

Question

我正在做一些 Haskell 练习。首先，我被要求定义一个函数 insert::Int -> [Int] -> [Int] 以便 insert x xs 将 x 插入列表 xs 中，使得 x 大于那些 它前面的元素并且小于或等于它之前的元素 关注它:

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

现在我需要使用insert来定义一个函数insertionSort::[Int] -> [Int]。这是我的尝试:

insertionSort :: [Int] -> [Int]
insertionSort [x] = [x]
insertionSort (x:xs) = insert x insertionSort xs

Error: Couldn't match expected type [Int] with actual type [Int] -> [Int]

有人知道我该如何解决这个问题吗？任何见解都将受到高度赞赏，谢谢。

Answer 1

在自己学习一些排序算法时，我想为您的解决方案提供一些建议/改进:

• 在任何情况下都避免非详尽的模式匹配:insertionSort [] = []
• 利用固定类型的 Ord 实例
• 考虑通过将 insert 集成到 where 语句中来进行 lambda 提升，以摆脱高级函数并保存参数 x
• 考虑守卫而不是if then else

这将导致:

insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort [x] = [x]
insertionSort (x:xs) = insert $ insertionSort xs
    where insert [] = [x]
          insert (y:ys)
              | x < y = x : y : ys
              | otherwise = y : insert ys