url::encode

Comments on programming, web development,
and computers by Titus Stone.

Posts tagged f

FizzBuzz in F#

If you’re not familiar with what FizzBuzz is, check out this blog post by Jeff Atwood (Coding Horror).  FizzBuzz is sort of that bare-minimum-entry-level-bar that when you can clear you know you’ve at least understood the basic grammar of a language.  Typically I find in learning languages what takes the most time is really learning the standard library and built in functions.

F# has proven to be no exception to this and even though it has the entire .NET framework library behind it, there were some quirky things there to trip me up.  A great example is the printfn function.

Consider the following, which, though it seems like a trivial bit of code is actually wrong:

let x = “Hello World”
printfn x 

Running the above will thrown an exception…

The type ‘string’ is not compatible with the type ‘Printf.TextWriterFormat<’a>’

Really?  A string can’t be printed out?  There’s a question on StackOverflow which summarizes why this happens, but the short version is that printfn expects input to be of type TextWriterFormat<T>.  Right.

So the fix for the code above would be:

let x = “Hello World”
printfn “%s” x

I’ve been trying to write FizzBuzz in F# now for a week and while I probably have had it correct for a while, the printfn issue has been throwing me off this whole time.

In any case, here is FizzBuzz in F# (where the side effect of printing has been isolated to outside of the function):

let fizzbuzz n =
    match n with
    | n when n % 15 = 0 -> “FizzBuzz”
    | n when n % 5 = 0  -> “Buzz”
    | n when n % 3 = 0  -> “Fizz”
    | _                 -> n.ToString()

[1 .. 100] |> Seq.iter(fun x -> printfn “%s” (fizzbuzz x))

Appending to a List in F#

One thing about functional languages which sounds somewhat simple at first but turns out to be more complex is immutable values.  Variables (or “values” as they’re called in F#) can’t be changed once they’ve been initialized.

let x = 2
// This isn’t allowed:
x = x + 3 

Values in F# can be thought of as an equivalent to C#’s readonly accessor.

int readonly x = 2;
// This isn’t allowed:
x += 3;

The reasons for this are beyond the scope of this blog post.  However, while the idea seems simple it contains a few “gotchas”.

One such of these is appending to a list.  In C# this is quite a common task:

List<string> names = new List<string>();
names.Add(“Bob”);

There is no such thing in F#.  Instead there is the cons operator, ::, the syntax of which is:

element :: list

The result from the above is that cons returns a new list, with the element on the left being the first item of that new list and every item which was in list following it.  (Sidenote, the F# documentation actually has this incorrect.  It’s not appended.  Too bad it’s not a wiki.)

let x = [1; 2; 3;]
let y = 0 :: x

val y : int list = [0; 1; 2; 3;]

Cons is a much better performer.  The code doesn’t have to iterate over all the list items just to add the new one.  To illustrate why this is relevant let us suppose we needed the append functionality and we were going to implement it ourself.

We could start by reversing the list, then using cons to add what we want to be the last item to the beginning.

let a = [1 .. 3]
let b = 4 :: List.rev a

val b : int list = [4; 3; 2; 1;]

This gets us halfway, because even though our data is sequenced correctly, the list is in the wrong order.  We can fix that by once again reversing b into our final list.

let a = [1 .. 3]
let b = 4 :: List.rev a
let c = List.rev b 

val c : int list [1; 2; 3; 4;]

At this point it should be obvious why there is no append operator.  Internally the language would be doing this.  You might say, “but it needs to get done, so why not just have a language construct for it?”

Let’s say we refactored the above code into a function for re-use.

let append elem list = List.rev (elem :: List.rev list)

Great, now let’s use it in some code.  Let’s say we’re using tail recursion and an accumulator to make a list of CSS vendor/webkit prefixes.

let webkitify props =
    let rec loop list acc =
        match list with
        | head :: tail -> loop tail (append (“-webkit-” + head) acc)
        | [] -> acc
    loop props []

let props = [“border-radius”; “box-shadow”;]
let prefixed = webkitify props

Making use of the append function now, how many times is List.rev being called?  Within append it’s called twice which means that our simple function to prefix CSS properties with -webkit- calls List.rev twice for every item of the list (n * 2).

That’s really inefficient.  This is likely a big reason there isn’t an append operator.  Instead a very small change could be made to the function.  First, instead of appending items to the accumulator, the cons operator could be used:

let webkitify props =
    let rec loop list acc =
        match list with
        | head :: tail -> loop tail ((“-webkit-” + head) :: acc)
        | [] -> acc
    loop props []

let props = [“border-radius”; “box-shadow”;]
let prefixed = webkitify props

Then, once the loop has run out of items to recurse through the final result (the accumulator) can be reversed once.

let webkitify props =
    let rec loop list acc =
        match list with
        | head :: tail -> loop tail ((“-webkit-” + head) :: acc)
        | [] -> List.rev acc
    loop props []

let props = [“border-radius”; “box-shadow”;]
let prefixed = webkitify props

And there you have it: Why you don’t need an list append function.

Just for clarity, the above code is just for illustration purposes.  If you really wanted to add -webkit- to a list of props you’d use List.map, which composes a new list based on a function that is applied to every list item.

List.map (fun x -> “-webkit-” + x) props

F# is a Trip (or What is Function Currying)

For developers that have been living in javaland, javascriptland, or C#land for any lengthy period of time, the first encounter with a very functional language, it’s definitely weird.  F# is Microsoft’s latest language addition to their .NET kingdom.  It’s a functional/object oriented hybrid language which leans more towards the functional side and finds it’s roots in OCaml.

Quite frankly, it has some of the coolest features you’ll find on .NET at the moment, which head and shoulders above the rest of the .NET languages is the interpreter.  Further, the integration of the interpreter with Visual Studio reminds me of a Paul Graham quote from Hackers and Painters, (paraphrased) “programming languages should be for programmers to sketch in”.

It works like this:

Highlight code you’d like to execute
Press Alt+Enter
The code runs and the result appears in a console below the code, directly in Visual Studio 

As it turns out the interactive console is also great for language exploration.  The syntax of F# is a bit more minimal than you’d expect coming from C#.  Functions are defined just like values using an = where parameters aren’t wrapped in parenthesis.

let increment x = x + 1

Running that in the interpreter returns

val increment : int -> int

Two really important things are in that line.  First, F# inferred the type.  No where in the code is int specified as the type.  F# is a strongly typed language, but it will infer the type.

The second important thing is that F# returned to us the type signature of the function.  This type signature business is reminiscent of languages like Scala and Haskell.  int -> int — It basically means one integer is inputted and one integer is outputted.

But things get more interesting.  The increment function could be given a more broad usage.

let add x y = x + y

Interpreting the new function add returns

val add : int -> int -> int

That is not what one would expect.  The way the function is written is the average developer would expect a type signature of

val add : int, int -> int

But that’s not what F# is returning.  Reading the type signature, it appears that F# is interpreting the add function as two functions which it turns out is the case.  If the lack of ()’s on the functions was odd at first, then this is part of the reason why.  For each parameter on a function, behind the scenes F# makes a new function that returns a function.  (It’s not called a “functional language” for nothin’)

Why does all of this matter however?  Is it just compiler trickery or is there any use for this?  Because F# is internally creating a function for each additional parameter past the first one, if only some of the arguments were to be passed into add, what would be returned would not be a result, but another function.

Consider

let add x y = x + y
let increment = add 1

> val increment : (int -> int)

let a = increment 2

> val a : int = 3

The type signature for increment is int -> int!  Increment is a partially applied function.  It executions some of the parameters of add.

This is function currying.

It’s a trip.