CODEWITHSUNDEEP
listhaskellsplit
papercup
papercup

Reputation: 91

Haskell: Splitting a list into 2 at index k

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.

Upvotes: 9

Views: 17649

Answers (5)

jimmyt
jimmyt

Reputation: 501

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

Upvotes: 4

none
none

Reputation: 11

A common trick for getting rid of quadratic behavior in building a list is to build it up backwards, then reverse it, modifying 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!"

The error check in ssplit is fine since won't get checked (one of the earlier patterns will match) unless there is an actual error.

In practice you might want to add a few strictness annotations to ssplit to manage stack growth, but that's a further refinement.

Upvotes: 1

Mark Reed
Mark Reed

Reputation: 95242

Basically, you need some way of passing along partial progress as you recurse through the list. I used a second function that takes an accumulator parameter; it is called from split and then calls itself recursively. There are almost certainly better ways..

EDIT: removed all the length checks., but I believe the use of ++ means it's 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 post or

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

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

Upvotes: 1

jkoshy
jkoshy

Reputation: 1863

See splitAt in the prelude:

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

Upvotes: 0

gereeter
gereeter

Reputation: 4761

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.

Upvotes: 20

Related Questions