Haskell: Splitting a list into 2 at index k

Question

I'm pretty new to Haskell, and I'm having a little trouble. I'm trying to implement a function that takes a list, and an int. the int is supposed to be the index k at which the list is split into a pair of lists. The first one containing the first k elements of the list, and the second from k+1 to the last element. Here's what I have so far:

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 actually figure out how to do the split. Any help would be appreciated.

Answer 1

First of all, note that the function you are trying to construct is already in the standard library, in the Prelude - it is called splitAt. Now, directly looking at its definition is confusing, as there are two algorithms, one which doesn't use the standard recursive structure at all -splitAt n xs = (take n xs, drop n xs) - and one that is hand-optimized making it ugly. The former makes more intuitive sense, as you are simply taking a prefix and a suffix and putting them in a pair. However, the latter teaches more, and has this overall 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 a list is made up of a head and a tail (it is of the form x:xs), then the list going from index k+1 onwards will be the same as the list going from k onwards once you remove the first element - drop (k + 1) (x : xs) == drop k xs. To construct the prefix, you similarly remove the first element, take a smaller prefix, and stick the element back on - take (k + 1) (x : xs) == x : take k xs.