Haskell: dividiendo una lista en 2 en el índice k

Question

Soy bastante nuevo para Haskell, y estoy teniendo un pequeño problema. Estoy tratando de implementar una función que toma una lista y un int. el int se supone que es el índice k en el que la lista se divide en un par de listas. El primero contiene los primeros k elementos de la lista, y el segundo de k + 1 al último elemento. Esto es lo que tengo hasta ahora:

split :: [a] -> Int -> ([a], [a]) 
split [] k = error "Empty list!" 
split (x:[]) k = ([x],[]) 
split xs k | k >= (length xs) = error "Number out of range!" 
      | k < 0 = error "Number out of range!" 

No puedo entender cómo hacer la división. Cualquier ayuda sería apreciada.

Answer 1

Básicamente, necesita una forma de pasar el progreso parcial a medida que recurse a través de la lista. Usé una segunda función que toma un parámetro de acumulador; se llama por división y luego se llama de manera recursiva. Es casi seguro que mejores formas ..

EDIT:. eliminado todos los controles de longitud, pero creo que el uso de ++ significa que sigue siendo O (n^2).

split xs k | k < 0 = error "Number out of range!" 
split xs k = ssplit [] xs k 

ssplit p xs 0 = (p, xs) 
ssplit p (x:xs) k = ssplit (p++[x]) xs (k-1) 
ssplit p [] k = error "Number out of range!" 

para obtener el comportamiento en el post original o

ssplit p [] k = (p,[]) 

para obtener el comportamiento más indulgente de la función estándar splitAt.

Answer 2

En primer lugar, tenga en cuenta que la función que está tratando de construir ya está en la biblioteca estándar, en el Prelude - se llama splitAt. Ahora, mirar directamente su definición es confuso, ya que hay dos algoritmos, uno que no usa la estructura recursiva estándar (splitAt n xs = (take n xs, drop n xs)) y uno que está optimizado a mano, lo que lo hace feo. El primero tiene un sentido más intuitivo, ya que simplemente toma un prefijo y un sufijo y los pone en un par. Sin embargo, esta última enseña más, y tiene esta estructura general:

splitAt :: Int -> [a] -> ([a], [a]) 
splitAt 0 xs  = ([], xs) 
splitAt _ []  = ([], []) 
splitAt n (x:xs) = (x:xs', xs'') 
    where 
    (xs', xs'') = splitAt (n - 1) xs 

La idea básica es que si una lista se compone de una cabeza y una cola (que es de la forma x:xs), a continuación, la lista va del índice k + 1 en adelante será el mismo que la lista que va de k en adelante una vez que elimine el primer elemento - drop (k + 1) (x : xs) == drop k xs. Para construir el prefijo, de forma similar elimina el primer elemento, toma un prefijo más pequeño y vuelve a colocar el elemento - take (k + 1) (x : xs) == x : take k xs.

Answer 3

Ver splitAt en el preludio:

ghci> :t flip splitAt 
flip splitAt :: [a] -> Int -> ([a], [a]) 
ghci> flip splitAt ['a'..'j'] 5 
("abcde","fghij") 

Answer 4

Un truco común para deshacerse de la conducta de segundo grado en la construcción de una lista es construir hacia arriba hacia atrás, luego revertirla, modificando solución de Mark Reed:

split xs k | k < 0 = error "Number out of range!" 
split xs k = (reverse a, b) 
    where 
    (a,b) = ssplit [] xs k 

ssplit p xs 0 = (p, xs) 
ssplit p (x:xs) k = ssplit (x:p) xs (k-1) 
ssplit p [] k = error "Number out of range!" 

La comprobación de errores en ssplit está bien ya que no se comprobará (uno de los patrones anteriores coincidirá) a menos que haya un error real.

En la práctica, es posible que desee agregar algunas anotaciones de rigor a ssplit para administrar el crecimiento de la pila, pero eso es un refinamiento adicional.

Answer 5

Qué tal esto:

splitAt' = \n -> \xs -> (take n xs, drop n xs) 

Algunas pruebas:

> splitAt' 3 [1..10] 
> ([1,2,3],[4,5,6,7,8,9,10]) 

> splitAt' 0 [1..10] 
> ([],[1,2,3,4,5,6,7,8,9,10]) 

> splitAt' 3 [] 
> ([],[]) 

> splitAt' 11 [1..10] 
> ([1,2,3,4,5,6,7,8,9,10],[]) 

> splitAt' 2 "haskell" 
> ("ha","skell")