68 people like it.

# Projecting lists

Three functions showing how to implement projection for functional lists. First version uses naive recursion and the second one is tail-recursive using the accumulator parameter. The third version extends this with continuation passing.

## Naive recursive implementation

 1: 2: 3: 4: 5: 6: /// Create a list containing results of calling /// the function 'f' on all elements of the input 'list' let rec map f list = match list with | x::xs -> (f x)::(map f xs) | [] -> []

## Tail-recursive implementation

 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: /// Create a list containing results of calling /// the function 'f' on all elements of the input 'list' let map f list = /// Inner recursive function that uses /// accumulator argument to construct list let rec mapAux acc list = match list with | x::xs -> mapAux ((f x)::acc) xs | [] -> acc |> List.rev mapAux [] list

## Continuation passing implementation

 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: /// Create a list containing results of calling /// the function 'f' on all elements of the input 'list' let map f list = /// Inner recursive function that uses /// continuation argument to construct list let rec mapAux cont list = match list with | x :: xs -> mapAux (fun ys -> (f x)::ys |> cont) xs | [] -> cont [] mapAux id list
val map : f:('a -> 'b) -> list:'a list -> 'b list

Full name: Script.L1.map

Create a list containing results of calling
the function 'f' on all elements of the input 'list'
val f : ('a -> 'b)
Multiple items
val list : 'a list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val x : 'a
val xs : 'a list
val map : f:('a -> 'b) -> list:'a list -> 'b list

Full name: Script.L2.map

Create a list containing results of calling
the function 'f' on all elements of the input 'list'
val mapAux : ('b list -> 'a list -> 'b list)

Inner recursive function that uses
accumulator argument to construct list
val acc : 'b list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val map : f:('a -> 'b) -> list:'a list -> 'b list

Full name: Script.L3.map

Create a list containing results of calling
the function 'f' on all elements of the input 'list'
val mapAux : (('b list -> 'c) -> 'a list -> 'c)

Inner recursive function that uses
continuation argument to construct list
val cont : ('b list -> 'c)
val ys : 'b list
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id