WARNING! I know that F# is intended to be use in a very Functional way, however, my goal is to show its Imperative and OO language features, so it can be compared with other 19 OO languages. Said that, if you know how to do something on the examples below in a more Functional style you can add it in a comment :)

Here below a little program in F# that implements 2 classes (in fact, they are 3). There is the main class, called Fiborial (Fibo(nnacci)+(Facto)rial) that implements the

*Fibonacci*and the

*Factorial*algorithms in two ways, one

*Recursive*(using recursion) and the other

*Imperative*(using loops and states). The second class is just an instance class that does the same thing, but its there just to show the difference between static and instance classes, and finally the third one (which will not appear in other languages) is the Program class which has the static execution method "Main".

You can also find 3 more little examples at the bottom. One prints out the Factorial's Series and Fibonacci's Series, the second one just shows a class that mixes both: static and instance members, and finally the third one that uses different return types (including System.Numerics.BigInteger) for the Factorial method to compare the timing and result.

As with the previous posts, you can copy and paste the code below in your favorite IDE/Editor and start playing and learning with it. This little "working" program will teach you some more basics of the Programming Language.

There are some "comments" on the code added just to tell you what are or how are some features called. In case you want to review the theory, you can read my previous post, where I give a definition of each of the concepts mentioned on the code. You can find it here: http://carlosqt.blogspot.com/2011/01/new-series-factorial-and-fibonacci.html

In F# like in VB.NET there is a type called Module. An F# module is a grouping of F# code constructs such as types, values, function values, and code in do bindings. It is implemented as a common language runtime (CLR) class that has only static members. Normally I would only use the Module type as the first example, however, here I included both, an instance class with only Static Members and a second example using Module. The syntax for the members declaration varies so I wanted to include both even if we see a second example in the Mixing Instance and Static members program.

**The Fiborial Program (using Type = Instance Class)**

// Factorial and Fibonacci in F# namespace FiborialFs open System open System.Collections.Generic open System.Diagnostics //open System.Numerics // Instance Class // with all static members type StaticFiborial() = class // Static Field static let mutable className:string = "" // Static Constructor/Initializer(s) static do className <- "Static Constructor" static do printfn "%s" className // Static Method - Factorial Recursive // in F#: type bigint = BigInteger static member public FactorialR(n:int) : bigint = if n = 1 then bigint(1) else bigint(n) * StaticFiborial.FactorialR(n-1) // Static Method - Factorial Imperative static member public FactorialI(n:int) : bigint = let mutable res:bigint = bigint(1) for i = n downto 1 do res <- res * bigint(i) res // Static Method - Fibonacci Recursive static member public FibonacciR(n:int) : int64 = if (n < 2) then int64(1) else StaticFiborial.FibonacciR (n - 1) + StaticFiborial.FibonacciR(n - 2) // Static Method - Fibonacci Imperative static member public FibonacciI(n:int) : int64 = let mutable pre:int64 = int64(1) let mutable cur:int64 = int64(1) let mutable tmp:int64 = int64(0) for i = 2 to n do tmp <- cur + pre pre <- cur cur <- tmp cur // Static Method - Benchmarking Algorithms static member public BenchmarkAlgorithm(algorithm:int, values:list<int>) = let timer = new Stopwatch() let mutable i:int = 0 let mutable testValue:int = 1 let mutable facTimeResult:bigint = bigint(0) let mutable fibTimeResult:int64 = int64(0) // "if-elif-else" Flow Control Statement if algorithm = 1 then printfn "\nFactorial Imperative:" // "For to" Loop Statement for i = 0 to values.Length - 1 do testValue <- values.Item(i) // Taking Time timer.Start() facTimeResult <- StaticFiborial.FactorialI testValue timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed elif algorithm = 2 then printfn "\nFactorial Recursive:" // "While" Loop Statement while i < values.Length do testValue <- values.Item(i) // Taking Time timer.Start() facTimeResult <- StaticFiborial.FactorialR testValue timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed i <- i + 1 elif algorithm = 3 then printfn "\nFibonacci Imperative:" // "For in" Loop Statement for item in values do testValue <- item // Taking Time timer.Start() fibTimeResult <- StaticFiborial.FibonacciI(testValue) timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed elif algorithm = 4 then printfn "\nFibonacci Recursive:" // "For in" Loop Statement for item in values do testValue <- item // Taking Time timer.Start() fibTimeResult <- StaticFiborial.FibonacciR testValue timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed else printfn "DONG!" end // Instance Class type InstanceFiborial() = class // Instance Field let mutable className:string = "" // Instance Constructor/Initializer(s) do className <- "Instance Constructor" do printfn "%s" className // Instance Method - Factorial Recursive member public self.FactorialR(n:int) : bigint = // Calling Static Method StaticFiborial.FactorialR n // Instance Method - Factorial Imperative member public self.FactorialI(n:int) : bigint = // Calling Static Method StaticFiborial.FactorialI n // Instance Method - Fibonacci Recursive member public self.FibonacciR(n:int) : int64 = // Calling Static Method StaticFiborial.FibonacciR n // Instance Method - Factorial Imperative member public self.FibonacciI(n:int) : int64 = // Calling Static Method StaticFiborial.FibonacciI n end module Program = //printfn "%s" (Fiborial.FactorialR(40).ToString()) printfn "\nStatic Class" // Calling Instance Class with Static Methods // No instantiation needed. Calling method directly from the class printfn "FacImp(5) = %A" (StaticFiborial.FactorialI 5) printfn "FacRec(5) = %A" (StaticFiborial.FactorialR 5) printfn "FibImp(11)= %i" (StaticFiborial.FibonacciI 11) printfn "FibRec(11)= %i" (StaticFiborial.FibonacciR 11) printfn "\nInstance Class" // Calling Instance Class and Methods // Need to instantiate before using. Calling method from instantiated object let ff = new InstanceFiborial() printfn "FacImp(5) = %A" (ff.FactorialI 5) printfn "FacRec(5) = %A" (ff.FactorialR 5) printfn "FibImp(11)= %i" (ff.FibonacciI 11) printfn "FibRec(11)= %i" (ff.FibonacciR 11) // Create a (generic) list of integer values to test // From 5 to 50 by 5 let values = [5..5..50] // Benchmarking Fibonacci // 1 = Factorial Imperative StaticFiborial.BenchmarkAlgorithm (1, values) // 2 = Factorial Recursive StaticFiborial.BenchmarkAlgorithm (2, values) // Benchmarking Factorial // 3 = Fibonacci Imperative StaticFiborial.BenchmarkAlgorithm (3, values) // 4 = Fibonacci Recursive StaticFiborial.BenchmarkAlgorithm (4, values) // Stop and Exit Console.Read() |> ignore

