我想擅长函数式编程,所以我给自己设定了一些任务。
我想确定整数列表中最长子序列的长度,其中下一个元素递增1。
所以结果应该是
incsubseq [] ~?= 0,
incsubseq [5] ~?= 1,
incsubseq [1,2,3,5,6] ~?= 3,
incsubseq [5,6,1,2,3] ~?= 3,
incsubseq [5,6,1,4,3] ~?= 2,
incsubseq [6,5,4,3,2,1] ~?= 1]
我的尝试是这样的:
incsubseq :: [Int] -> Int
incsubseq [] = 0
incsubseq [_] = 1
incsubseq (a:b)
| a == ((head b)-1) = 1 + (incsubseq b)
| a /= ((head b)-1) = (incsubseq b)
当然,这只适用于没有更长子序列的列表,例如[1,2,3,42] = 3,但不适用于 [1,2,100,101,102] 这样的列表,它应该是 3 但是 NOT(是 2)!
我真的非常感谢您的帮助,因为这个问题让我抓狂,来自 OO-Programming。
最佳答案
您同时解决了太多问题 - 我会尝试以更易于理解的步骤分解问题
- 创建列表中的所有序列
- 使用
map
创建一个包含他们的length
的新列表 - 找到长度的
最大值
现在第一部分会很简单,如果你的序列是“所有相同的东西”那么 Data.List
中的 group
就足够了,但这不是情况下,不幸的是 groupBy (\x y -> x + 1 == y)
这正是您正在寻找的 - 不起作用(出于技术原因我不想扩展)。
所以首先你需要实现你自己的groupBy'
函数或者“作弊”然后看here我在哪里
groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy rel [] = [] groupBy rel (x:xs) = (x:ys) : groupBy rel zs where (ys,zs) = groupByAux x xs groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs) where (ys,zs) = groupByAux x xs groupByAux y xs = ([], xs)
然后你可以简单地 groupBy (\x y -> x + 1 == y) [1,2,100,101,102]
接下来的步骤应该是可管理的。
注意:如果你想要最长的序列,你可以创建一个快捷方式并使用maximumBy(比较`on`长度)
。
完整解决方案:
import Data.Function (on) import Data.List (maximum) longestLength :: [Int] -> Int longestLength xx = maximum $ map length $ groupBy' (\x y -> x + 1 == y) xx groupBy = ... -- see above
关于list - 整数列表中最长子序列的长度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36959704/