In object oriented programming, a class is a blueprint to create instances of a type.

  1: // show me all the blueprints -- reflect over some .NET libs
  2: open System
  3: open System.IO
  4: open System.Reflection
  5: 
  6: // some reflection helpers
  7: module Reflect =
  8:   type Info =
  9:     | Types        of Type
 10:     | Fields       of FieldInfo
 11:     | Properties   of PropertyInfo
 12:     | Events       of EventInfo
 13:     | Methods      of MethodInfo
 14:     | Constructors of ConstructorInfo
 15: 
 16:   let getTypes (x : string) = 
 17:     let asm = Assembly.LoadFrom(x) in asm.GetTypes()
 18:     |> Seq.map (fun x -> Types x)
 19: 
 20:   let getType ( x : obj ) : Type =
 21:     let y = x.GetType() in y
 22: 
 23:   let getFields (x : obj) (flags : BindingFlags) =
 24:     let t = getType x in t.GetFields flags 
 25:     |> Seq.map (fun x -> Fields x)
 26: 
 27:   let getProperties (x : obj) (flags : BindingFlags) =
 28:     let t = getType x in t.GetProperties flags
 29:     |> Seq.map (fun x -> Properties x)
 30: 
 31:   let getEvents (x : obj) (flags : BindingFlags) =
 32:     let t = getType x in t.GetEvents flags
 33:     |> Seq.map (fun x -> Events x)
 34: 
 35:   let getMethods (x : obj) (flags : BindingFlags) =
 36:     let t = getType x in t.GetMethods flags
 37:     |> Seq.map (fun x -> Methods x)
 38: 
 39:   let getConstructors (x : obj) (flags : BindingFlags) =
 40:     let t = getType x in t.GetConstructors flags
 41:     |> Seq.map (fun x -> Constructors x)
 42: 
 43:   let getMembers fflags pflags eflags mflags cflags (x : obj) = seq {
 44:     yield! getFields       x fflags
 45:     yield! getProperties   x pflags
 46:     yield! getEvents       x eflags
 47:     yield! getMethods      x mflags
 48:     yield! getConstructors x cflags }
 49: 
 50: // I don't want to type these over and over again
 51: let Static = 
 52:   (   BindingFlags.Static   
 53:   ||| BindingFlags.NonPublic 
 54:   ||| BindingFlags.Public)
 55: let Instance = 
 56:   (   BindingFlags.Instance 
 57:   ||| BindingFlags.NonPublic 
 58:   ||| BindingFlags.Public)
 59: let All = 
 60:   (   BindingFlags.Static   
 61:   ||| BindingFlags.Instance  
 62:   ||| BindingFlags.NonPublic 
 63:   ||| BindingFlags.Public)
 64: 
 65: // A sequence of types from FSharp.Core.dll
 66: let fscore = 
 67:   Reflect.getTypes (@"C:\Program Files (x86)\FSharp-2.0.0.0\bin\FSharp.Core.dll")
 68: 
 69: // Printing all members
 70: fscore
 71: |> Seq.map(fun x ->
 72:   match x with
 73:   | Reflect.Types x -> (Reflect.getMembers All All All All All x),(x.Name)
 74:   | _ -> failwith "wrong type")
 75: |> Seq.iter (fun (x,y) ->
 76:   Seq.iter (fun x ->
 77:     match x with
 78:     | Reflect.Types        x -> printfn "%s\tType: %s"        y <| x.Name
 79:     | Reflect.Fields       x -> printfn "%s\tField: %s"       y <| x.Name
 80:     | Reflect.Properties   x -> printfn "%s\tProperty: %s"    y <| x.Name
 81:     | Reflect.Events       x -> printfn "%s\tEvent: %s"       y <| x.Name
 82:     | Reflect.Methods      x -> printfn "%s\tMethod: %s"      y <| x.Name
 83:     | Reflect.Constructors x -> printfn "%s\tConstructor: %s" y <| x.Name) x )

