Splitting a list of items into two lists of odd and even indexed items

Question

I would like to make a function that accepts a list and returns two lists: the first contains every odd item, and the second contains every even item.

For example, given [1;2;4;6;7;9], I would like to return [ [1;4;7] ; [2;6;9] ].

I have written this so far and I do not know how to progress.

let splitList list =
    let rec splitOdd oList list1 list2 =
        match oList with
        | [] -> []
        | head :: tail -> splitEven tail (list1::head) list2
    and splitEven oList list1 list2 =
        match oList with
        | [] -> []
        | head :: tail -> splitOdd tail list1 (list2::head)
    splitOdd list [] []

Monaural

Couldn't you use List.partition for this? – Bohlin

@Mathias: No, List.partition uses a predicate and there is no suitable predicate in this case. – Blaylock

Answer 1

Implementation which does not stack-overflows:

let splitList list = List.foldBack (fun x (l,r) -> x::r, l) list ([],[])

Soosoochow

It's worth noting that foldBack converts the list to an array to allow tail-to-head traversal. This is generally a good thing since array traversal is fast, but the cost should be considered for larger lists. – Burmeister

Damn this is very nice solution. It took me few seconds to realize how it works but I have to admit that this solution is very elegant (y). – Deadening

So, can you explain it in more detail how does this work? If I understand correctly List.foldBack applies the function to each element in the list, goes from tail to head? ([],[]) is a tuple, where the state is stored. How does the fun part work? What is the meaning of x::r? Thanks – Kelbee

@DávidMolnár from the definition of fold, in pseudocode, split [a;b;c;d] --> (a::r , l) { where (l, r) <-- split [b;c;d] }; split [] --> ([] , []) . thus, [] --> ([],[]) ; [d] --> ([d],[]); [c;d] --> ([c],[d]); [b;c;d] --> ([b;d],[c]); [a;b;c;d] --> ([a;c] , [b;d])... – Reconvert

cf.. – Reconvert

Answer 2

If you mean odd and even values for positions of items, here is a (non-tail-recursive) solution:

let rec splitList = function
    | [] -> [], []
    | [x]-> [x], []
    | x1::x2::xs -> let xs1, xs2 = splitList xs
                    x1::xs1, x2::xs2

Protean

Entirely what I was looking for... thanks a lot! There's definitely much to learn about this language, especially its succinctness. – Monaural

The problem with this implementation though is that not being tail-recursive it causes stack overflow on lists of ~80000 elements. – Vicechairman

F# implementers could have taken note of en.wikipedia.org/wiki/Tail_call#Tail_recursion_modulo_cons – Reconvert

Answer 3

Here is a straightforward non-recursive solution:

let splitList ll =
    ll
    |> List.mapi (fun i x -> (i % 2 = 0, x))
    |> List.partition fst
    |> fun (odd,even) -> [List.map snd odd, List.map snd even];;

val splitList : 'a list -> 'a list list

Being applied to your sample it yields exactly what you wanted:

splitList [1;2;4;6;7;9];;

val it : int list list = [[1; 4; 7]; [2; 6; 9]]

Llama

Answer 4

Another (less efficient) option

let splitList xs = 
    let odd, even =
        xs
        |> List.zip [ 1 .. (List.length xs) ]
        |> List.partition (fun (i, _) -> i % 2 <> 0)
    [ odd |> List.map snd; even |> List.map snd ]

If you want to avoid creating temporary lists, consider using sequences:

let splitListSeq xs =
    xs
    |> Seq.mapi (fun i x -> (i % 2 = 0, x))
    |> Seq.groupBy (fun (b, _) -> b)
    |> Seq.map snd
    |> Seq.map ((Seq.map snd) >> Seq.toList)
    |> Seq.toList

Yet, another one, similar to Daniel's version:

let splitListRec xs =
    let rec loop l r = function
        | []      -> [l; r]
        | x::[]   -> [x::l; r]
        | x::y::t -> loop (x::l) (y::r) t
    loop [] [] xs |> List.map List.rev

Touchback

Answer 5

It looks like this is what you were going for, which is indeed a nice way to do it as it's tail-recursive.

let splitList items =
  let rec splitOdd odds evens = function
    | [] -> odds, evens
    | h::t -> splitEven (h::odds) evens t
  and splitEven odds evens = function
    | [] -> odds, evens
    | h::t -> splitOdd odds (h::evens) t
  let odds, evens = splitOdd [] [] items
  List.rev odds, List.rev evens

Burmeister

Answer 6

My 2¢, in OCaml, since there still is a bounty open.

Maybe you could give us a hint what you want. Elegance? FP? Tail recursion? Performance?

Edit:

I removed the longer solution. For List.partition to work, the predicate was missing. Here it is:

let so_split lst = 
  let flag = ref false in
  List.partition (fun e -> flag := not !flag; !flag) lst

Improvements any? Testing the solution:

# so_split [1;2;4;6;7;9];;
- : int list * int list = ([1; 4; 7], [2; 6; 9])

Allow

hi, the bounty does say "One or more of the answers is exemplary and worthy of an additional bounty." :) It is both to reward an answer and to draw attention to the question so more people might take interest in it. – Reconvert

Okay, I took interest in it. When someone asks for more information you would normally not repeat the known text, but paraphrase it, or better... – Allow

Answer 7

Sounds like you want List.partition<'T> ( http://msdn.microsoft.com/en-us/library/ee353782.aspx ). This function takes a predicate and a list and will return a pair (2-tuple) where the first element is all the elements that passed your test and the second is all the elements that did not pass the test. So you could classify odds and evens with:

List.partition odd [1;2;4;6;7;9]

If your really want a list, you can use fst and snd to extract the elements from the tuple and put them in a list.

Good luck!

Ouse

Again, the question is about odd and even index. partition doesn't pass the index to the function used for partitioning. – Halftimbered

I tried this method like so: List.partition (fun i -> (i % 2 = 0)) [1;2;4;6;7;9] and got this result ([2; 4; 6], [1; 7; 9]) . So, this solution is very good at separating odd numbers from even ones. – Commingle

Answer 8

Just for completeness here is a boring, more imperative solution:

let splitList (list:int list) =
    let odds = [for i in 0..list.Length-1 do
                  if i%2=1 then
                    yield list.[i]]
    let evens = [for i in 0..list.Length-1 do
                    if i%2=0 then
                        yield list.[i]]
    odds,evens 

Panhellenic

do the list comprehensions define lazily generated sequences, in F# ? – Reconvert

You need to use 'seq{ }' for lazy stuff, but it looks the same – Panhellenic

I was just wondering will this require two passes over the list or could it conceivably be compiled into one (lazy) pass that adds to one or the other resulting sequence's tail as it goes. (I'm a big fan of tailrecursion-modulo-cons). – Reconvert

A list comprehension will only produce one list (or seq). – Panhellenic