CODEWITHSUNDEEP
ocaml
Collin
Collin

Reputation: 1867

OCaml recursive function int list -> int -> (int list * int list)

Studying for a midterm and was looking through some old exam questions. This one doesn't have a solution posted and is stumping me:

partition: int list -> int -> (int list * int list) divides its first argument into two lists, one containing all elements less than its second argument, and the other all the elements greater than or equal to its second argument. partition [5;2;10;4] 4 = ([2], [5;10;4])

oh, and i'm supposed to be able to find the solution without using an auxiliary function

here is as far as i've gotten: 

let rec partition l n = match l with 
    | [] -> ([], []) (* must return this type *)
    | x :: xs -> if x < n then (* append x to first list, continue recursing *)
                    else (* append x to second list, continue recursing *)

normally, I'd use an aux function with an extra parameter to store the pair of lists i'm building, but that can't be done here. i'm a bit stuck

Upvotes: 1

Views: 1142

Answers (1)

hivert
hivert

Reputation: 10667

You should use the let in construction to match the return value of the recursive call:

let rec partition l n = match l with 
    | [] -> ([], [])
    | x :: xs -> let a, b = partition xs n in
                    if x < n then (x::a), b
                    else          a, (x::b);;

Upvotes: 2

Related Questions