根据谓词对 haskell 中的列表进行排序

Question

我正在努力学习 Haskell，但在尝试完成示例问题时遇到了问题。问题是根据给定的谓词对 Haskell 中的列表进行排序，即类型为

sort :: (a -> a -> Bool) -> [a] -> [a]

我目前的代码是：

sort _ [] = []
sort f (x:xs) =
            let 
            smaller = sort f (filter (f x) xs)
            bigger = sort f (filter (f x) xs) --error is on this line 
            in smaller ++ [x] ++ bigger

从某种意义上说，代码无法正常工作，我不确定如何取相反的函数。例如，如果它是一个普通的排序函数，我会使用 smaller = quicksort (filter (<=x) xs) 和 bigger = quicksort (filter (>x) xs) 这将根据该谓词分解列表，但是我如何使用更高阶的谓词来做到这一点？

Answer 1

您只需要使用 not 函数来反转您的布尔值：

not :: Bool -> Bool

f :: a -> a -> Bool
f x :: a -> Bool

not . f x :: a -> Bool

你会把它用作

sort _ [] = []
sort f (x:xs) =
    let smaller = sort f (filter (f x) xs)
        bigger  = sort f (filter (not . f x) xs)
    in smaller ++ [x] ++ bigger

根据谓词对 haskell 中的列表进行排序

Sort a list in haskell according to a predicate

sorting

haskell