And the Output is:

**The Fiborial Program (using Module = Static Class)**

// Factorial and Fibonacci in F# namespace FiborialFs open System open System.Collections.Generic open System.Diagnostics // Static Class module StaticFiborial = // Static Field let mutable className:string = "" // Static Constructor/Initializer(s) do className <- "Static Constructor" do printfn "%s" className // Static Method - Factorial Recursive // in F#: type bigint = BigInteger let rec FactorialR(n:int) : bigint = if n = 1 then bigint(1) else bigint(n) * FactorialR(n-1) // Static Method - Factorial Imperative let public FactorialI(n:int) : bigint = let mutable res:bigint = bigint(1) for i = n downto 1 do res <- res * bigint(i) res // Static Method - Fibonacci Recursive let rec FibonacciR(n:int) : int64 = if (n < 2) then int64(1) else FibonacciR(n - 1) + FibonacciR(n - 2) // Static Method - Fibonacci Imperative let public FibonacciI(n:int) : int64 = let mutable pre:int64 = int64(1) let mutable cur:int64 = int64(1) let mutable tmp:int64 = int64(0) for i = 2 to n do tmp <- cur + pre pre <- cur cur <- tmp cur // Static Method - Benchmarking Algorithms let public BenchmarkAlgorithm(algorithm:int, values:list<int>) = let timer = new Stopwatch() let mutable i:int = 0 let mutable testValue:int = 1 // "if-elif-else" Flow Control Statement if algorithm = 1 then printfn "\nFactorial Imperative:" // "For to" Loop Statement for i = 0 to values.Length - 1 do testValue <- values.Item(i) // Taking Time timer.Start() FactorialI testValue |> ignore timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed elif algorithm = 2 then printfn "\nFactorial Recursive:" // "While" Loop Statement while i < values.Length - 1 do testValue <- values.Item(i) // Taking Time timer.Start() FactorialR testValue |> ignore timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed i <- i + 1 elif algorithm = 3 then printfn "\nFibonacci Imperative:" // "For in" Loop Statement for item in values do testValue <- item // Taking Time timer.Start() FibonacciI testValue |> ignore timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed elif algorithm = 4 then printfn "\nFibonacci Recursive:" // "For in" Loop Statement for item in values do testValue <- item // Taking Time timer.Start() FibonacciR testValue |> ignore timer.Stop() // Getting Time printfn " (%A) = %A" testValue timer.Elapsed else printfn "DONG!" module Program = printfn "\nStatic Class" // Calling Instance Class with Static Methods // No instantiation needed. Calling method directly from the class printfn "FacImp(5) = %A" (StaticFiborial.FactorialI 5) printfn "FacRec(5) = %A" (StaticFiborial.FactorialR 5) printfn "FibImp(11)= %i" (StaticFiborial.FibonacciI 11) printfn "FibRec(11)= %i" (StaticFiborial.FibonacciR 11) // Create a (generic) list of integer values to test // From 5 to 50 by 5 let values = [5..5..50] // Benchmarking Fibonacci // 1 = Factorial Imperative StaticFiborial.BenchmarkAlgorithm(1, values); // 2 = Factorial Recursive StaticFiborial.BenchmarkAlgorithm(2, values); // Benchmarking Factorial // 3 = Fibonacci Imperative StaticFiborial.BenchmarkAlgorithm(3, values); // 4 = Fibonacci Recursive StaticFiborial.BenchmarkAlgorithm(4, values); // Stop and Exit Console.Read() |> ignore

