將列表拆分成已排序的子列表

Question

如何將列表[1,2,4,1,5,7,3,4,2,3]劃分爲一個子列表，該子列表將按照打破序列。例如，一個列表[1,2,4,1,5,7,3,4,2,3]應該產生一個子列表，如[[1,2,4]，[1,5,7]，[ 3,4]，[2,3]。

對此的任何想法或建議如何解決此問題？

謝謝。

Answer 1

這裏有一個提示：每當你需要看連續的元素，同時處理的列表，這是一個好主意，通過荏苒名單反對它的尾巴開始：

Prelude> let f xs = zip xs $ tail xs 
Prelude> f [1,2,4,1,5,7,3,4,2,3] 
[(1,2),(2,4),(4,1),(1,5),(5,7),(7,3),(3,4),(4,2),(2,3)] 

現在你可以使用類似splitWhen $ uncurry (>)（其中splitWhen來自Data.List.Split）以適當地劃分列表。

Answer 2

你可以用2個函數來完成它，一個是在第一個項目低於第二個時分割頭部，另一個是分割頭部的函數的輸出，並將遞歸調用的結果連接到本身與列表的尾部。

splitList :: [Int] -> [[Int]] 
splitList [] = [] 
splitList (x:xs) = ys : splitList zs 
    where (ys,zs) = splitHead (x:xs) 


splitHead :: [Int] -> ([Int], [Int]) 
splitHead [x] = ([x], []) 
splitHead (x:y:xs) 
    | x > y = ([x], (y:xs)) 
    | x <= y = (x:ys, zs) 
    where (ys,zs) = splitHead (y:xs) 

Answer 3

像特拉維斯上面，我首先想到的是自己的尾巴壓縮列表： 但是，它看起來並不像它相當在這種情況下工作。不僅沒有真正的分裂函數能夠完全符合你的要求，而且還有一個問題是你會在開始或結束時失去一個元素。代替抽象適當的解決方案，來看看這個：

splitAscending :: Ord a => [a] -> [[a]] 
splitAscending = foldr f [] where 
    f x [] = [[x]] 
    f x (y:ys) = if x < head y 
    -- It's okay to call head here because the list y is 
    -- coming from the summary value of the fold, which is [[a]]. 
    -- While the sum value may be empty itself (above case), it will 
    -- never CONTAIN an empty list. In general be VERY CAREFUL when 
    -- calling head. 
     then (x:y):ys -- prepend x to the first list in the summary value 
     else [x]:y:ys -- prepend the new list [x] to the summary value 

一個快速和骯髒的解決方案，我希望它適合你的需要

- 而且，這是我對堆棧溢出的第一篇文章： ）

Answer 4

嗯，這並不像我希望的那樣乾淨，但是在這裏。 分裂使用包：http://hackage.haskell.org/package/split

:m+ Data.List.Split 
Prelude Data.List.Split> let f ys = let ys' = zip ys (tail ys) in map (map fst) ((split . whenElt) (uncurry (>)) $ ys') 

大括號可以非常容易清理這裏。

Answer 5

如何

asc [] = [[]] 
asc (x:xs) = map reverse $ reverse $ foldl ins [[x]] xs 
    where ins ((y:ys):yss) z | z > y = (z:y:ys) : yss 
          | otherwise = [z] : (y:ys) : yss 

或

asc = map reverse.reverse.foldl ins [[]] 
     where ins [[]] z = [[z]] 
      ins ((y:ys):yss) z | z > y = (z:y:ys) : yss 
           | otherwise = [z] : (y:ys) : yss  

？