listocaml

Combining two lists alternately


Write a function that combines the two lists provided. Items in the output list are to alternate. You must not use library functions (e.g. "length", "reverse", "append") of complexity greater than O(1).

My code:

let rec zip(aList, bList) list = 
let rec first(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(aLst = []) then second(aLst,bLst)
     else aLst.hd :: second(aLst.tl, bLst)

 let rec second(aLst, bLst) list = 
    if(aLst = [] && bLst = []) then []
    else if(bLst = []) then first(aLst,bLst)
    else bLst.hd :: first(aLst, bLst.tl);;

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

The problem:

let rec second(aLst, bLst) list =

Error: Syntax error

I'm also afraid of rec - is it gonna work properly?


Solution

  • A common recursive pattern for alternation is to swap the arguments in recursive calls, eg.

    let rec zip a b =
      match a with
      | [] -> b
      | x :: a' -> x :: zip b a'                      (* swap arguments *)
    
    zip [-6;-5;-4] [1;2;3];;
    (* - : int list = [-6; 1; -5; 2; -4; 3] *)