Haskell 中的插入排序

Question

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

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

现在我需要使用插入来定义一个函数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

insert x insertionSort xs

正在使用三个参数调用 insert (x、insertionSort、xs)。也许你想要

insert x (insertionSort xs)

Answer 2

在自己学习一些排序算法的同时，我想给你一些suggestions/improvements解决方案：

在任何情况下都避免非穷尽模式匹配：insertionSort [] = []
利用 Ord 的实例而不是固定类型
考虑 lambda 提升，将插入整合到 where 语句中，以摆脱高级函数并保存参数 x
考虑 guards 而不是 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

Haskell 中的插入排序

Insertion sort in Haskell

haskell

functional-programming