75 people like it.

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:13 years ago
Author:Tomas Petricek
Tags: list , filter , recursion , pattern matching