2

假设我有这样的列表：

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

有什么建议么？

4

5 回答 5

8

你可以通过手动递归来做到这一点，但我更愿意相信 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]]

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

于 2013-01-18T21:27:55.917 回答
6 
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]]
于 2013-01-18T16:37:16.950 回答
4

这个问题非常适合基于paramorphism的解决方案。拥有（如该帖子中所定义）

para  :: (a -> [a] -> b -> b) -> b -> [a] -> b
foldr :: (a ->        b -> b) -> b -> [a] -> b

para  c n (x : xs)  =  c x xs (para  c n xs)
foldr c n (x : xs)  =  c x    (foldr c n xs)
para  c n []        =  n
foldr c n []        =  n

我们可以写

partition_asc xs  =  para c [] xs  where
  c x (y:_) ~(a:b) | x<y  =  (x:a):b 
  c x  _      r           =  [x]:r

微不足道，因为抽象适合。

顺便说一句，它们在 Common Lisp 中有两种类型mapmapcar- （一个一个地处理输入列表的元素）和maplist（处理列表的“尾部”）。有了这个想法，我们得到

import Data.List (tails)

partition_asc2 xs  =  foldr c [] . init . tails $ xs  where
  c (x:y:_) ~(a:b) | x<y  =  (x:a):b
  c (x:_)     r           =  [x]:r

两个版本中的惰性模式使其以高效的方式处理无限输入列表（如Daniel Fischer的回答中首次显示）。

2020-05-08 更新：毕竟不是那么微不足道。两者都head . head . partition_asc $ [4] ++ undefined和partition_asc2失败相同*** Exception: Prelude.undefined。组合功能过早地g强制下一个元素。y在查看下一个元素之前，需要更加仔细地编写它以立即高效，例如对于第二个版本，

partition_asc2' xs  =  foldr c [] . init . tails $ xs  where
  c (x:ys) r@(~(a:b))  =  (x:g):gs
         where
         (g,gs) | not (null ys) 
                  && x < head ys =  (a,b)
                | otherwise      =  ([],r)

（再次，如丹尼尔的回答中所示）。

于 2013-01-22T03:53:18.730 回答
3

您可以使用右折叠来分解列表：

foldr foo [] xs
  where
    foo x yss = (x:zs) : ws
      where
        (zs, ws) = case yss of
                     (ys@(y:_)) : rest
                            | x < y     -> (ys,rest)
                            | otherwise -> ([],yss)
                     _ -> ([],[])

（为了让第二个参数中的组合函数变得惰性，这有点复杂，因此它也适用于无限列表。）

于 2013-01-18T16:37:55.600 回答
1

处理此任务的另一种方法（实际上奠定了非常有效的排序算法的基础）是使用连续传递样式，即 CPS，在这种特殊情况下，它适用于从右侧折叠；foldr.

照原样，这个答案只会将上升的块分块，但是同时将下降的块分块会很好......最好在 O(n) 中以相反的顺序排列，这将使我们只需要二进制合并获得的块以获得完美排序的输出。然而，这是另一个问题的另一个答案。

chunks :: Ord a => [a] -> [[a]]
chunks xs = foldr go return xs $ []
            where
            go :: Ord a => a -> ([a] -> [[a]]) -> ([a] -> [[a]])
            go c f = \ps -> let (r:rs) = f [c]
                            in case ps of
                               []  -> r:rs
                               [p] -> if c > p then (p:r):rs else [p]:(r:rs)

*Main> chunks [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> chunks [4,5,6,7,1,2,3,4,5,4,3,2,6,1,2]
[[4,5,6,7],[1,2,3,4,5],[4],[3],[2,6],[1,2]]

在上面的代码中，c代表当前，代表p上一个，记住我们是从右边折叠的，所以上一个，实际上是下一个要处理的项目。

于 2019-12-03T20:39:27.830 回答