CODEWITHSUNDEEP
listf#functional-programmingocamltail-recursion
Nathron
Nathron

Reputation: 1649

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

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 [] []

Upvotes: 17

Views: 7348

Answers (8)

Fsharp Pete
Fsharp Pete

Reputation: 751

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

Upvotes: 0

Str.
Str.

Reputation: 1439

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])

Upvotes: 1

pad
pad

Reputation: 41290

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

Upvotes: 13

Frank
Frank

Reputation: 2788

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

Upvotes: 2

Ed&#39;ka
Ed&#39;ka

Reputation: 7140

Implementation which does not stack-overflows:

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

Upvotes: 41

Gene Belitski
Gene Belitski

Reputation: 10350

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]]

Upvotes: 8

Daniel
Daniel

Reputation: 47904

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

Upvotes: 2

gnuvince
gnuvince

Reputation: 2387

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!

Upvotes: 0

Related Questions