How can I implement a tail-recursive list append?
append, f#, tail-recursion
Solution
Traditional (not tail-recursive)
let rec append a b =
match a, b with
| [], ys -> ys
| x::xs, ys -> x::append xs ys
With an accumulator (tail-recursive)
let append2 a b =
let rec loop acc = function
| [] -> acc
| x::xs -> loop (x::acc) xs
loop b (List.rev a)
With continuations (tail-recursive)
let append3 a b =
let rec append = function
| cont, [], ys -> cont ys
| cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys)
append(id, a, b)
Its pretty straight-forward to convert any non-tail recursive function to recursive with continuations, but I personally prefer accumulators for straight-forward readability.
Problem
A simple append function like this (in F#): ``` let rec app s t = match s with | [] -> t | (x::ss) -> x :: (app ss t) ``` will crash when s becomes big, since the function is not tail recursive. I noticed that F#'s standard append function does not crash with big lists, so it must be implemented differently. So I wondered: How does a tail recursive definition of append look like? I came up with something like this: ``` let rec comb s t = match s with | [] -> t | (x::ss) -> comb ss (x::t) let app2 s t = comb (List.rev s) t ``` which works, but looks rather odd. Is there a more elegant definition?