302 people like it.

A beautiful fixed-point finding function

We start with an initial value and then applying f repeatedly, until the value does not change anymore.

let rec iterate f value = seq { yield value; yield! iterate f (f value) }

let fixedPoint f initial = 
    iterate f initial 
        |> Seq.pairwise 
        |> Seq.pick (fun (first, second) -> if first = second then Some first else None)
val iterate : f:('a -> 'a) -> value:'a -> seq<'a>

Full name: Script.iterate
val f : ('a -> 'a)
val value : 'a
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val fixedPoint : f:('a -> 'a) -> initial:'a -> 'a (requires equality)

Full name: Script.fixedPoint
val f : ('a -> 'a) (requires equality)
val initial : 'a (requires equality)
module Seq

from Microsoft.FSharp.Collections
val pairwise : source:seq<'T> -> seq<'T * 'T>

Full name: Microsoft.FSharp.Collections.Seq.pairwise
val pick : chooser:('T -> 'U option) -> source:seq<'T> -> 'U

Full name: Microsoft.FSharp.Collections.Seq.pick
val first : 'a (requires equality)
val second : 'a (requires equality)
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
Next Version Raw view Test code New version

More information

Posted:13 years ago
Author:Nick Palladinos
Tags: fixed point