Thursday, April 30, 2009

Announcing the F# Users Group (Take Two)

Okay, let's try this again......


Announcing the Houston F# Users Group!!!

Our meetings will be the last Tuesday of every month. (Except the first one)

In our first meeting, we're going to get acquainted with F# and it's capabilities via a Code Kata, so bring your computer, download the CTP, and be ready to code. (Yep, still doing this.)

If you have any questions or requests, would like to speak, or would like to sponsor, please email us at: houston.fsharp@gmail.com.

Here's the info:

Date: May 12, 2009
Time: 7:00-8:30 PM.
Place: Microsoft Houston Office
Address: 2000 Sam Houston Tollway S #350
City: Houston
State: Texas
Zip: 77042

What's your function?

Friday, April 24, 2009

F# Problem 14

Euler problem 14 was probably one of the more complicated for me to figure out conceptually. I suppose I'm an FSL student (functional as a second language). Nevertheless, the solution was simpler than I first anticipated.

The solution entailed creating a function that, when unfolded, would complete the sequence specified in the problem. One issue I encountered while solving this was a simple overflow issue with my values. I had to change the basic type used to solve the problem from int to int64. The result can be calculated within a few seconds.


let seq x = 
let next x =
match x with
| 1L -> None
| _ ->
match x % 2L with
| 0L -> Some(x, x / 2L)
| _ -> Some(x, (3L * x) + 1L)

Seq.unfold next x


let s = Seq.map seq [1000000L .. -1L .. 500000L]


let result =
Seq.map (fun x -> (Seq.length x, Seq.hd x)) s
|> Seq.max_by (fun x -> fst x)
|> snd

let print = result |> printfn "%A"

Wednesday, April 15, 2009

Adventures in F#: Euler Problem 12

So the question is "What is the first triangle number to have over 500 divisors?"

My first attempt at solving this question included a brute force method of creating a sequence containing all of the potential divisors for a particular number, and then, using the modulus operator, filter this list down to only the items where the result of the modulus operation is zero. I tried to perform this on every item within the sequence of triangle numbers, but this took longer than I was willing to wait, so I started researching some math formulas.

It turns out that you can calculate the number of divisors for a particular number by using a rather simple formula. Here's an example.

Let's say that I have the number 36, and I want to find the number of divisors for this number. First, I would attempt to divide 36 by 2 evenly, which would result in 18. Next I would try to divide 18 by 2 evenly, which would result in 9. Next, I would find that 9 cannot be divided into two evenly, so I would then increase my attempt by 1 and try again, so I would try to divide 9 by 3, and I would find that it divides cleanly, resulting in 3. Finally, I would divide 3 by 3, and would return 1, at which point I would stop. All in all, this would look like this:

36 / 2 = 18
18 / 2 = 9
9 / 3 = 3
3 / 3 = 1

So, if you look at all of the divisors in this process, you would see that some of them would be repeated. Thus, I can use exponent notation to represent the number 36, as follows:

22 * 32 = 36

Now, you'll notice my exponents, 2 and 2. If I take these exponent values, add 1 and then multiply the two together, we'll find the number of possible divisors for 36:

(2 + 1) * (2 + 1) = 9

What are those 9 divisors?

1, 2, 3, 4, 6, 9, 12, 18, 36

So this is the formula for finding the number of divisors for any particular number. In F#, I wrote this as a Seq.unfold on a recursive function that would return the prime factorials for a particular number. I then skipped the first element (because the first element was always 2), and executed the Seq.count_by on the resulting function, thus returning a list of tuples where the first item in the tuple was the factorial, and the second item was the number of times that factorial appeared within the sequence. Next, I mapped a new sequence, retrieving the second value of the tuple and adding one to it, and lastly, I used Seq.reduce to find the product of all the items in the resulting sequence. The output was then the number of divisors for a particular number, x. This function was named divisorcount.

Next, I used Seq.unfold to create a lazy sequence of triangle numbers.

Lastly, I retrieved my result by calling Seq.first and testing each of the elements of the triangle number sequence to determine if the return value was over 500.

So finally, without further ado, here's my code. It returns in a little over 2 seconds.


module Problem12

let divisorcount x =
if x = 1 then 0
else
let rec div (x:int * int) =
if (fst x = 0) then None
else if (snd x = 1) then Some(0, snd x)
else match (snd x % fst x) with
| 0 -> Some(fst x, snd x / fst x)
| _ -> div (fst x + 1, snd x)
Seq.unfold (fun x ->
match (div x) with
| None -> None
| Some(o) -> Some(fst x, o)) (2, x)
|> Seq.skip 1
|> Seq.count_by (fun x -> x)
|> Seq.map (fun x -> snd x + 1)
|> Seq.reduce (fun x prod -> x * prod)


