Ocaml Functional Programming Tree

Question

I'm writing a function called unzip that turns:

[(1,2);(3,4);(5,6)]

to

([1;3;5],[2;4;6])

I've got a working implementation right here:

let unzip (data:(int*int) list) : int list * int list =
   match data with
   |(x,y)::tl->(x::traverse (tl,true),y::traverse (tl,false))
   |[]->([],[])
  let rec traverse tree = 
    match tree with
    |((x,y)::tl,dir) -> if dir then x::traverse (tl, dir) else y::traverse (tl,dir)
    |([],_) -> [];;

However I'm not sure if this is the cleanest way to do this. As you can see, my traverse function accepts a boolean to know whether or not to go right or left, specifically because of:

(x::traverse (tl,true),y::traverse (tl,false))

Now is there even a way to do this so I only have to call one function, AND it knows where to put the data? or is this an alright way of doing it?

PS: I can't use non-core functions. (Modules, etc.)

Answer 1

You have the right idea, but you didn't quite know how to get there. You don't need that traverse function to operate on the left or right lists. Just bind them to separate variables through a simple let in expression and you can add the items to each of the lists.

let rec unzip = function
    | (x, y)::t -> let l, r = unzip t in (x::l, y::r)
    | []        -> ([], [])