tip for tail recursive map

[pikatchou pokemon <ocaml.pikatchou@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1390 bytes --]

hi everyone,

I know this topic has been discussed several times, but I don't think I have
seen the solution I use for functions of the List module which are not tail
recursive.
I thought sharing the tip could be nice.
I will take an example, List.map.
When rewritten in CPS map becomes:

let rec map k f = function
  | []    -> k []
  | x :: rl -> map (fun res -> k ((f x) :: res)) f rl

The trick consists in "unfolding" this function manually, in order to
allocate less closures:

let rec map k f = function
  | [] -> k []
  | x :: rl ->
      let x = f x in
      match rl with
      | [] -> k [x]
      | y :: rl ->
            let y = f y in
            match rl with
            | [] -> k [x ; y]
            | z :: rl ->
                  let z = f z in
                    match rl with
                    | [] -> k [x ; y ; z]
                    | t :: rl ->
            let t = f t in
            map (fun res -> k (x :: y :: z :: t :: res)) f rl

Performances are roughly equivalent to List.map on short and medium size
lists (at least on my machine), but as
it's tail recursive it doesn't blow the stack on long lists.
Please note that performances are not as good as the "Obj.magic" version of
map on very long lists.
However, this does the job for me, I have a fast map on short and medium
size lists (< 10000 elements) but
still working on larger ones.

Hope this helps !

[-- Attachment #2: Type: text/html, Size: 1589 bytes --]