let triangles =
Seq.unfold (fun x -> Some(snd x + fst x, (snd x + fst x, snd x + 1))) (0, 1)

let result =
triangles
|> Seq.first (fun x -> if divisorcount x > 500 then Some(x) else None)
|> Option.get

let print = divisorcount 9 |> printfn "%A"

Monday, April 13, 2009

Euler Problem 11 in F#

Just finished cleaning this, and I believe this to be my best work of F# to date.

This is my answer to Euler Problem 11.


let multiply sq =
let rec multiply sq x =
match sq with
[] -> x
_ -> multiply (List.tl sq) (x * (List.hd sq))
multiply sq 1

let getNS sq x y z =
Seq.nth x sq > Seq.nth (y + z)

let getEW sq x y z =
Seq.nth (x + z) sq > Seq.nth y

let getNWSE sq x y z =
Seq.nth (x + z) sq > Seq.nth (y + z)

let getNESW sq x y z =
Seq.nth (x + z) sq > Seq.nth (y - z)

let products sq length f minX maxX minY maxY =
let xAxis = [minX .. maxX]
let yAxis = [minY .. maxY]
let lengths = [0 .. length - 1]
let mapParameters s1 f = Seq.map (fun x -> f x) s1
mapParameters xAxis (f sq)
> Seq.map_concat (mapParameters yAxis)
> Seq.map (mapParameters lengths)
> Seq.map (fun x -> Seq.to_list x > multiply)

let f = products sequence 4

let ns = f getNS 0 19 0 16
let ew = f getEW 0 16 0 19
let nwse = f getNWSE 0 16 0 16
let nesw = f getNESW 0 16 3 16

let max = [ ns; ew; nwse; nesw ]
> Seq.concat
> Seq.max


Here's a brief description of what I've done.

First, the value "sequence" is of the type seq<#seq<int>>. It contains a sequence, which itself contains a sequence of every item in every row. The outer sequence is the row, where the inner sequence is the column. To create this, I literally copied the block of text from the Euler site, and pasted it into my program as a string. I then used the following code to convert it to this structure:


let sequence = 
let split (separator:string) (s:string) =
s.Split([| separator |], StringSplitOptions.None)
let sr = new StringReader(valuesfromwebsite)
sr.ReadToEnd()
|> split Environment.NewLine
|> Seq.map (split " ")
|> Seq.map (Seq.map (Int32.Parse))


multiply - Returns the product of every item in the int list passed in.
getNS, getEW, getNWSE and getNESW - Returns a sequence containing z values from sq starting at the coordinate x, y, and moving in the direction specified by the method name (NS is "north-south", while "getNESW" is "northeast-southwest", etc).
products - Returns a sequence of integer values which are the products of executing multiply returned from the specified function (f), across the entire grid (sq) starting and ending at the specified grid coordinates, within minX, maxX, minY and maxY.
f - A partially closed method specifying the first to arguments of "products"
ns, ew, nwse, nesw - The results of calling the get* methods on the grid.
max - The maximum value from ns, ew, nwse, and nesw.

I believe this proves that F# can be most succinct in many ways than C#. Here's the C# version on Bill Wagner's blog as a comparison.

Thursday, April 9, 2009

Announcing the Houston F# Users Group! - APRIL DELAYED

EDIT: Sorry folks, looks like this is being cancelled due to rain. The Microsoft office is closed today due to flooding and a power outage. I apologize for any inconvenience, but I hope to give an update soon on when the first meeting will be.

Announcing the Houston F# Users Group!!!

Our meetings will be the last Tuesday of every month.

In our first meeting, we're going to get acquainted with F# and it's capabilities via a Code Kata, so bring your computer, download the CTP, and be ready to code.

If you have any questions or requests, would like to speak, or would like to sponsor, please email us at: houston.fsharp@gmail.com.

Here's the info:

Date: April 28, 2009
Time: 7:00-8:30 PM.
Place: Microsoft Houston Office
Address: 2000 Sam Houston Tollway S #350
City: Houston
State: Texas
Zip: 77042

What's your function?

Wednesday, April 8, 2009

Another Thing to Add to My C# Wish List

So I've been plagued by this problem lately it seems.

C# is an object oriented language. It wasn't originally built to be functional, but it now has some functional elements, such as lambda expressions and Linq. Lately, I've been learning alot about functional programming via F#. I've actually grown to love the concept of "programming without side effects" that functional programming has to offer, and I was recently working on a small bit of code that (hopefully) would encourage me more to introduce some functional concepts into my code.

