list - 需要根据元素升序的中断将列表划分为列表(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

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

previousAndNext xs = zip xs (drop 1 xs)

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

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目前不适用于无限列表。不过，我已经提交了一个让它变得更懒的补丁。