Haskell: Teilen einer Liste in 2 bei Index k

Question

Ich bin ziemlich neu in Haskell, und ich habe ein wenig Ärger. Ich versuche, eine Funktion zu implementieren, die eine Liste und einen Int aufnimmt. Der int soll der Index k sein, bei dem die Liste in ein Listenpaar aufgeteilt wird. Der erste enthält die ersten k Elemente der Liste und der zweite von k + 1 bis zum letzten Element. Hier ist, was ich bis jetzt habe:

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

Ich kann nicht wirklich herausfinden, wie man die Spaltung macht. Jede Hilfe wäre willkommen.

Answer 1

Im Grunde brauchen Sie eine Möglichkeit, einen Teil des Fortschritts weiterzuleiten, während Sie durch die Liste rekrutieren. Ich habe eine zweite Funktion verwendet, die einen Akkumulator-Parameter annimmt; es wird von split aufgerufen und ruft sich dann rekursiv auf. Es gibt fast sicher bessere Möglichkeiten ..

EDIT:. entfernt alle Länge überprüft, aber ich glaube, dass die Verwendung von ++ bedeutet, es ist immer noch 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!" 

das Verhalten in der ursprünglichen Nachricht zu erhalten oder

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

das tolerante Verhalten der Standard splitAt Funktion zu erhalten.

Answer 2

Beachten Sie, dass die Funktion, die Sie versuchen zu konstruieren, bereits in der Standardbibliothek ist, in der Prelude - es heißt splitAt. Nun, es ist verwirrend, seine Definition direkt zu betrachten, da es zwei Algorithmen gibt, einen, der überhaupt nicht die rekursive Standardstruktur verwendet - und eine, die handoptimiert ist, was sie hässlich macht. Ersteres macht mehr intuitiven Sinn, da Sie einfach ein Präfix und ein Suffix nehmen und sie zu einem Paar zusammenfügen. Jedoch lehrt das letztere, und hat diese Gesamtstruktur:

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

Die Grundidee ist, dass, wenn eine Liste aus einem Kopf und einem Schwanz gemacht wird (es ist von der Form x:xs), dann wird die Liste gehen ab dem Index k + 1 ist das gleiche wie die Liste ab k, wenn Sie das erste Element - drop (k + 1) (x : xs) == drop k xs - entfernen. Um das Präfix zu konstruieren, entfernen Sie in ähnlicher Weise das erste Element, nehmen ein kleineres Präfix und kleben das Element wieder an - take (k + 1) (x : xs) == x : take k xs.

Answer 3

Siehe splitAt im Vorspiel:

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

Answer 4

Ein gemeinsamer Trick für den Aufbau eine Liste von quadratischen Verhalten loszuwerden ist es nach hinten aufzubauen, ist es dann umgekehrt, Mark Reed-Lösung ändern:

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

Die Fehlerprüfung in sssplit ist in Ordnung, da nicht überprüft wird (eines der früheren Muster wird übereinstimmen), es sei denn, es liegt ein tatsächlicher Fehler vor.

In der Praxis möchten Sie vielleicht einige stressness Annotationen zu ssplit hinzufügen, um Stack-Wachstum zu verwalten, aber das ist eine weitere Verfeinerung.

Answer 5

Was dazu:

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

Einige Tests:

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