That should keep your FSI busy for a moment while you read the rest of this post. It’s not a secret that there are quite a few types available to us in .NET and we get a handful or two more when we reference FSharp.Core.dll. A type is just data, and alone it is boring if not a bit useless. Here’s the interesting part though: In F#, functions are types. These function types are still data. To do something interesting, all we need is to give a function some data, and it gives us some new data in return. The data we give to our function can be an Object(s) and/or another function(s), as both are just data.

F# is a functional programming language. When we say ‘functional’ we are talking about a Function (computer science) as much as we’re talking about a Function (mathematics). A function in F# straddles these two definitions quite nicely. No doubt you are familiar with the computer science definition of a Function / Method / Procedure / Subroutine. For this reason I want you to fearlessly broach the mathematical side of F# functions. Or, if you are mathematically inclined but haven’t used F# for mathematical programming… Have a look.

Let’s take a short look at the “anatomy” of an F# function. Really, this isn’t going to be mathematically rigorous. I’m not a mathematician, I’m a programmer. I’m not patient enough to do any hand holding throughout, so I’m just going to show you (unless you already know) the names for things so when we bring them up in later posts (about Gang of Four OOP Design Patterns from the perspective of Functional Programing) we won’t have to stop and explain what they mean.

 84: // Function
 85: let sum   a b = a + b   // val add   : int -> int -> int
 86: let mul   a b = a * b   // val mul   : int -> int -> int
 87: let sqr   n   = mul n n // val sqr   : int -> int

A function relates each element of a “set” with exactly one element of another “set”, which could possibly be the same “set”. Maybe, as programmers, we can get away with saying “class”. I think you will also find that the term ‘relates’ is more useful in the long run over a word like ‘transforms’, at least until later on…

There is a kind of notation we can use to reason about the type of a function in F#. It is called arrow notation. It is easy to read, and after a few exercises and expanding our vocabulary a little it becomes pretty easy to manipulate. To show this off I’m going to need a function that takes a lot of parameters. Are you familiar with the Drake equation? (a more informative and animated infographic is just as entertaining to watch)

 88: // functions are actually curried
 89: let drakeEq R fp ne fl fi fc L : float = 
 90:   (float R) * fp * ne * fl * fi * fc * (float L)

There are a lot of Objects and Arrows in this particular function’s signature. Good, because I want to show you what a curried function actually means. Place your mouse cursor over the function name drakeEq on line 89 and observe the signature:

\(drakeEq : int \rightarrow float \rightarrow float \rightarrow float \rightarrow float \rightarrow int \rightarrow float\)

This arrow notation may seem arcane to you, but it is necessary due to the fact that function parameters are implicitly curried. This signature corresponds with the lambda beginning at line 92 and ending at line 98. This arrow notation may seem arcane to you, but it is extremely helpful in F# due to the fact that function parameters are implicitly curried. You can use this feature of F# to construct higher order functions. You can pick-apart the parameters and wedge functions into them as long as the algebraic type signatures line up. Here’s how you read that signature: drakeEq is a function that takes an int and a float and a float and a float and a float and an int and returns a float. When reading function signatures, the last type to appear is the type being returned by the function. Any functions taking other functions as parameters will express that in their type signatures by surrounding the input function with parenthesis. For the drakeEq, though, here is what is (sort of) happening behind the scenes:

 91: // like this:
 92: (fun (R  : int  ) ->
 93:  (fun (fp : float) ->
 94:   (fun (ne : float) ->
 95:    (fun (fl : float) ->
 96:     (fun (fi : float) ->
 97:      (fun (fc : float) ->
 98:       (fun (L  : int  ) -> (float R) * fp * ne * fl * fi * fc * (float L))))))))

Hmm… This looks like a bunch of nested lambda expressions. In fact, all but the outer-most of these anonymous functions is wrapped by an outer lambda. This has the same recursive structure as a Linked List does, with the exception that the input values to each one of the lambdas have closure in the nested lambdas.

 99: // recursive data type
100: type 'a LinkedList =
101:   | Empty                                  // aka: nil
102:   | Element of    'a      * 'a LinkedList  // aka: cons
103:               // aka: car   // aka: cdr

