给定如下列表:
[1, 2, 2, 6, 7, 8, 10, 11, 12, 15]
将其拆分为平淡增加的范围(可能相等(:
[[1, 2, 2], [6, 7, 8], [10, 11, 12], [15]]
我尝试使用递归方法:
splitRanges [] = [[]]
splitRanges (x:y:xs)
| x `elem` [y, y + 1] = [x, y] : splitRanges xs
| otherwise = xs
因此,如果我融合它们后该物品比该物品少或等于一个。但它说我正在尝试构建一个无限类型:
Occurs check: cannot construct the infinite type: a0 = [a0]
Expected type: [[a0]]
Actual type: [a0]
但是[单调的事实]与列表的拆分方式有什么关系?
严格增加会产生不同的结果。
还是你真的想说别的?
我希望我不是。
列表将始终是单调的吗?
不,拆分单调列表意味着将其分成一个子列表。
如果不是,这将如何影响结果?
如果它不是单调的,您将有许多子列表。
它总是棕色成三人一组吗?
否,这些组可能包含 n 个元素。
更多的例子会很好
splitRanges [1, 3] == [[1], [3]]
splitRanges [1, 2, 5] == [[1, 2], [3]]
splitRanges [0, 0, 1] == [[0, 0, 1]]
splitRanges [1, 5, 7, 9] == [[1], [5], [7], [9]]
我欣赏提示而不是完整的答案,因为我想提高自己,复制粘贴不是改进。
尝试将问题分解为更易于管理的部分。
首先,您如何从列表的开头拆分一个平淡增加的范围?让我们猜测应该是splitOne :: [Integer] -> ([Integer], [Integer])
.
其次,如何重复将splitOne应用于剩余列表?尝试使用 splitOne 实现splitMany :: [Integer] -> [[Integer]]
。
对于分裂一,你应该尝试找到什么?要拆分的第一个位置。什么是"平仓"?让我们弥补一下。
split 0 1 2 3 4 …
list [ | x1, | x2, | x3, | x4, | x5, …]
所以在 0 处分裂是([], [x1,x2,x3,x4,x5,…])
,而在 3 处分裂是([x1,x2,x3],[x4,x5,…])
。您可以看到拆分位置和拆分列表之间的关系是什么?
您如何确定列表的第一个拆分位置?假设这是按firstSplitPos :: [Integer] -> Integer
实现的。空列表的第一个拆分位置是什么?
您现在可以使用 firstSplitPos 实现 splitOne 吗?
一个可能的答案
-- What are the adjacencies for:
-- 1) empty lists?
-- 2) lists with one element?
-- 3) lists with more than one element?
--
-- Bonus: rewrite in point-free form using <*>
--
adjacencies :: [a] -> [(a,a)]
adjacencies xxs = zip xxs (drop 1 xxs)
-- Bonus: rewrite in point-free form
--
withIndices :: [a] -> [(Int,a)]
withIndices xxs = zip [0..] xxs
-- This is the most involved part of the answer. Pay close
-- attention to:
-- 1) empty lists
-- 2) lists with one element
-- 3) lists which are a blandly increasing sequence
--
firstSplitPos :: (Eq a, Num a) => [a] -> Int
firstSplitPos xxs = maybe (length xxs) pos (find q searchList)
where q (_,(a,b)) = a /= b && a + 1 /= b
searchList = withIndices (adjacencies xxs)
-- Why is the split position one more than the index?
pos (i,_) = i + 1
--
-- Bonus: rewrite in point-free form using <*>
--
splitOne :: (Eq a, Num a) => [a] -> ([a],[a])
splitOne xxs = splitAt (firstSplitPos xxs) xxs
splitMany :: (Eq a, Num a) => [a] -> [[a]]
-- What happens if we remove the case for []?
splitMany [] = []
splitMany xxs = let (l, r) = splitOne xxs in l : splitMany r
另一种方法
这是我对卡斯滕解决方案的解释。它已经很简洁了,但我选择了不使用 2 元组的变体。
我们知道Haskell列表是归纳定义的。为了证明这一点,我们可以定义一个等效的数据类型。
data List a = Cons a (List a) -- Cons = (:)
| Nil -- Nil = []
然后问一个问题:我们可以在列表上使用归纳来解吗?如果是这样,我们只需要解决两种情况:缺点和零。foldr
的类型签名向我们展示了这一点:
foldr :: (a -> b -> b) -- Cons case
-> b -- Nil case
-> [a] -- The list
-> b -- The result
如果列表为零怎么办?那么唯一平淡增加的序列是空序列。因此:
nilCase = [[]]
我们可能想要nilCase = []
,因为这似乎也很合理——即没有平淡增加的序列。
现在你需要一些想象力。在缺点的情况下,我们一次只能查看一个新元素。有了这个新元素,我们可以决定它是否属于右邻序列,或者它是否开始一个新序列。
我所说的右邻是什么意思?在[5,4,1,2,2,7]
中,1
属于右邻序列[2,2]
。
这是什么样子?
-- The rest of the list is empty
consCase new [] = [new] : []
-- The right-adjacent sequence is empty
consCase new ([]:ss) = [new] : ss
-- The right-adjacent sequence is non-empty
-- Why `new + 1 == x` and not `new == x + 1`?
consCase new sss@(xxs@(x:_):ss)
| new == x || new + 1 == x = (new:xxs):ss
| otherwise = [new]:sss
现在我们解决了 Nil 案例和 Cons 案例,我们完成了!
splitRanges = foldr consCase nilCase
编写函数以采用谓词而不是将拆分条件写入函数本身将是有用且惯用的:
splitBy2 :: (a -> a -> Bool) -> [a] -> [[a]]
splitBy2 ok xs = snd $ f xs [] []
where f (a:b:xs) acc_list acc_out_lists | ok a b = ...
我希望你不介意破坏它的一部分,但是由于评论正在讨论你想要什么(我希望我已经得到了它(,也许你对另一个可能的解决方案感兴趣?
我不想破坏这一切,但我认为你可以很容易地解决这个问题:
blandly :: (Ord a, Num a) => [a] -> [[a]]
blandly = g . foldr f ([],[])
where f x ([],xss) = ([x],xss)
f x (y:ys,xss)
| abs (x-y) <= 1 = undefined
| otherwise = undefined
g (ys,xss) = undefined
你只需要填补undefined
孔
这个想法只是从右边折叠列表,在元组的第一项中积累你的内部列表,只要元素不远;如果是:将其推到第二项。
如果操作正确,它将产生:
λ> blandly [1,3]
[[1],[3]]
λ> blandly [1,2,5]
[[1,2],[5]]
λ> blandly [0,0,1]
[[0,0,1]]
λ> blandly [1,5,7,9]
[[1],[5],[7],[9]]
这似乎是你想要的
1 小时后 - 我想我可以发布我的解决方案 - 如果您不想被宠坏,请停止阅读
blandly :: (Ord a, Num a) => [a] -> [[a]]
blandly = uncurry (:) . foldr f ([],[])
where f x ([],xs) = ([x],xs)
f x (y:ys,xs)
| abs (x-y) <= 1 = (x:y:ys,xs)
| otherwise = ([x],(y:ys):xs)
也许我在这里有一个轻微的误解(示例没有指定( - 但如果你只想单调增加内部列表,你只需要更改abs
部分:
blandly :: (Ord a, Num a) => [a] -> [[a]]
blandly = uncurry (:) . foldr f ([],[])
where f x ([],xss) = ([x],xss)
f x (y:ys,xss)
| 0 <= y-x
&& y-x <= 1 = (x:y:ys,xss)
| otherwise = ([x],(y:ys):xss)