DEV Community

Golden Search Algorithm in F#

Juan C LR on May 18, 2018

Start I wrote the code for the Golden Search algorithm in python for one of my university classes, I really found this method interestin...

Read full post

amieres • Sep 3 '18 • Edited

Like someone already mentioned your code is imperative, not functional.
The first clue is that functional code does not use mutability.
Your implementation is not using recursion just a loop, that is the second clue. To use recursion in F# you need to add rec before the function name, like below where it says: let rec golden ...
A functional version could look like this:

let round   (f:float) = Math.Round(f, 6)
let funcion  x        =  0.5 - (x * Math.E) ** (-x ** 2.0)
let R                 = (5.0 ** 0.5 - 1.0) / 2.0

let goldenAlgorithm limits =
    let rec golden iter (a, b) = // <--- recursive function
        if round a = round b then (iter, a, funcion a) else // <--- solution
        if funcion a > funcion b 
            then   a                       , (a + R * (b - a))
            else  (a + (1.0 - R) * (b - a)),  b
        |> golden (iter + 1)     // <--- recursive call
    golden 1 limits              // <--- initial call

goldenAlgorithm (0.0, 2.0)
|||> printfn "iteraciones: %i\nvalor en x:  %f\nvalor en f(x):  %f"

// output:
// iteraciones: 32
// valor en x:  0.223130
// valor en f(x):  -0.475414

This code demonstrates several traits of F#:

How clean and uncluttered the code is. I removed extra parenthesis to make the code more clear.
The use of the pipe (|>) and even the triple pipe! (|||>) to avoid unnecessary names
Use of tuples (and triplets).
Pattern matching. Notice how limits becomes (a, b) when calling:
- golden 1 limits

Type inference. F# is a strongly typed language like C# but you do not need to specify the types of every function or parameter, the compiler can deduced them.

Inside goldenAlgorithm is the recursive function golden of type:
int -> float * float -> (int * float * float)

It receives the number of iteration (starting with 1) and the limits a & b.
It calls itself using tail recursion until it finds a solution and returns a triplet with the total number of iterations, the solution x and the value of f(x).

My suggestion to you is to not abandon functional programming. You are just starting and the more you learn the more you are going to like it, I promise.
Your reason for sticking with OOP is mainly because that is your comfort zone right now, real growth happens when you venture out of your comfort zone.

Computer Science • May 18 '18

I really like how you approached the Golden Algorithm and how you implemented it.

Arantxa Abad • May 18 '18

Very interesting your article! Nice job implementing the Golden Algorithm!👌🏼

Anthony Lloyd • May 21 '18

You are evaluating the function too often. You should only need to evaluate once for each iteration. You can see this if you put a printfn in the function and see the repeated same calls.

Christophe Riolo • May 22 '18

This is not functional programming, you are implementing a loop and modifying variables, so it's imperative. If it were functional, you would instead use a recursive function :)