Different implementations of map in F#

mapcat.fs

let time func =
    System.GC.Collect()
    let start = System.Diagnostics.Stopwatch.GetTimestamp()
    func ()
    let ende = System.Diagnostics.Stopwatch.GetTimestamp()
    float (ende - start) / float System.Diagnostics.Stopwatch.Frequency * 1000.0
 
let timeavg name func =
    let times = 100
    let result = time (fun _ -> for i in 1..times do (func () |> ignore))
    printfn "%A took %f ms" name (float result / float times)
 
let generate n =
    let rec loop rest acc =
        if rest > 0 then loop (rest - 1) (rest :: acc) else acc
    loop n []
 
let reverse lst =
    let rec loop rest acc =
        match rest with
        | car :: cdr -> loop cdr (car :: acc)
        | [] -> acc
    loop lst []
 
let rec mapcat1 pred lst =
    match lst with
    | car :: cdr -> (pred car) :: (mapcat1 pred cdr)
    | [] -> []
 
let mapcat2 pred lst =
    let rec loop rest acc =
        match rest with
        | car :: cdr -> loop cdr (pred car :: acc)
        | [] -> acc
    loop lst []
 
let mapcat3 pred lst =
    let rec loop rest acc =
        match rest with
        | car :: cdr -> loop cdr (acc @ [pred car])
        | [] -> acc
    loop lst []
 
let mapcat4 pred lst =
    mapcat2 pred lst |> reverse
 
let mapcat5 pred lst =
    mapcat2 pred lst |> mapcat2 (fun x -> x)
 
let mapcat6 pred lst =
    let rec loop rest cont =
        match rest with
        | car :: cdr -> loop cdr (fun acc -> cont (pred car :: acc))
        | [] -> cont []
    loop lst (fun x -> x)
 
let count = 25000
 
let l = generate count
let square x = x * x
let timeavgl name func = timeavg name (fun _ -> func square l)
 
timeavgl "recursive" mapcat1
timeavgl "tail-recursive (cons)" mapcat2
// timeavgl "tail-recursive (append)" mapcat3 - commented out since it's quadratic
timeavgl "tail-recursive (cons) + reverse" mapcat4
timeavgl "tail-recursive (cons) + reverse (via map)" mapcat5
timeavgl "tail-recursive (continuations)" mapcat6
timeavgl "standard" List.map
 
type Cell =
    val car: int
    val mutable cdr: Cell
 
    new (car_, cdr_) = { car = car_; cdr = cdr_; }
 
let nil: Cell = Unchecked.defaultof<Cell>
let cons car cdr = Cell(car, cdr)
 
let generate_mut n =
    let rec loop rest acc =
        if rest > 0 then loop (rest - 1) (cons rest acc) else acc
    loop n nil
 
let rec mapcat1_mut pred lst =
    if System.Object.ReferenceEquals(lst, null) then lst
    else cons (pred lst.car) (mapcat1_mut pred lst.cdr)
 
let mapcat2_mut pred lst =
    let rec loop (rest: Cell) (last: Cell) =
        if System.Object.ReferenceEquals(rest, null) then
            rest
        else
            let cell = cons (pred rest.car) nil
            last.cdr <- cell
            loop rest.cdr cell
 
    let head = Cell(0, nil)
    let res = loop lst head
    head.cdr
 
let mapcat3_mut pred (lst: Cell) =
    if System.Object.ReferenceEquals(lst, null) then
        nil
    else
        let result = cons (pred lst.car) nil
 
        let mutable last = result
        let mutable rest = lst.cdr
 
        while not (System.Object.ReferenceEquals(rest, null)) do
            let cell = cons (pred rest.car) nil
            last.cdr <- cell
            last <- cell
            rest <- rest.cdr
 
        result
 
let l_mut = generate_mut count
let timeavgl_mut name func = timeavg name (fun _ -> func square l_mut)
 
timeavgl_mut "mutable recursive" mapcat1_mut
timeavgl_mut "mutable tail-recursive" mapcat2_mut
timeavgl_mut "mutable loop" mapcat3_mut