测试列表是否已排序

Question

在haskell中找到最少的列表真的很容易:

foldl1 (min) [9,5,7,3,7,4,6,10]给了我3.;)

我换成min与<=测试如果列表进行排序:

foldl1 (<=) [9,5,7,3,7,4,6,10]

我收到此错误消息:

No instance for (Num Bool) arising from the literal `9'
Possible fix: add an instance declaration for (Num Bool)
In the expression: 9
In the second argument of `foldl1', namely `[9, 5, 7, 3, ....]'
In the expression: foldl1 (<=) [9, 5, 7, 3, ....]

有没有办法解决这个错误？

Answer 1

是.从我们的基础案例开始

isSorted [] = True -- An empty list is sorted

现在为非空案例

isSorted (x:xs) = fst $ foldl' step (True, x) xs
  where step (b, x) y = (b && (x <= y), y)

基本上我们在元组的第一个参数和第二个元素中跟踪排序状态,然后我们更新排序状态和每个步骤的值.

虽然这不是懒惰,也不适用于无限列表,而是尝试

 import Control.Applicative

allSorted :: Ord a => [a] -> Bool
allSorted = all (uncurry (<=)) . (zip <$> id <*> tail)
allSorted = all (uncurry (<=)) . (zip <*> tail)
allSorted = and . (zipWith (<=) <*> tail)