7
\$\begingroup\$

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#?

\$\endgroup\$
  • \$\begingroup\$ Is this the sort of situation that could be solved in C# via the yield keyword? \$\endgroup\$ – Dan Neely Jun 10 '13 at 17:19
  • \$\begingroup\$ @DanNeely I'm not sure what you mean. \$\endgroup\$ – Wesley Wiser Jun 10 '13 at 17:23
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – svick Jun 10 '13 at 22:14
  • \$\begingroup\$ The title of your post should be the function/purpose of your code. \$\endgroup\$ – SirPython Mar 8 '15 at 20:28
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think you need a 'rec' in there. But yes, it's probably neater. \$\endgroup\$ – mavnn Jun 10 '13 at 14:33
  • \$\begingroup\$ @mavnn You're right, I'm always forgetting rec in recursive functions. \$\endgroup\$ – svick Jun 10 '13 at 14:37
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.