División de listas en sublistas ordenadas

Question

¿Cómo puedo dividir una lista [1,2,4,1,5,7,3,4,2,3] en una lista de sublistas que se dividiría en los valores que rompen el secuencia. Por ejemplo, una lista [1,2,4,1,5,7,3,4,2,3] debería arrojar una lista de sublistas como [[1,2,4], [1,5,7], [ 3,4], [2,3]].

¿Alguna idea sobre esto o sugerencias sobre cómo resolver este problema?

Gracias.

Answer 1

Aquí hay una pista: cada vez que tiene que mirar a elementos consecutivos al procesar una lista, que es una buena idea empezar por comprimir la lista contra su cola:

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

Ahora usted puede usar algo como splitWhen $ uncurry (>) (donde splitWhen es de Data.List.Split) para dividir la lista apropiadamente.

Answer 2

Puede hacerlo con 2 funciones, una que divide la cabeza mientras que el primer elemento es más bajo que el segundo y otra que toma la salida de la función que divide la cabeza y concatena el resultado de una llamada recursiva a sí mismo con la cola de la lista.

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

como Travis anteriormente, mi primer pensamiento es para comprimir la lista con su propia cola: Sin embargo, no lo parece bastante trabaja en esta situación. No solo no existe realmente una función dividida que haga exactamente lo que usted desea, sino que también existe el problema de que perderá un elemento, ya sea al principio o al final. En lugar de una solución adecuada abstraído, echar un vistazo a esto:

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 

Una solución rápida y sucia, espero que se adapte a sus necesidades

- Además, este es mi primer post en desbordamiento de pila:)

Answer 4

Bueno, esto no es tan limpio como me gustaría, pero aquí está. El uso de paquete divide: 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') 

Los apoyos podría muy probable limpiado aquí.

Answer 5

¿Qué tal

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 

o

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  

?