And the Output is:

**Printing the Factorial and Fibonacci Series**

// Factorial and Fibonacci in F# namespace FiborialSeries open System open System.Text open System.Numerics // Static Class module Fiborial = // We first define the Factorial and Fibonacci methods // so we can use them after in the Series methods let rec Factorial(n:int) : bigint = if n = 1 then bigint(1) else bigint(n) * Factorial(n-1) let rec Fibonacci(n:int) : int64 = if (n < 2) then int64(1) else Fibonacci(n - 1) + Fibonacci(n - 2) // Using a StringBuilder as a list of string elements let public GetFactorialSeries(n:int): string = // Create the String that will hold the list let mutable series:StringBuilder = StringBuilder() // We begin by concatenating the number you want to calculate // in the following format: "!# =" ignore (series.Append "!") ignore (series.Append n) ignore (series.Append " = ") // We iterate backwards through the elements of the series for i = n downto 1 do // and append it to the list ignore (series.Append i) if i > 1 then ignore (series.Append " * ") else ignore (series.Append " = ") // Get the result from the Factorial Method // and append it to the end of the list ignore (series.Append(Factorial n)) // return the list as a string series.ToString() // Using a StringBuilder as a list of string elements let public GetFibonnaciSeries(n:int): string = // Create the String that will hold the list let mutable series:StringBuilder = StringBuilder() // We begin by concatenating the first 3 values which // are always constant ignore (series.Append "0, 1, 1") // Then we calculate the Fibonacci of each element // and add append it to the list for i = 2 to n do if i < n then ignore (series.Append ", ") else ignore (series.Append " = ") ignore (series.Append(Fibonacci i)) // return the list as string series.ToString() module Program = // Printing Factorial Series printfn "" printfn "%s" (Fiborial.GetFactorialSeries 5) printfn "%s" (Fiborial.GetFactorialSeries 7) printfn "%s" (Fiborial.GetFactorialSeries 9) printfn "%s" (Fiborial.GetFactorialSeries 11) printfn "%s" (Fiborial.GetFactorialSeries 40) // Printing Fibonacci Series printfn "" printfn "%s" (Fiborial.GetFibonnaciSeries 5) printfn "%s" (Fiborial.GetFibonnaciSeries 7) printfn "%s" (Fiborial.GetFibonnaciSeries 9) printfn "%s" (Fiborial.GetFibonnaciSeries 11) printfn "%s" (Fiborial.GetFibonnaciSeries 40)

And the Output is:

**Mixing Instance and Static Members in the same Class**

We can also define instance classes that have both, instance and static members such as: fields, properties, constructors, methods, etc. However, we cannot do that if the type is a Module because Module = Static Class and remember the features mentioned in the previous post:

The main features of a static class are:

- They only contain static members.
- They cannot be instantiated.
- They are sealed.
- They cannot contain Instance Constructors

