learning F# five minutes at a time

When I started working thru the ProjectEuler problems, I started out coding the solutions in C# but later switched to F#. I had wanted a reason to learn a little functional programming, and this seemed like a fun way to do it. Little did I realize what a stretch of my object oriented, imperative, mind it would be.

Since the switch to F# I would have to admit that the time-to-solution is about 1/2 learning the math and 1/2 trying to grok how things are done in F# or in functional languages in general. The leap from object thinking and imperative programming to functional is non-trivial, at least for me. It’s one thing to take C# code in your head and convert, or port, it to F# and quite another to learn the functional way of accomplishing what you have in your head. It is a frank admission of how new I am to functional concepts that the first time I tried to figure out how to create a List(Of T) in F# I couldn’t figure out the syntax because there was this other pesky List class “getting in the way” of my imperative genius! Figured I had to do some reading only to find that Lists are one of the core data structures in functional languages and entirely different than List(Of T) (and way cool by the way). In fact look up LISP “the mother of all functional” on Wikipedia and find this definition (emphasis mine):

The name LISP derives from "LISt Processing". Linked lists are one of Lisp languages' major data structures, and Lisp source code is itself made up of lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or even new domain-specific languages embedded in Lisp.

Doh!

So that may have been my lesson one in the “this is not your momma’s .NET” class. If so lesson two is shaping up to be functions themselves. Seeing that all programming languages have functions I might be forgiven for thinking that I had this one handled. However: it is one thing to say “everything is a function” and quite another to realize that every thing is a function! Some cases in point:


let x = 144

 

A value declaration is actually a function x of type unit –> int (no value in int out). Note: the term variable just doesn’t fit in a language where every thing is, by default, immutable. You can force mutability but as a quote I just heard on DotNetRocks put it so well: “every time you type the mutable keyword in F# somewhere a puppy dies”



let update = printfn "processing complete"

 

This also evaluates to a function of unit –> unit.

Something we would think of as a more traditional function might be declared as:



let f x = x+1

 

This function f can be expressed in F#-ese as int –> int. Basically it takes in an integer and returns an integer. Ho-hum. Now let’s kick it up a notch:



let f x y = x*y


This evaluates, no shocker to int –> int –> int. Notice that it is not int, int –> int. The (->) symbol is the function symbol and basically amounts to “when the function is applied to the value on the left the value on the right comes out. So, why are there two function symbols in the definition? Because there are two functions implied by f x y = x+y. The first function takes the value of x and returns a new function that will take in the value of y and return the final result (x+y). So if we were to write this in C# it might look something like this:



f_part1(x).Invoke(y)

 

So, we can actually call a function in stages, storing the midterm result of the function that needs to be called next. To show this I have a simple function in F# that computes the A value of a Pythagorean triplet. The function takes in two parameters: m & n. I can call the function on one line or only pass m on the first call then later call the function that was returned from the first partial call and now pass in n to get the final result.



let pyA m n = 
(sq m - sq n)
let partial = pyA 144
//partial is the function that was returned by partial evaluation of just the first of the two implied functions
let r = partial 12
printfn "result %d" r

 

It is interesting to take the compiled F# assembly and decompile it in Reflector to see what is going on under the hood. If you look at the C# version of the IL you see this:



[Serializable]
internal class partial@139 : FSharpFunc<int, int>
{
// Fields
[DebuggerBrowsable(DebuggerBrowsableState.Never), CompilerGenerated, DebuggerNonUserCode]
public int x;
// Methods
internal partial@139(int x)
{
this.x = x;
}
public override int Invoke(int y)
{
return Program.gcd(this.x, y);
}
}
//later the call to the function is shown as this:
int x = 0x90;
int r = new partial@139(x).Invoke(12);

 

 

So we can see a class (in the C# version) is created to store the partial result and expose the Invoke() function to complete the calculation. F# doesn’t have to jump thru these hoops, but it does help illustrate what is going in F# function evaluation. So some function rules we have gleaned:

 


    • every function takes in a value (no parameters in = a value of Unit)

 


    • every function returns a value (no return value = a value of Unit)

 


    • every function takes in only one value. What we see as multi-parameter functions are actually multiple functions chained together.

 

 

BTW: this info was gleaned from F# Survival Guide by John Puopolo with Sandy Squires. I found it at that link as a free ebook and it is a well written introduction to functional programming for the functionally challenged .NET programmer. ;-)

getting your math on

Recently I started working thru the ever growing list of cool math and algorithm based puzzles on ProjectEuler.net. Moving pretty slowly so far, but having fun learning some new things which is really the point of the exercise anyway. My basic approach so far is to digest a new puzzle and see if I can solve it based on what I already know. If I can’t then I let it steep for a while trying to figure out just what is that I don’t know I don’t know. After I have a clue what I might need to know I start Google-Binging, not for solutions but for information and explanations that will help me understand the problem and the solution. After that I need to, in most cases, code up an algorithm to solve the problem.

In searching for insights, I repeatedly come to the same sites and publications that I wanted to recommend and comment on here.

Most insightful: betterexplained.com

This is not a problem –> solution format, rather the author attempts to develop my “math intuition”. I always find a deeper understanding than I actually need to solve the current problem. I love when some light bulbs go off in previously dim corners of my mind. I found this site first when looking for a better understanding of prime numbers and how they factor in to the fabric of the universe. I have not yet ordered his book, but have read much of the content and would highly recommend it.

Most practical for the problem at hand: dr. Math (mathforum.org)

This is the problem –> solution format, and it works great for breaking down a problem and building up to the solution in a way that you come away with an understanding of how you got there, without just handing you a formula that actually answers the question. In fact, in most cases the final solution is left as an exercise to the reader once the foundation is laid. I first found the good Dr. when Google-Binging for ideas how to work through finding the number of divisors of a given number.

Best book (so far): Mathematics in 10 Lessons

This book has so not been practical for solving problems today, but has been a fun read so far that it takes math and builds it up from first principles. The stated goal of the book is to explain math for non-technical people in such a way that even an poet can at least glimpse the elegance that mathematicians see. Lofty goal and I wish him well, however the book is a fun read for the technical guy or gal who just want to fill in some gaps.

Most to be avoided: StackOverflow

As much as it grieves me to say it: while StackOverflow is a routine go-to place for programming topics, when it comes to ProjectEuler most of what I have found there have been people looking for someone to hand them the solution. What is the point of that? That’s like someone telling me how the movie is going to end. So, watch out for spoilers.

Know of other items that would be good additions? Please share.

The Blog is Dead … Long live “the Blog”

I have enjoyed blogging at weblogs.asp.net and the “boy named goo” blog. I thank them for their hosting. However, my use of that blog has really dropped off and I see traffic on that site as a whole seeming to do the same.

All that being said, the real reason ;-) to start a new blog on my own site is simply because I wanted to. I hope to be a bit more active here, keep my own bar low  for “blog worthiness” and enjoy writing more for what it is to me: a hobby and a way to process and save my pseudo-random stream of thoughts regarding development, technology and any other thing that comes to mind along the way.

About me

.NET developer in upstate NY, USA
Current focus technologies: WPF, WCF
Intrigued by: Functional programming ala F#, Code Analysis, Math
Hobbies: this blog, go figure

Month List