首页 文章

在Haskell中插入排序

提问于
浏览 次
2

我在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]匹配

有谁知道我怎么解决这个问题？任何见解都非常感谢，谢谢 .

haskell functional-programming

2 回答

  • 8
    insert x insertionSort xs

    用三个参数调用 insert （ x ， insertionSort ， xs ） . 可能你想要的

    insert x (insertionSort xs)
    回复于
  • 7

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

    • 在任何情况下都避免非穷举模式匹配： 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
    回复于

相关问题