73 people like it.
Like the snippet!

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 Head : '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

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/n
Posted:	14 years ago
Author:	Tomas Petricek
Tags:	list , map , recursion , pattern matching , continuation passing