需要根据元素的升序(Haskell)将列表分区为列表

Question

说我有这样的列表:

[4,5,6,7,1,2,3,4,5,6,1,2]

我需要一个Haskell函数,它将此列表转换为列表列表,列表由原始列表的段组成,这些段按升序排列.所以结果应该是这样的:

[[4,5,6,7],[1,2,3,4,5,6],[1,2]]

有什么建议？

Answer 1

你可以通过手动递归来做到这一点,但我喜欢相信Haskell是一种更加进化的语言.让我们看看我们是否可以开发一个使用现有递归策略的解决方案.首先是一些预赛.

{-# LANGUAGE NoMonomorphismRestriction #-}
-- because who wants to write type signatures, amirite?
import Data.List.Split -- from package split on Hackage

第一步是观察我们想要根据一次查看列表的两个元素的标准来拆分列表.所以我们需要一个新的列表,其中的元素代表"previous"和"next"值.这有一个非常标准的技巧:

previousAndNext xs = zip xs (drop 1 xs)

但是,对于我们的目的,这不会很有效:这个函数总是输出一个比输入短的列表,我们总是想要一个与输入长度相同的列表(特别是我们想要一些输出,即使是输入是长度列表一).所以我们将使用"null终止符"稍微修改标准技巧.

pan xs = zip xs (map Just (drop 1 xs) ++ [Nothing])

现在我们将通过此列表查看前一个元素大于下一个元素(或下一个元素不存在)的位置.让我们编写一个执行该检查的谓词.

bigger (x, y) = maybe False (x >) y

现在让我们编写实际执行拆分的功能.我们的"分界符号"将是满足的价值bigger; 我们永远不想扔掉它们,所以让我们保留它们.

ascendingTuples = split . keepDelimsR $ whenElt bigger

最后一步就是将构造元组的位,分裂元组的位以及最后一点重新组合起来扔掉我们不关心的元组的位:

ascending = map (map fst) . ascendingTuples . pan

让我们在ghci中尝试一下:

*Main> ascending [4,5,6,7,1,2,3,4,5,6,1,2]
[[4,5,6,7],[1,2,3,4,5,6],[1,2]]
*Main> ascending [7,6..1]
[[7],[6],[5],[4],[3],[2],[1]]
*Main> ascending []
[[]]
*Main> ascending [1]
[[1]]

PS在当前版本中split,keepDelimsR比它需要的稍微严格一些,因此ascending目前不适用于无限列表.不过,我已经提交了一个补丁,让它变得更加懒散.

Answer 2

ascend :: Ord a => [a] -> [[a]]
ascend xs = foldr f [] xs
  where
    f a []  = [[a]]
    f a xs'@(y:ys) | a < head y = (a:y):ys
                   | otherwise = [a]:xs'

在ghci

*Main> ascend [4,5,6,7,1,2,3,4,5,6,1,2]
[[4,5,6,7],[1,2,3,4,5,6],[1,2]]