Разделение списка на отсортированные подсписки

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

Как и в случае с Трэвисом выше, моя первая мысль - застегнуть список собственным хвостом: однако, в этой ситуации это не совсем похоже.Мало того, что на самом деле не существует функции разбиения, которая делает именно то, что вы хотите, но есть также проблема, что вы потеряете элемент в начале или в конце.Вместо правильно абстрактного решения, взгляните на это:

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 2

Вот подсказка: всякий раз, когда вам нужно посмотреть на последовательные элементы во время обработки списка, рекомендуется начать с сжатия списка с хвоста:

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 3

Ну, это не так чисто, как хотелось бы, но вот оно.Использование пакета split : 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 4

Вы можете сделать это с 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 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     

?