Haskell: Divisione di una lista in 2 all'indice k

Question

Sono abbastanza nuovo per Haskell e sto avendo un piccolo problema. Sto cercando di implementare una funzione che accetta una lista e un int. l'int dovrebbe essere l'indice k in cui la lista è divisa in una coppia di liste. Il primo contenente i primi k elementi dell'elenco e il secondo da k + 1 all'ultimo elemento. Ecco cosa ho fino ad ora:

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!" 

Non riesco a capire come eseguire la divisione. Qualsiasi aiuto sarebbe apprezzato.

Answer 1

Fondamentalmente, hai bisogno di un modo per passare il progresso parziale mentre ricorri dall'elenco. Ho usato una seconda funzione che accetta un parametro dell'accumulatore; viene chiamato da split e quindi si chiama in modo ricorsivo. Ci sono quasi certamente modi migliori ..

EDIT:. rimossi tutti i controlli di lunghezza, ma credo che l'uso di ++ significa che è ancora 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!" 

per ottenere il comportamento nel post originale o

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

per ottenere il comportamento più clemente della funzione standard splitAt.

Answer 2

Prima di tutto, si noti che la funzione che si sta tentando di costruire è già nella libreria standard, nello Prelude - si chiama splitAt. Ora, guardare direttamente alla sua definizione è confuso, poiché ci sono due algoritmi, uno che non usa affatto la struttura ricorsiva standard - splitAt n xs = (take n xs, drop n xs) - e uno che è ottimizzato a mano rendendolo brutto. Il primo ha un senso più intuitivo, dato che stai semplicemente prendendo un prefisso e un suffisso e mettendoli in coppia. Tuttavia, quest'ultimo insegna più, e ha questa struttura generale:

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

L'idea di base è che se un elenco è costituito da una testa e una coda (è della forma x:xs), allora l'elenco andando dall'indice k + 1 in poi sarà uguale alla lista che va da k in poi una volta rimosso il primo elemento - drop (k + 1) (x : xs) == drop k xs. Per costruire il prefisso, rimuovi in ​​modo simile il primo elemento, prendi un prefisso più piccolo e rimetti l'elemento su - take (k + 1) (x : xs) == x : take k xs.

Answer 3

Vedi splitAt nel preludio:

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

Answer 4

Un trucco comune per sbarazzarsi di un comportamento quadratica nella costruzione di una lista è quello di costruire fino a ritroso, poi invertire esso, modificando la soluzione di 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!" 

Il controllo degli errori in ssplit va bene poiché non verrà controllato (uno dei modelli precedenti corrisponderà) a meno che non vi sia un errore effettivo.

In pratica si potrebbe voler aggiungere alcune annotazioni di rigore a ssplit per gestire la crescita dello stack, ma questo è un ulteriore raffinamento.

Answer 5

Che dire di questo:

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

Alcuni test:

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