需要一個列表劃分爲基於中的元素（哈斯克爾）的升序符列表

Question

說我有任何這樣的名單：

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

我需要一個哈斯克爾功能，將改變這個列表到列表列表由原始列表中按升序形成一系列的片段組成。所以結果應該是這樣的：

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

有什麼建議嗎？

Answer 1

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

Answer 2

您可以使用右倍，打破了列表中的下步驟：

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) 
        _ -> ([],[]) 

（這有點纔能有合併複雜函數在第二個參數中是惰性的，所以它對於無限列表也很有效。）

Answer 3

你可以通過manu但是我喜歡相信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 

的最後一步只是扔在一起構成的元組的位，即拆分元組的位，並改寫（munging）扔掉我們不關心的元組的位的最後一位：

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 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 g [] xs where 
    g x (y:_) ~(a:b) | x<y = (x:a):b 
    g x _  r   = [x]:r 

不重要的，因爲抽象適合。

BTW它們具有two kinds of map Common Lisp中 - 和maplist（列表的處理「尾部」）mapcar （由一個的輸入列表中的一個的處理元件）。有了這個想法，我們得到兩個版本

import Data.List (tails) 

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

懶人模式，使其具有無限的輸入工作在生產方式列出 （如在丹尼爾的回答首先所示）。