需要根据元素升序将列表划分为列表（Haskell）

假设我有这样的列表：

[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]]

有什么建议么？

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

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

第一步是观察我们想要根据同时查看列表中两个元素的标准来拆分列表。因此，我们需要一个新列表，其中的元素代表“上一个”和“下一个”值。有一个非常标准的技巧：

previousAndNext xs = zip xs (drop 1 xs)

然而，就我们的目的而言，这不太有效：这个函数总是输出一个比输入短的列表，并且我们总是想要一个与输入长度相同的列表（特别是我们想要一些输出，即使当输入是长度为 1 的列表）。因此，我们将使用“空终止符”稍微修改一下标准技巧。

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]]

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