namespace FiborialExtrasFs2 open System // Instance Classes can have both: static and instance members. // However, Modules (Static Classes) only allow static members to be defined. // Instance Class type Fiborial() = class // Instance Field let mutable instanceCount:int = 0 // Instance Constructor/Initializer(s) do instanceCount <- 0 do printfn "\nInstance Constructor %i" instanceCount // Static Field static let mutable staticCount:int = 0 // Static Constructor/Initializer(s) static do staticCount <- 0 static do printfn "\nStatic Constructor %i" Fiborial.StaticCount // Instance Read-Only Property member public this.InstanceCount with get() = instanceCount // Static Read-Only Property // Remeber that Properties are Methods to the CLR, so, you can also // define static properties for static fields. static member public StaticCount with get() = staticCount // Instance Method member public this.Factorial(n:int) = instanceCount <- instanceCount + 1 printfn "\nFactorial(%i)" instanceCount // Static Method static member public Fibonacci(n:int) = staticCount <- staticCount + 1 printfn "\nFibonacci(%i)" Fiborial.StaticCount end module Program = // Calling Static Constructor and Methods // No need to instantiate Fiborial.Fibonacci 5 // Calling Instance Constructor and Methods // Instance required let fib:Fiborial = new Fiborial() fib.Factorial 5 Fiborial.Fibonacci 15 fib.Factorial 5 // Calling Instance Constructor and Methods // for a second object let fib2:Fiborial = new Fiborial() fib2.Factorial 5 printfn "" // Calling Static Property printfn "Static Count = %i" Fiborial.StaticCount // Calling Instance Property of object 1 and 2 printfn "Instance 1 Count = %i" fib.InstanceCount printfn "Instance 2 Count = %i" fib2.InstanceCount

And the Output is:

**Factorial using System.Int64, System.Double, System.Numerics.BigInteger (bigint)**

The Factorial of numbers over 20 are massive!

For instance: !40 = 815915283247897734345611269596115894272000000000!

Because of this, the previous version of this program was giving the "wrong" result

!40 = -70609262346240000 when using "long" (System.Int64) type, but it was not until I did the Fiborial version in VB.NET that I realized about this faulty code, because instead of giving me a wrong value, VB.NET execution thrown an Overflow Exception when using the "Long" (System.Int64) type.

My first idea was to use ulong and ULong, but both failed for "big" numbers. I then used Double (double floating point) type and got no more exception/wrong result. The result of the factorial was now correct !40 = 1.1962222086548E+56, but still I wanted to show the Integer value of it, so I did some research and found that there is a new System.Numerics.BigInteger class in the .NET Framework 4.0. Adding the reference to the project and using this new class as the return type of the Factorial methods, I was able to get the result I was expecting.

!40 = 815915283247897734345611269596115894272000000000

What I also found was that using different types change the time the algorithm takes to finish:

System.Int64 < System.Double < System.Numerics.BigInteger

Almost by double!

To illustrate what I just said, lets have a look at the following code and the output we get.

open System open System.Diagnostics // Long Factorial let rec FactorialInt64(n:int): int64 = match n with | 1 -> int64(1) | n -> int64(n) * FactorialInt64(n - 1) // Double Factorial let rec FactorialDouble(n:int): double = match n with | 1 -> double(1) | n -> double(n) * FactorialDouble(n - 1) // BigInteger Factorial let rec FactorialBigInteger(n:int): bigint = match n with | 1 -> bigint(1) | n -> bigint(n) * FactorialBigInteger(n - 1) let timer:Stopwatch = new Stopwatch() let mutable facIntResult:int64 = int64(0) let mutable facDblResult:double = double(0) let mutable facBigResult:bigint = bigint(0) let values:list<int> = [5..5..50] printfn "\nFactorial using Int64" // Benchmark Factorial using Int64 for i in values do timer.Start() facIntResult <- FactorialInt64(i) timer.Stop() printfn "(%i) = %A : %i" i timer.Elapsed facIntResult printfn "\nFactorial using Double" // Benchmark Factorial using Double for i in values do timer.Start() facDblResult <- FactorialDouble(i) timer.Stop() printfn "(%i) = %A : %E" i timer.Elapsed facDblResult printfn "\nFactorial using BigInteger" // Benchmark Factorial using Double for i in values do timer.Start() facBigResult <- FactorialBigInteger(i) timer.Stop() printfn "(%i) = %A : %A" i timer.Elapsed facBigResult

NOTE: you DONT need to manually add a reference to the System.Numerics.dll assembly to your project because F# already adds it for you. In fact you don't need to use BigInteger, but bigint which is a type bigint = BigInteger.

And the Output is:

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)

ReplyDeletelet factorial n = let m = bigint n in [1 .. n] |> Seq.reduce ( * )

that factorial should be:

ReplyDeletelet factorial n = [1I .. (bigint n)] |> Seq.reduce ( * )

Thanks Daniel

ReplyDeleteI will add a section with examples people give in the comments to compare time and syntax.

You really should try Daniel's implementations - your recursive forms are not tail recursive and this will drag down performance significantly.

ReplyDeleteThanks James,

DeleteI will definitively do something with those examples. Maybe a new post once I finish with the Factorial and Fibonacci series (just 2 more)