Remember that functions are data too, so this means we can recursively deconstruct functions, or recursively construct them and hand them out to be evaluated later, as we do in Continuation Passing Style. We could specify the drakeEq like so:

104: let drakeEq' (R,fp,ne,fl,fi,fc,L) : float =
105:   (float R) * fp * ne * fl * fi * fc * (float L)

This changes the signature to:

\(drakeEq' : int * float * float * float * float * float * int \rightarrow float \)

And we lose the ability to curry the function on each of the inputs. Because the notation (value1,value2) represents a tuple in F# and a tuple is essentially just one composite value. So, the real power behind currying can be harnessed in this way, as well as; Higher Order Functions (HoF), Partial Application, and continuation passing style, for example. Let’s take a look at each one of those concepts.

106: let xs = Element(1, Element(2, Element(3,Empty)))
107: // these signatures compose
108: [1..9]               // int list is usable as an seq<'a>
109: ( |> )               // ('a -> ('a -> 'b) -> 'b)
110: (Seq.filter)         // (('a -> bool) -> seq<'a> -> seq<'a>)
111: (fun x -> x % 3 = 0) // (int -> bool)
112: 
113: // into this higher order function
114: [1..9] |> Seq.filter (fun x -> x % 3 = 0)

The type ‘a is special and stands for a generic type. The type ‘b stands for a generic type that isn’t necessarily the same type as ‘a. The evaluation order for line 114 considers ( |> ) first. The job of ( |> ) is to put the expression on the left into the expression on the right. When the type is evaluated it is inferred to be the type int. So our ‘a here is really standing for int now. The next part that is evaluated is the lambda. Easy to see that its type is (int -> bool) and since ‘a stands for int, it fits nicely into the first parameter of Seq.filter. Seq.filter enumerates our list applying the lambda to each element and returns to us a seq<int> containing the elements [3;6;9].

The compiled representation of an F# function is an instance of the Microsoft.FSharp.FastFunc class. F# functions are not delegates.

116: // partial application
117: let next      = sum 1                         // val next  : int -> int
118: let twice     = mul 2                         // val twice : int -> int
119: let x = let n = 4 in twice <| sqr n + next n  // val it    : int = 42

F# programmers love composability, though these trivial examples do little to expose the great usefulness of these features. To make the most of these features, as you gain experience, you need to become comfortable with the functional arrow notation. Look, you don’t have to be good at math to make use of it, you really only need to know the rules for moving symbols around.

121: // an example of continuation passing style using a (foldBack) catamorphism
122: let foldr f acc xs =
123:   let rec foldr xs k =
124:     match xs with
125:     | Element(x,xs) -> foldr xs (fun racc -> k (f x racc))
126:     | Empty         -> k acc
127:   foldr xs id
128: 
129: // the opposite of foldr (no continuation passing is necessary)
130: let rec foldl f acc xs =
131:   match xs with
132:   | Element(x,xs) -> foldl f (f acc x) xs
133:   | Empty         -> acc
134: 
135: // some higher order functions implemented in terms of folds
136: let identity  xs = foldr (fun x xs -> Element(x,xs)) (Empty) xs
137: let reverse   xs = foldl (fun xs x -> Element(x,xs)) (Empty) xs
138: let length    xs = foldl (fun xs _ -> 1 + xs)           0    xs
139: let summation xs = foldl (fun xs x -> x + xs)           0    xs
140: let product   xs = foldl (fun xs x -> x * xs)           1    xs

Folding is pretty useful and goes a long way to creating elegant and composable programs. You can also call folding a “catamorphism”. Folding is easier to say, but catamorphism is a lot more meaningful, and more general. By the way, the dual of any theorem is also a theorem. If you’ve been using the intellisense on the code to view the signatures of these functions you will notice that a cataomorphism on our LinkedList type is:

\(LinkedList<'a> \rightarrow ‘b\)

To “dualize” this we simply turn the arrow around.

\(‘a \rightarrow LinkedList<'b>\)

Here, we don’t have to worry about the discrepancy between the positions of ‘a and ‘b. They’re equally generic. Intellisense will typically report them in alphabetical order.

142: // the dual of folding,  unfolding
143: let rec unfold unspool finished x = 
144:   match x with
145:   | x when finished x -> Empty
146:   | _ -> let a,y = unspool x in Element(a,unfold unspool finished y)
147: 
148: let fibUntil until = 
149:   unfold (fun x -> let b' = (fst x + snd x) in (b',(snd x, b')))
150:          (fun x -> snd x >= until )
151:          (0,1)
152: 
153: fibUntil 34
154: 
155: let fibs (x : int)  =
156:   let x = ref x in
157:   unfold ( fun x   -> let b' = (fst x + snd x) in (b',(snd x, b')))
158:          ((fun x _ -> if !x = 0 then    true
159:                       else x := !x - 1; false ) <| x)
160:          (0,1)
161: 
162: fibs 10

Unfolding is also useful and goes just as far toward creating elegant and composable programs. You can also call unfolding an “anamorphism”. However, I should let you know that my sloppy blog solutions are no match for what F# provides out of the box. I just wanted an anamorphism over our LinkedList type we defined above. LinkedList already comes with F# as List and a lazy version, LazyList, is available in PowerPack. When unfolding though, we don’t know when we’re going to stop so it is definitely better to use a lazy data structure. F# gives us the Seq module that works with any IEnumerable:

164: // best to use whats already in the framework
165: let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
166: fibonacci |> Seq.nth 10000

Mathematicians don’t like a lot of cruft in their notation, especially when simple symbols will do the trick. A function is like a machine that relates an input to an output. Another way of looking at a function is a sort of dictionary. Where the input is the key, and the output is the value. In fact, I really like that way of looking at things. You cannot have the same key mapping to different values. Neither may a function relate its input to different values (unless these values have been tuple’d into one value!). Notice the similarity here between the F# function signatures:

Signature:
\(f : {N} \rightarrow {N}\)

Implementation:
\(f : x \mapsto x^2\)

Functions usually have a name, but like F# you don’t have to necessarily give them one: \(x = n^2\). There is still an input n and an output y and the relation of squaring.

\(f(x) = x^2\)

We read this as “f of x equals x squared”. Of course x is definately numerical in nature, so in F# it would be like: let inline f (x : ^x) = x * x. A bit more wordy, but computers aren’t as smart as mathematicians so we have to clue them in that ^x here needs to be statically resolved.

Functions have formal rules. It must work every time for every possible input value. It must give the same result for the same input value every time. You can only have one relation for each input value. One-to-many relations are not O.K., but many-to-one relations are just fine. If a relationship doesn’t follow these rules, then it is not a function. These rules are very important in the long run for making educated assumptions regarding the interaction, or rather, the composition of functions in a complex system.

The Domain of a function is it’s spectrum of input. The Codomain is its spectrum of output. The Range of a function is some subset of the codomain, for which the domain relates. A Relationship is the operation performed on the domain to give us a value in the codomain. For instance, using the relation \(x^2\) in the domain of Integers (\({Z}\) then we know that \(f : {Z} \rightarrow {Z}\) is the signature of our function. The \(\mapsto\) in \(f : x \mapsto x^2\) is called “maps to” and maps an integer to another integer. Or, if you prefer to imagine it as a table lookup, it “looks up” an integer value using an integer key. Though the domain and codomain are the same sets, the range of our relation \(x^2\) is a subset of \({Z}\). You do the math on that one.

Functions can come in pieces, called piecewise functions. F# can do piecewise functions using pattern matching syntax. Have a look at the foldr and foldl implementations again. Sometimes you’re matching on the quality of a type instead of a type itself… in that case pattern matching accompanied by Active Patterns will give you the same semantics as piecewise functions in mathematics.

BONUS:

I can imagine a situation where we would want to take from the domain of our Drake equation the most educated guesses we have available to restrict the range to some known quantity. For instance we know for certain there is 1 civilization in our galaxy capable of radio astronomy. Maybe there is more than one educated guess for each of the drake equation’s parameters. There’s really no use in bickering about which one is the better one… after all they’re both estimates and outright guesses, right? We do have a pretty good guess for R, and we can say that N is definately equal to 1. What could the others be? Enter: Solver Foundation.

167: #I "lib"
168: #r "Microsoft.Solver.Foundation.dll"
169: open Microsoft.SolverFoundation.Common
170: open Microsoft.SolverFoundation.Solvers
171: open Microsoft.SolverFoundation.Services
172: 
173: // This wrapper comes with Solver Foundation in the F# Samples
174: #load "SfsWrapper.fsx"
175: open SfsWrapper
176: 
177: // these measure types aren't necessary for this example but were 
178: // used to make it easier to keep track of what the variables in the 
179: // drake equation stand for.
180: [<Measure>] type Year
181: [<Measure>] type Star
182: [<Measure>] type Planet
183: [<Measure>] type LifeCapible = Planet / Planet / Star
184: [<Measure>] type Life = Planet / LifeCapible
185: [<Measure>] type IntelligentLife = Planet / Life
186: [<Measure>] type CommunicatingIntelligentLife = Planet / IntelligentLife
187: [<Measure>] type Civilization
188: 
189: let context = SolverContext.GetContext()
190: let drake   = SfsModel(context)
191: 
192: // optimization variables
193: let R  = drake.CreateRealVariable<Star/Year>()
194: let fp = drake.CreateRealVariable<Planet/Star>()
195: let ne = drake.CreateRealVariable<LifeCapible>()
196: let fl = drake.CreateRealVariable<Life>()
197: let fi = drake.CreateRealVariable<IntelligentLife>()
198: let fc = drake.CreateRealVariable<CommunicatingIntelligentLife>()
199: let L  = drake.CreateRealVariable<Year>()
200: let N  = drake.CreateRealVariable<CommunicatingIntelligentLife 
201:                                     IntelligentLife Life 
202:                                       LifeCapible Planet>()
203: 
204: // none of these should dip below 0.0
205: drake.AddConstraints [|
206:   0.0<_> <<== R;  0.0<_> <<== fp; 0.0<_> <<== ne; 0.0<_> <<== fl;
207:   0.0<_> <<== fi; 0.0<_> <<== fc; 0.0<_> <<== L;  1.0<_> ==== N
208: |]
209: 
210: let cR  = drake.AddConstraint ( R  ====   7.0<_> )
211: let cfp = drake.AddConstraint ( fp <<==   8.0<_> )
212: let cne = drake.AddConstraint ( ne <<==   1.0<_> )
213: let cfl = drake.AddConstraint ( fl <<==   1.0<_> )
214: let cfi = drake.AddConstraint ( fi <<==   1.0<_> )
215: let cfc = drake.AddConstraint ( fc <<==   1.0<_> )
216: let cL  = drake.AddConstraint ( L  <<== 304.0<_> )
217: let cN  = drake.AddConstraint ( N  ==== R * fp * ne * fl * fi * fc * L )
218: 
219: let minimumLifeCapible = drake.AddGoal( GoalKind.Minimize,
220:                                         R * fp * ne * fl * fi * fc * L )
221: 
222: //drake.RemoveGoal(minimumLifeCapible)
223: let solution = drake.Solve(LocalSearch)
224: 
225: // see the results
226: // val it : SolverQuality = LocalOptimal
227: solution.Quality
228: // val it : R  = 7.0
229: R.Value  |> float
230: // val it : fp = 4.341172079
231: fp.Value |> float
232: // val it : ne = 0.06266237088
233: ne.Value |> float
234: // val it : fl = 0.0303299242
235: fl.Value |> float
236: // val it : fi = 0.1318182999
237: fi.Value |> float
238: // val it : fc = 0.7418663017
239: fc.Value |> float
240: // val it : L  = 177.0579602
241: L.Value  |> float
242: // val it : N  = 0.99999999
243: N.Value  |> floatF# Web Snippets

Solver Foundation is really fun to play with and the samples that come with it are great! But I’ll save a post on it for later. F# 3.0 will ship with a feature called “Type Providers” which will make it trivial to retrieve values for these variables from existing data sources in the cloud.