从列表中选择递增序列
我想问一下如何从Haskell的列表中选择元素的递增子序列。规则是在非空列表中选择第一个元素，然后选择比先前选择的元素大的每个元素。例如，在列表[3,1,8,4,6,7,9,2,11,4,3]
中将选择 sublist [3,8,9,11]。到目前为止，我的代码并没有完全涵盖这个问题：
incrSub :: Ord a => [a] -> [a]
incrSub [] = []
incrSub (x:xs) = if x < head xs then x: incrSub (xs) else incrSub (xs)
回答
考虑在提供的样本输入上评估您的函数：
incrSub [3, 1, 8, 4, 6, 7, 9, 2, 11, 4, 3]incrSub (3 : 1 : 8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])3 < 1 == False?incrSub (1 : 8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])1 < 8 == True?1 : incrSub (8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])8 < 4 == False?1 : incrSub (4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : [])4 < 6 == True?1 : 4 : incrSub (6 : 7 : 9 : 2 : 11 : 4 : 3 : [])6 < 7 == True?1 : 4 : 6 : incrSub (7 : 9 : 2 : 11 : 4 : 3 : [])7 < 9 == True?1 : 4 : 6 : 7 : incrSub (9 : 2 : 11 : 4 : 3 : [])9 < 2 == False?1 : 4 : 6 : 7 : incrSub (2 : 11 : 4 : 3 : [])2 < 11 == True?1 : 4 : 6 : 7 : 2 : incrSub (11 : 4 : 3 : [])11 < 4 == False?1 : 4 : 6 : 7 : 2 : incrSub (4 : 3 : [])4 < 3 == False?1 : 4 : 6 : 7 : 2 : incrSub (3 : [])3 < undefined == undefined?1 : 4 : 6 : 7 : 2 : undefined
注意实际结果和预期结果之间的关系：
input 3 : 1 : 8 : 4 : 6 : 7 : 9 : 2 : 11 : 4 : 3 : []
expected 3 : 8 : 9 : 11 : []
actual 1 : 4 : 6 : 7 : 2 : undefined
因此，这表明需要注意以下几点：
-
您的条件正在过滤与您想要的相反的内容。
-
您没有正确处理列表的末尾。特别是，考虑 1 元素列表的情况
incrSub [42]。 -
您的代码很容易出错，因为您使用的是
head，这是一个部分函数。首选模式匹配可能会有所帮助，特别是如果您启用警告（例如传递-Wall给 GHC 或添加{-# GHC_OPTIONS -Wall #-}到您的文件）。回想一下，您可以使用嵌套模式x1 : x2 : xs来匹配至少包含 2 个元素x1和x2.
使用等式推理来处理这样的示例是一种非常强大的 Haskell 代码调试技术。您还可以使用基于属性的测试库QuickCheck来识别失败的测试用例。例如，它可以快速识别单例列表的最小失败测试用例：
> import Test.QuickCheck (quickCheck)
> resultIsSorted :: [Int] -> Bool; resultIsSorted input = let { result = incrSub input } in result == sort result
> quickCheck resultIsSorted
*** Failed! Exception: 'Prelude.head: empty list' (after 2 tests and 2 shrinks):
[0]
您可以编写更复杂的属性来查找更有趣的边缘情况。