How to convert this function to use tail call

Question

Recursive function:

let rec listMerge (l1 : 'a list) (l2 : 'a list) =
    if l1.IsEmpty then      l2 
    elif l2.IsEmpty then    l1 
    else                    l1.Head :: l2.Head :: listMerge l1.Tail l2.Tail

Now, unless I am happily mistaken, this does not actually perform tail call, it just may look like it, if not considering that :: is right associative.

Then, I am under impression (from something I read, but couldn't find now) that this can easily be converted to tail recursive by using an extra fun or something.

So, is it possible? Code?

My answer: So, this is how I changed the functions, thanks to answers below:

let listMerge l1 l2 =
    let rec mergeLoop  (l1 : 'a list) (l2 : 'a list) acc =
        if l1.IsEmpty then      (List.rev acc) @ l2 
        elif l2.IsEmpty then    (List.rev acc) @ l1
        else                    mergeLoop l1.Tail l2.Tail (l2.Head :: l1.Head :: acc)
    mergeLoop l1 l2 []

Answer 1

You can accumulate the constructed result in subsequent calls to listMerge and finally return the accumulated result. My F# skills are pretty rusted, but here goes a simple Lisp function.

(defun list-merge (xs ys &optional acc)
  (cond ((< 0 (length xs)) (list-merge (rest xs) ys (cons (first xs) acc)))
        ((< 0 (length ys)) (list-merge xs (rest ys) (cons (first ys) acc)))
        (t acc)))

(list-merge '(1 2 3) '(3 4 5)) ;=> (5 4 3 3 2 1)
(list-merge '() '(1 2))        ;=> (2 1)
(list-merge '() '())           ;=> nil

Answer 2

You should use pattern matching:

let rec merge xs ys =
  match xs, ys with
  | [], xs | xs, [] -> xs
  | x::xs, y::ys -> x::y::merge xs ys

To get tail calls you can use an accumulator:

let merge xs ys =
  let rec loop xys xs ys =
    match xs, ys with
    | [], xs | xs, [] -> List.fold (fun xs x -> x::xs) xs xys
    | x::xs, y::ys -> loop (y::x::xys) xs ys
  loop [] xs ys

or continuation passing style:

let merge xs ys =
  let rec loop xs ys k =
    match xs, ys with
    | [], xs | xs, [] -> k xs
    | x::xs, y::ys -> loop xs ys (fun xys -> k(x::y::xys))
  loop xs ys id

Answer 3

As @Ramon suggested, you should use pattern matching for better readability:

let rec listMerge xs ys =
    match xs, ys with
    | [], _ -> ys
    | _, [] -> xs
    | x::xs', y::ys' -> x::y::listMerge xs' ys'

As you can see, two cons constructors (::) are the last operations on listMerge so the function isn't tail-recursive.

You can use an accumulator to obtain results in a tail-recursive way:

let listMerge xs ys =
    let rec loop xs ys acc =
        match xs, ys with
        | [], zs | zs, [] -> (List.rev zs)@acc
        | x::xs', y::ys' -> loop xs' ys' (y::x::acc)
    List.rev (loop xs ys [])

In the function above, the first List.rev call could be avoided if you add a few more patterns to deconstruct two lists until both of them are empty.

In F#, there is a tail-recursive approach using sequence expressions which is along the line of continuation-passing style:

let listMerge xs ys =
    let rec loop xs ys =
        seq {
            match xs, ys with
            | [], zs | zs, [] -> yield! zs
            | x::xs', y::ys' -> 
                yield x
                yield y
                yield! loop xs' ys'
        }
    loop xs ys |> Seq.toList

I like this approach since it is convenient and close to your original formulation.

Answer 4

I think you have to reuse the original F# code found in F# PowerPack.
In fact, what you need is List.fold2, except the function should not throw an exception SR.listsHadDifferentLengths in case if the list sizes are different, but instead process the remainder of the longer list, like this:

let l1 = ["A1"; "A2"; "A3"; "A4"; "A5"; "A6"; "A7"]
let l2 = ["B1"; "B2"; "B3"; "B4"]

let expectedResult = ["A1"; "B1"; "A2"; "B2"; "A3"; "B3"; "A4"; "B4"; "A5"; "A6"; "A7"]

Here's how we do it:

[<CompiledName("Fold2Tail")>]
let fold2Tail<'T1,'T2,'State> f g1 g2 (acc:'State) (list1:list<'T1>) (list2:list<'T2>) = 
    let f  = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
    let g1 = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(g1)
    let g2 = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(g2)
    let rec loop acc list1 list2 =
        match list1, list2 with 
        | [], [] -> acc
        | _,  []  -> g1.Invoke(acc, list1)
        | [], _   -> g2.Invoke(acc, list2)
        | (h1::t1),(h2::t2) -> loop (f.Invoke(acc,h1,h2)) t1 t2
    loop acc list1 list2

g1 and g2 are predicates of type 'State -> 'T1 list -> 'State and 'State -> 'T2 list -> 'State, correspondingly. They tell how to process the remainders of both lists. Note there are two of them, since in general case 'T1 and 'T2 are different types. Yes, it is somewhat overhead, but you can easily reduce it to your needs, sacrificing universality.

Usage:

let ret =
    fold2Tail
        (fun s x y  -> [ yield! s; yield x; yield y ] ) // f
        List.append // g1
        List.append // g2
        []          // 'State
        l1 l2

Answer 5

Simple version using an accumulator:

let rec listMerge (l1 : 'a list) (l2 : 'a list) acc =
    if l1.IsEmpty then      (List.rev l2)@acc 
    elif l2.IsEmpty then    (List.rev l1)@acc
    else                    listMerge l1.Tail l2.Tail (l1.Head :: l2.Head :: acc)

I tested this with two million element lists and there was no stack overflow so I am reasonably confident this is tail recursive.