73 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

 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

More information

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