# What's the most idiomatic way to call a function an arbitrary number of times with the previous result?

Basically I have a function of the type 'a -> 'a (an optimization function on a AST) and I want to call it (passing the previous result) until it returns the same thing as the input.

Right now I have this:

let performOptimizations ast =
Seq.initInfinite (fun _ -> 0)
|> Seq.scan (fun last _ -> optimizeAst last) ast
|> Seq.pairwise
|> Seq.find (fun (first, second) -> first = second)
|> fst


This seems really convoluted because it is created an infinite sequence of ints just so that the scan will continue until the ast is no longer modified. I realized that I could also do something like this:

let performOptimizations ast =
let mutable newAst = optimizeAst ast
let mutable lastAst = ast
while newAst <> lastAst do
lastAst <- newAst
newAst <- optimizeAst newAst

newAst


However, I would prefer to avoid mutation.

What's the functional, idiomatic way of doing this in F#?

• Is this the sort of situation that could be solved in C# via the yield keyword? – Dan Is Fiddling By Firelight Jun 10 '13 at 17:19
• @DanNeely I'm not sure what you mean. – Wesley Wiser Jun 10 '13 at 17:23
• @DanNeely I don't think so. The final result here isn't a collection, it's a single item. The usual way to solve this in C# would be to use something like the while loop in the question. – svick Jun 10 '13 at 22:14
• The title of your post should be the function/purpose of your code. – SirPython Mar 8 '15 at 20:28

I general, I agree with what mavnn said in his answer, I just think the function can be written in a simpler way:

let rec performOptimizations ast =
let optimized = optimizeAst ast
if ast = optimized then
ast
else
performOptimizations optimized


This method also sounds like a good candidate for making it more generic, something like:

let rec doWhileNotSame seed getNextValue =
let nextValue = getNextValue seed
if seed = nextValue then
seed
else
doWhileNotSame nextValue getNextValue

• I think you need a 'rec' in there. But yes, it's probably neater. – mavnn Jun 10 '13 at 14:33
• @mavnn You're right, I'm always forgetting rec in recursive functions. – svick Jun 10 '13 at 14:37

F# supports tail call recursion.

Your algorithm would seem a perfect candidate for the approach, something along the lines of:

let performOp ast =
let rec inner lastAst newAst =
if lastAst = newAst then
lastAst
else
inner newAst (optimizeAst newAst)
inner ast (optimizeAst ast)


By default tail call optimization is turned off in Debug compiles to ensure you get full stack traces in the case of an exception in the recursive function. If you are debugging with large asts you can override this option in the project properties.

I know, this is an old topic. Since I don't see my approach, I am still going to submit it.

I use a kind of a fixed point operator fix:

let rec fix f x = let y= f x in if x=y then x else fix f y


then the function

fix ast


will apply ast as many times to the argument as needed (or it will run forever if such an argument isn't hit). However, with this approach one has some flexibility with the "break-condition", maybe something along the lines.

let rec fix f condition x =
if condition f x then x
else fix f condition (f x)


where condition is of type ('a -> 'a) -> 'a -> bool.