Haskell: Splitting list into tuple of two new lists

Question

I am having difficulty figuring out how to split a list of Ints into a tuple containing two new lists, such that every element (starting with first) goes into the first list and every other element in the second.

Like so:

split [] = ([],[])
split [1] = ([1],[])
split [1,2] = ([1],[2])
split [1,2,3] = ([1,3],[2])
split [1,2,3,4] = ([1,3],[2,4])

I'm trying to accomplish this recursively(with guards) and only using the single argument xs

This is my approach that keeps getting error messages:

split :: [Int] -> ([Int],[Int])
split xs | length(xs) == 0 = ([],[])
         | length(xs) == 1 = (xs !! 0 : [],[])
         | length(xs) == 2 = (xs !! 0 : [], xs !! 1 : [])
         | otherwise = (fst ++ xs !! 0, snd ++ xs !! 1) ++ split(drop 2 xs))    

Answer 1

Your split function returns a pair, but in the last case you are using ++ on the result of split. That will be a type error, since ++ works on lists, not pairs. There is also a type error because fst and snd are functions to pick out the elements of a pair, but you are using them is a strange way.

Furthermore, use pattern matching instead of using length. Also, the case where you test if the length is 2 is not needed, since the general case removes 2 elements which takes you down to the base case of the empty list.

You can also make your function more general by using a type variable a instead of Int in the type.

[Edit]: Added code

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:xys) = (x:xs, y:ys) where (xs, ys) = split xys

Answer 2

Another way to do this is with mutual recursion. It comes out very easy to read:

split xs = (odds xs, evens xs)

odds (x:xs) = x : evens xs
odds xs     = []

evens xs = odds (drop 1 xs)

Answer 3

split :: [a] -> ([a], [a])
split xs | null xs = ([], [])
         | otherwise = (head xs : snd pair, fst pair)
  where pair = split (tail xs)

But you should be using a fold:

split :: [a] -> ([a], [a])
split = foldr (\x (ys, zs) -> (x : zs, ys)) ([], [])

Answer 4

The Haskell Blow Your Mind wiki, has some one liners:

-- splitting in two (alternating)
-- "1234567" -> ("1357", "246")

-- the lazy match with ~ is necessary for efficiency, especially enabling
-- processing of infinite lists
foldr (\a ~(x,y) -> (a:y,x)) ([],[])

(map snd *** map snd) . partition (even . fst) . zip [0..]

transpose . unfoldr (\a -> toMaybe (null a) (splitAt 2 a))

Answer 5

Two alternative versions:

split = conv . map (map snd) . groupWith (even.fst) . zip [0..] where
  conv [xs,ys] = (xs,ys)

split xs = (ti even xs, ti odd xs) where
  ti f = map snd . filter (f.fst) . zip [0..]

Answer 6

There is a mistake in the last clause. You have to get results from recursive call and then add first and second elements to them.

split :: [Int] -> ([Int],[Int])
split xs | length(xs) == 0 = ([],[])
         | length(xs) == 1 = (xs !! 0 : [],[])
         | length(xs) == 2 = (xs !! 0 : [], xs !! 1 : [])
         | otherwise = let (fst, snd) = split(drop 2 xs) in
                     (xs !! 0 : fst, xs !! 1 : snd)

Answer 7

In case you are looking for some alternate way to do this, below is one such implementation:

split xs = 
     let (a,b) = partition (odd . snd) (zip xs [1..]) 
     in ( (map fst a), (map fst b))

Answer 8

Here is a simple solution:

By taking a list [a] we are able to split it in two new list, first we start off by declaring what happens with a empty list, here you can choose between returning an error "Empty list" or just returning two empty list as shown below, in the case of one element in list we split it in one containing x and one empty list ([x],[ ]). In cases with list size > 1 we calculate n (length of the list "divided by" 2), then we 'take' the first n elements in a new list and 'drop' the n elements from the original list xs.

split :: [a] -> ([a],[a])
split [] = ([],[])
split [x] = ([x],[])
split xs = (take n xs, drop n xs)
    where n = (length xs) `div` 2