在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

错误:无法将预期类型[Int]与实际类型[Int] - > [Int]匹配

有谁知道如何解决这个问题？非常感谢任何见解,谢谢.

Answer 1

insert x insertionSort xs

呼吁insert有三个参数(x,insertionSort,xs).可能你想要的

insert x (insertionSort xs)

Answer 2

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

• 在任何情况下都避免使用非详尽的模式匹配: insertionSort [] = []
• 利用Ord固定类型的实例
• 通过将insert集成到where语句中来考虑lambda提升,以便摆脱高级函数并保存参数x
• 考虑守卫在如果当时别人

这将导致:

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