Back to Questions
3.3k
views5
comments
What's the best way to do an iteration until convergence without using mutable state in F#?
f#

Consider we have this code:

1
2
3
4
5
6
7
8

    let mutable t = initialValue
    let mutable converged = false
    while not converged do
        let previousT = t 
        t <- computeIteration t
        if t = previousT then
            converged <- true
    t

How can we do this in a purely funcional way?

.

Your code is reasonable F# code (though usage of ref types is usually better), but you could write this:

1
2
3
4
5

let rec loop t =
  let nextT = computeIteration t
  if t <> nextT then
    loop nextT
loop initialValue
By on 10/16/2011 4:52 PM ()

There is no way in this code to get the value of the last state no ?
Maybe this :

1
2
3
4
5
6
7
8

// val convergence : ('a -> 'a) -> 'a -> 'a (requires equality)
let rec convergence f state =
    let state' = f state
    if state = state'
        then state'
        else convergence f state'

let convergedState = convergence computeIteration initialValue

Edit: added an example of use

By on 10/16/2011 5:15 PM ()

Yes, I have forgotten to return a value. It would simply require an else case:

1
2
3
4
5
6
7
8

let rec loop t =
  let nextT = computeIteration t
  if t <> nextT then
    loop nextT
  else
    nextT

let t = loop initialValue
By on 10/16/2011 5:32 PM ()

I was hoping any built-in higher-order function like a variation of fold would achieve this, but as that does not seem to be the case I defined my own function based on Ramon suggestion:

1
2
3
4
5
6
7
8

let iterateUntilConvergence iteration initialValue =
    let rec loop t = 
        let nextT = iteration t
        if t <> nextT then
            loop nextT
        else
            nextT
    loop initialValue

Thanks

By on 10/16/2011 7:32 PM ()

A fold variation, or more precisely an unfold, would probably be useful if you want to keep the successive states you go through:

1
2
3
4
5
6
7
8
9
10
11

let iterateUntilConvergence iteration initialValue =
    Seq.unfold (fun t ->
                    let nextT = iteration t
                    if t = nextT then
                        None
                    else
                        Some (nextT, nextT))
               initialValue

iterateUntilConvergence (fun x -> x / 10.) 1.
// Returns: seq [1.0; 0.1; 0.01; 0.001; ...]

An interesting point here is that the lazyness of sequences allows you to do some bookkeeping outside the function. For example, the caller can take care of checking that the sequence doesn't diverge.

Edit: the unfold should actually return nextT and not t, else it would lack the last (and most important!) element.

By on 10/17/2011 12:22 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper