76 people like it.
Like the snippet!

Filtering lists

Two functions showing how to filter functional lists using the specified predicate. First version uses naive recursion and the second one is tail-recursive using the accumulator parameter.

Naive recursive implementation

1: 
2: 
3: 
4: 
5: 
6: 
7:

  /// Create a list containing all elements 
  /// of 'list' that match the predicate 'f'
  let rec filter f list = 
    match list with 
    | x::xs when f x -> x::(filter f xs)
    | _::xs -> filter f xs
    | [] -> []

Tail-recursive implementation

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11:

  /// Create a list containing all elements 
  /// of 'list' that match the predicate 'f'
  let filter f list = 
    /// Inner recursive function that uses
    /// accumulator argument to construct list
    let rec filterAux acc list = 
      match list with 
      | x::xs when f x -> filterAux (x::acc) xs
      | _::xs -> filterAux acc xs
      | [] -> acc |> List.rev
    filterAux [] list

val filter : f:('a -> bool) -> list:'a list -> 'a list

Full name: Script.L1.filter

Create a list containing all elements
of 'list' that match the predicate 'f'

val f : ('a -> bool)

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 filter : f:('a -> bool) -> list:'a list -> 'a list

Full name: Script.L2.filter

Create a list containing all elements
of 'list' that match the predicate 'f'

val filterAux : ('a list -> 'a list -> 'a list)

Inner recursive function that uses
accumulator argument to construct list

val acc : 'a 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

Raw view Test code New version

More information

Link:	http://fssnip.net/m
Posted:	14 years ago
Author:	Tomas Petricek
Tags:	list , filter , recursion , pattern matching