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.

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

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

Link:http://fssnip.net/1c
Posted:14 years ago
Author:Nick Palladinos
Tags: fixed point

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.