Haskell: splitting a list into 2 with index k

Question

I am new to Haskell and I have small problems. I am trying to implement a function that takes a list, and int. int must be an index k at which the list is split into a pair of lists. The first of them contains the first k elements of the list, and the second - from k + 1 to the last element. Here is what I still have:

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

I can’t figure out how to make a split. Any help would be appreciated.

Answer 1

First of all, note that the function that you are trying to build is already in the standard library, in Prelude - it is called splitAt . Now the direct definition is confusing because there are two algorithms: one that does not use the standard recursive structure at all - splitAt n xs = (take n xs, drop n xs) - and one that is manually optimized, making it ugly. The first has a more intuitive meaning, because you just take the prefix and suffix and put them in a pair. However, the latter teaches more and has this general structure:

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

The basic idea is that if the list consists of a head and a tail (it has the form x:xs ), then the list coming from index k + 1 will be the same as the list going from k after you delete the first element is drop (k + 1) (x : xs) == drop k xs . To build a prefix, remove the first element in the same way, take the smaller prefix and reinsert the element - take (k + 1) (x : xs) == x : take k xs .

Answer 2

How about this:

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

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

Answer 3

Basically, you need some way to go through partial progress when you recurs through a list. I used a second function that takes a battery parameter; it is called from split and then calls itself recursively. There are almost certainly better ways.

EDIT: removed all length checks., But I believe using ++ means it is still 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!" 

to get the behavior in the original message or

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

To get the more forgiving behavior of the standard splitAt function.

Answer 4

A common trick to get rid of quadratic behavior when building a list is to create it back and then change it, change Mark Reed's solution:

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

Error checking in ssplit is great because it will not be checked (one of the earlier templates will match) if there is no actual error.

In practice, you may need to add a few severity annotations to ssplit to control stack growth, but this is another refinement.

Answer 5

See splitAt in the prelude:

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