Here was my first attempt:


public static class FuncExtensions
{
public static Func<T1, T3> ComposeWith<T1, T2, T3>(this Func<T1, T2> _this, Func<T2, T3> other)
{
return new Func<T1, T3>(o => other(_this(o)));
}
}

class Program
{
static void Main(string[] args)
{
new Func<DateTime, int>(GetYear).ComposeWith(ConvertToDouble)(DateTime.Now);
}

static int GetYear(DateTime dt)
{
return dt.Year;
}

static double ConvertToDouble(int value)
{
return (double)value;
}
}


Okay, so that didn't work out too well. I received the following error:

The type arguments for method
'ConsoleApplication2.FuncExtensions.ComposeWith(System.Func,
System.Func)' cannot be inferred from the usage. Try specifying the
type arguments explicitly.


Hooray. Obviously, this won't work. But my question is "why not?" I mean, after all, you can do something like this:


Func<DateTime, double> func = x => ConvertToDouble(GetYear(x));


Sure, some of you might be asking why I would even want to have a .ComposeWith method like what I defined before. Most object oriented developers would wonder the same thing, but seeing an F# equivalent (data types aside) of the code might help you understand why:

open System

let convertToDouble i = double i
let getYear (d:DateTime) = d.Year
let func = getYear >> convertToDouble
func DateTime.Now |> printfn "%f"


Now, don't get me wrong. I'm not complaining about C#, or saying that C# is an inferior language or anything like that. I typically take issue with people who start using a language and then harp on it constantly about how much they hate it. I love C#. It's what brings the bacon home, and it's an excellent general purpose language to do (almost) everything, but the future is coming, and the idea of "programming without side effects" is a very popular one in the world right now, and will probably gain even more support over the coming years. I don't want C# to turn into a functional language, but I do feel that compatibility and support for a functional programming style may be very important in the next few years.

Besides, I'm not talking about recreating the wheel here. I'm talking about generic type resolution. Type resolution is already used in delegate instance assignment ("Func<DateTime, int> func = GetYear;"), lambda expressions, and the syntax to attach event handlers to events. It would be nice to see this applied more consistently across the C# spec, namely using the same kind of type resolution with non-anonymous methods. This would allow C# methods to be treated almost like first class citizens of the type system, and would allow for a richer experience when it comes to writing code without side effects. While it's possible to code without side effects in C#, it seems as though the number of hoops one has to jump through to get there almost discourages the practice.

The above main method has to be refactored as follows in order to work properly in C#. Notice the explicit type declarations (in addition to the fact that the method is required to be wrapped in a Func<T, TResult> type in order for the extension method to work properly:


static void Main(string[] args)
{
Func<DateTime, double> func = new Func<DateTime, int>(GetYear)
.ComposeWith<DateTime, int, double>(ConvertToDouble);

Console.WriteLine(func(DateTime.Now));
}


It just seems a little kludgy from a functional programming perspective, while it seems perfectly reasonable from an object oriented perspective. After all, there's the level of abstraction of forcing a function into an object (via the Func<T, TResult> constructor), which would be consistent with the object orientation of the language, nevertheless, it'd be nice to write code that looks like this:


Func<DateTime, double> func = GetYear.ComposeWith(ConvertToDouble);

Monday, April 6, 2009

Aggravation While Registering C# Express

So I installed Visual C# Express a while back so I can get fonts and colors correct for Forum posts. Today, I started it up and got the "Registration required" dialog, which had a link to the supposed registration screen, which opened in IE with this mysterious screen:



Really? Then I found this interesting link. Aggravating indeed.

Sunday, April 5, 2009

Just Finished with ALT.NET Open Spaces

I went to the ALT.NET Open Spaces conference this weekend.

I attended several amazing sessions including one convened by Claudio Lassala on maintaining excellent coding standards in a tight economy, as well as another excellent one on "Being Agile".

I also convened a session about F#, which, much to my surprise, actually went okay, I felt like (thanks to Tim Rayburn who has several additions and clarifications to offer).

All in all the conference made me happy to be in the field I'm in, and greatly challenged me to learn more about many things. I'm definately humbled to have been spending so much time with so many who would be considered "the smartest man in the room". Thanks to Ben Scheirman for organizing, Doc List for facilitating and J Sawyer and Microsoft for providing the physical space. Thanks to all who went, and all who attended the F# (and the Linq Expressions) sessions, and I look forward to another Open Spaces event as soon as possible!