Haskell: split even and odd elements into tuple

I can't use high order functions. I just can't see to figure out how to do this. I am very new to haskell. It also has to be recursive.

split :: [Int] -> ([Int],[Int])
split xs = 

I am given this to start with. I honestly don't even know where to start with this problem.

Examples:

split []
([],[])

split [1]
([1],[])

split [1,2,3,4,5,6,7,8,9,10]
([1,3,5,7,9],[2,4,6,8,10])

any help would be much appreciated.

Edit: Its even and odd positions.

So

split [3,6,8,9,10] would be ([3,8,10],[6,9])

ok so i came up with this. Its not pretty, but it seems to work ok.

split :: [Int] -> ([Int],[Int])
split [] = ([],[])
split [xs] = ([xs],[])
split xs = (oddlist xs, evenlist xs)

oddlist :: [Int] -> ([Int])
oddlist xs | length xs <= 2 = [head(xs)]
           | otherwise = [head(xs)] ++ oddlist(tail(tail(xs)))

evenlist :: [Int] -> ([Int])
evenlist xs | length xs <= 3 = [head(tail(xs))]
            | otherwise = [head(tail(xs))] ++ evenlist(tail(tail(xs)))

split [] = ([], [])
split [x] = ([x], [])
split (x:y:xs) = (x:xp, y:yp) where (xp, yp) = split xs

If you relax the "no higher-order functions" restriction, you can do it like this:

split :: [a] -> ([a],[a])
split = foldr (\x ~(y2,y1) -> (x:y1, y2)) ([],[])

Note the ~ makes the pattern match lazy, so split can produce results on demand, rather than needing to inspect the entire list first.

You can reimpose the restriction by expanding the foldr:

split :: [a] -> ([a],[a])
split [] = ([],[])
split (x : xs) = (x : y1, y2)
  where
    (y2, y1) = split xs

If you’re not allowed to use higher-order list functions, your alternative is basically to use recursion.

The examples already give the cases that you need to cater to:

-- Base case:
split [] = …

-- Recurrence:
split (x : xs) = (do something with x) … (split xs) …

Since you've put your solution up now, this is how I would implement it:

split xs = (everyother 0 xs, everyother 1 xs)
      where everyother _ []     = []
            everyother 1 (x:xs) = everyother 0 xs
            everyother 0 (x:xs) = x : (everyother 1 xs)

This implies that the first item in a list is item 0.

I think it is related to Get every Nth element.

Anyway, this is what I would do:

ghci> let split ys = let skip xs = case xs of { [] -> [] ; [x] -> [x] ; (x:_:xs') -> x : skip xs' } in (skip ys, skip . drop 1 $ ys)
ghci> split [1..10]
([1,3,5,7,9],[2,4,6,8,10])

Or nicely formatted:

split xs = (skip xs, skip . drop 1 $ xs)
  where 
  skip [] = []
  skip [x] = [x]
  skip (x:_:xs') = x : skip xs'