我在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]匹配
有谁知道如何解决这个问题?非常感谢任何见解,谢谢。
insert x insertionSort xs
用三个参数调用insert
(x
,insertionSort
,xs
)。可能你想要的
insert x (insertionSort xs)
在自己学习一些排序算法的同时,我想为您的解决方案提供一些建议/改进:
insertionSort [] = []
Ord
实例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