Do Loop Until You Die

Getting Source Code into Your Blog

I have always written my blogs using Microsoft Word. A quick look around the internet and the vitriolic hatred of Word as a blog writing tool becomes apparent. But I try not to let popular opinion affect my technology choices, and instead focus on what works for me.

The blogging workflow for Word was easy. Write the entry, pasting source code straight from visual studio as I went along. Save as hmtl filtered. Copy the html output into wordpress, and voila, shiny new blog entry.

I don’t know if it was the upgrade to latest version of wordpress, maybe an upgrade to the theme i am using, but my old workflow no longer worked. The problem involved additional spacing in all the paragraph tags generated by word. I fiddled, I faddled, but no matter how i massaged the html i just couldn’t get the source code to look right. So instead of blasting the evil empires worthless text editor on slashdot, i simply started looking for a new workflow that works for me.

I had tried live writer before and had found it a very capable blog editor, however, the ease of copying source code straight from visual studio was no longer an option. A quick look at what others were doing turned up the wordpress option, the live writer option, and the visual studio option.

The wordpress option uses javascript to format your code when the page is loaded in the browser. I would call this delayed syntax highlighting, since it waits until the last possible moment to actually format your code. The downside of this is the highlighting does not follow your visual studio settings, and only supports languages that have javascipt provider written for them. Since i write a decent amount of f#, which is not supported, this route was a non starter.

I tried the live writer option in my last blog post. It works reasonably well, but i got continually frustrated with having to resize my code blocks because of a large space between the code block and the next line of text. And because it uses pre tags there is not direct access to the code from the editor. The nail in the coffin though was when i checked the feed in ie, firefox, chrome, and google reader, every client rendered the spacing different with google reader adding a huge number of spaces after the code block.

So for this blog entry i’m using the visual studio option. The only thing that stopped me from using CopySourceAsHtml last time was it did not support Visual Studio 2010. Luckily, adding support is rather a trivial with a few hickups along the way.

First we add an xml addin description for Visual Studio 2010. Next we update the installer to build an addin directory for Visual Studio 2010. Tweak the user interface of the installer and we’ve got a 2010 installer except

The command bars api is busted in Beta 1. Which means you will have to assign shortcut keys to the commands.

And to get rid of the error when visual studio 2010 loads, we simply comment out the code that adds the menu to the command bars. And for all our hard work we can now post the following to our blog form visual studio 2010.

var rect = RectangleFluent.Create()
    .SetColor(Color.AliceBlue)
    .SetHeight(16)
    .SetLength(16);

Dim rect = RectangleFluent.Create() _
    .SetColor(Color.AliceBlue) _
    .SetHeight(16) _
    .SetLength(16)

let rect = RectangleFluent.Create().SetColor(Color.AliceBlue).SetHeight(16).SetLength(16)

I’ll be interested to see how the code renders in the various clients. You can download a modified installer here that supports Visual Studio 2010. Hopefully, the comand bar api will be fixed for beta 2.

Consuming Fluent Interfaces

I guess I’ve been living under a rock for the last year, but I’ve only recently started using a couple of fluent APIs. A quick search of the internet and fluent APIs are popping up for everything from twitter to orm mapping to dependency injection.

So far I buy into the advantages of fluent interfaces over traditional property setting and long lists of function parameters. I find the consuming code easier to read, more intentful, easier to mix and match behavior, and yes, more fluid.

So let’s throw together a trivial fluent interface and examine how we consume it from a couple of different .Net languages.

public interface IRectangleFluent
{
    IRectangleFluent SetHeight(int height);
    IRectangleFluent SetLength(int length);
    IRectangleFluent SetColor(Color color);
}

public class RectangleFluent : IRectangleFluent
{
    Color color;
    int height;
    int length;

    public RectangleFluent() { }

    public IRectangleFluent SetColor(Color color)
    {
        this.color = color;
        return this;
    }

    public IRectangleFluent SetHeight(int height)
    {
        this.height = height;
        return this;
    }

    public IRectangleFluent SetLength(int length)
    {
        this.length = length;
        return this;
    }
}

Basically, instead of properties, we’re using methods to return the current context for the next call in the method chain. To consume our fluent interface from c# we simply write

var rect = new RectangleFluent()
    .SetColor(Color.AliceBlue)
    .SetHeight(16)
    .SetLength(16);

From VB we write

Dim rect = (New RectangleFluent()) _
            .SetColor(Color.AliceBlue) _
            .SetHeight(16) _
            .SetLength(16)

Not quite as pretty, as we have to wrap the construction of our instance in an additional set of parenthesis, and of course we have the infamous line continuations. I could have sworn i read something about line continuations in VB being smarter, i guess not smart enough to realize we want to call our method on the next line.

The additional set of parenthesis are needed in f# as well

let rect = (new RectangleFluent()).SetColor(Color.AliceBlue).SetHeight(16).SetLength(16)

although we can write

let rect = RectangleFluent().SetColor(Color.AliceBlue).SetHeight(16).SetLength(16)

which I really don’t like as it’s very difficult to tell whether an object is being created or a static method is being called.

Luckily, a common practice in fluent libraries is to use a static factory method for creation of object instances, which standardizes the construction of the instance across all three languages. Adding a factory method to our definition and changing the constructor to private

private RectangleFluent() { }

public static IRectangleFluent Create()
{
    return new RectangleFluent();
}

allows us to write

var rect = RectangleFluent.Create()
    .SetColor(Color.AliceBlue)
    .SetHeight(16)
    .SetLength(16);

Dim rect = RectangleFluent.Create() _
    .SetColor(Color.AliceBlue) _
    .SetHeight(16) _
    .SetLength(16)

let rect = RectangleFluent.Create().SetColor(Color.AliceBlue).SetHeight(16).SetLength(16)

The c# and vb allow for very readable consuming code, but I’m embarrassed to admit I can’t figure out how to format the f# code for readability. I’ve looked everywhere and I can’t find an example of calling a method in a method chain on the next line, at least VB’s unsmart line continuation characters let us do it. With the abundance of fluent APIs on the horizon, and f# being pitched as the hot new language for VS 2010, I’m sure I’m overlooking something obvious.

Hide your Design Decisions with Abstract Data Types

We all know the importance of protecting consumers of our libraries from our design decisions. In object oriented programming we refer to this protection mechanism as encapsulation or black box design. Functional programming allows us to achieve the same goal under a slightly different guise, abstract data types.

Abstract Data Types in ML

The first way to build an abstract data type in ML is to define the data type using abstype instead of datatype.

abstype ‘a Set = set of ‘a list

with …

Here we’ve chosen to use a list as the underlying store for our Set data type. As long as we keep the “interface” the same, we are free to choose a different design for the underlying store. The abstype keyword hides the set data constructor from the consumer, preventing sets being constructed from lists.

The abstype keyword may seem convenient, however, modern ML programs rarely use it. Abstype has been deprecated in favor of opaque signature ascription.

signature SetSig =

sig

type ‘a set

val empty : ‘a set

val singleton : ‘a -> ‘a set

end;

structure Set :> SetSig =

struct

type ‘a set = ‘a list;

val empty = [];

fun singleton a = [a]

end;

The Set structure is similar to a typeclass where we’ve provided an implementation for SetSig using lists. We are free to provide an implementation using binary trees and change the implementation Set will use under the covers.

signature SetSig = …

structure ListSet :> SetSig = …

structure TreeSet :> SetSig = …

Set = TreeSet

The consumer remains unaware that we’re now using a binary tree instead of a list to represent sets.

Abstract Data Types in F#

There is no abstype keyword in F# so we’ll use opaque signature ascription to achieve our data abstraction.

module SetSig

type ‘a set

val internal toList : ‘a set -> ‘a list

val empty : ‘a set

val singleton : ‘a -> ‘a set

module SetSig

type ‘a set = internal Set of ‘a list

let toList s = match s with Set lst -> lst

let empty = Set[]

let is_empty s = List.length(toList s) = 0

let singleton x = Set[x]

There are a couple of problems with the F# implementation.

The fist is just annoying. We use the module keyword for both the signature and the implementation in F#. The signature must go into a file with the fsi extension and the implementation in a file with an fs extension. The system is similar to header files in c and went out of favor around the time Java was introduced. Hopefully, the day will come when the signature and the many implementations of the signature can be declared in the same file.

The second is limiting. Notice how we’ve had to declare a toList method to convert our set to a list? This limits our signature to lists. Without the concept of functors we have no way to vary our implementation without changing our signature.

The third is explicitness. Even with functors in the language we would constantly have to convert from a set to a functor and back again. There is no implicit conversion mechanism.

The fourth is the module system. Notice how without a different keyword for signature and structure we have no way to provide additional implementations of our signature. ML allows the following all in one file

signature SetSig = …

structure ListSet :> SetSig = …

structure TreeSet :> SetSig = …

Set = TreeSet

How we achieve this in F# I do not know.

Expanding Our Set Signature

Let’s add a bit more functionality to our Set signature to get an idea of how cumbersome problem number two is.

module SetSig

type ‘a set

val internal toList : ‘a set -> ‘a list (* list all set elts, sorted low to high *)

val empty : ‘a set (* the empty set *)

val is_empty : ‘a set -> bool (* is a set the empty set *)

val singleton : ‘a -> ‘a set (* a set with one element *)

val union: ‘a set -> ‘a set -> ‘a set (* union of two sets *)

val is_member : ‘a -> ‘a set -> bool (* is elt a member of given set? *)

val remove : ‘a -> ‘a set -> ‘a set (* remove elt from given set *)

module SetSig

type ‘a set = internal Set of ‘a list

let toList s = match s with Set lst -> lst

let empty = Set[]

let is_empty s = List.length(toList s) = 0

let singleton x = Set[x]

let union s1 s2 = Set(ListSetUtils.union (toList s1) (toList s2))

let is_member x s = ListSetUtils.is_member x (toList s)

let remove x s = Set(ListSetUtils.remove x (toList s))

Two patterns should immediately jump out at you.

1. We constantly have to use toList to convert our set to a list

2. We constantly have to use the Set data constructor to wrap our list as a set

The constant wrapping and unwrapping obfuscates the purpose of our code and makes it harder to vary the implementation without rewriting everything. You wish there was a way to tell the compiler to implicitly convert from list to set and vice versa instead of always having to explicitly make the conversion.

Pattern Matching To the Rescue

All is not doom and gloom, however, F# has very cool pattern matching capabilities. Let’s say a consumer of our library wants to add a function to calculate the cardinality of the set. In ML we would provide a destructor function and force the user into the following pattern.

let rec cardinality s =

if is_empty s then 0 else

let (x,s’) = singleton_split s

1 + cardinality s’

With F# we can provide pattern matching over our abstract data types.

module SetSig

…

val internal singleton_split : ‘a set -> ‘a * ‘a set (* remove elt from given set and return singleton *)

val (|Nil|Cons|) : ‘a set -> Choice<’a set,(’a * ‘a set)>

module SetSig

…

let singleton_split s =

match toList s with

| [] -> invalid_arg “s”

| x::s -> let lst = ListSetUtils.remove x s

(x, Set(lst))

let (|Nil|Cons|) s =

if is_empty s then Nil(s)

else Cons(singleton_split s)

Notice the return type of our pattern matching function, choice basically returns all possibilities and allows us to match on them. The consumer of our library can now do the following.

let rec cardinality s =

match s with

| Nil s -> 0

| Cons(x,s) -> 1 + cardinality s

Handy, and an F# exclusive feature.

A Mixed Bag of Functionality

The Set class provided in Microsoft.FSharp actually implements a Set as an object oriented class. Unfortunately, swapping this Set out for your own implementation is a non starter as it does not implement an interface.

With Haskell we get higher kinded polymorphism and type classes, ML solves many of the same problems with a sophisticated module system, F# uses the object oriented type system of .Net to solve problems the way you would in VB or C#. Hopefully, at some point F# will be free to forge its own road on the .Net platform, making it easier to solve problems the other functional languages have licked.

Abstracting the Map Function

When pitching functional programming to an imperative friend, the “map” function is the canonical example of the obvious advantages of the functional approach. And once our backwoods imperative friend has begrudgingly accepted “map” as a neat party trick, we can really amaze them by abstracting “map” over any mappable structure. That is as long as brand of functional magic is something besides F#.

A Map over Trees

Let’s start with an example from Real World Haskell.

type Tree<’a> =

| Node of (Tree<’a>) * (Tree<’a>)

| Leaf of ‘a

let tree = Node ((Leaf “foo”),(Node((Leaf “x”),(Leaf “quux”))))

And we can write a function to calculate the length of the string at each node.

let rec tree_lengths = function

| Leaf s -> Leaf (String.length s)

| Node (l,r) -> Node (tree_lengths l,tree_lengths r)

> tree_lengths tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

But we prefer to use our party trick wherever we can and so we write.

let rec tree_map f tree =

match tree with

| Leaf a -> Leaf (f a)

| Node (l,r) -> Node (tree_map f l,tree_map f r)

> tree_map String.length tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

Then impress them with our combinations.

let odd = (fun x -> x % 2 <> 0)

> tree_map (odd << String.length) tree;;

val it : Tree<bool> = Node ((Leaf true),(Node((Leaf true),(Leaf false))))

And finally define an operator for our tree_map mapping function.

let (<$>) f tree = tree_map f tree

> String.length <$> tree;;

val it : Tree<int> = Node ((Leaf 3),(Node((Leaf 1),(Leaf 4))))

> (odd << String.length) <$> tree;;

val it : Tree<bool> = Node ((Leaf true),(Node((Leaf true),(Leaf false))))

A Map over Type<_>

Now that we’ve defined a map function for Tree types let’s compare it to our familiar map function over lists.

// val tree_map : (’a -> ‘b) -> Tree<’a> -> Tree<’b>

let rec tree_map f tree =

match tree with

| Leaf a -> Leaf (f a)

| Node (l,r) -> Node (tree_map f l,tree_map f r)

// val list_map : (’a -> ‘b) -> List<’a> -> List<’b>

let rec list_map f list =

match list with

| [] -> []

| h::t -> (f h) :: list_map f t

In both cases we’re taking a function over ordinary types and lifting it into a function over container types. If a is a Type then our Tree and List types are related in that they are both Type<_>. And because we prefer to codify the relationship between apparently disparate structures, we write the following map function

// val list_map : (’a -> ‘b) -> Type<’a> -> Type<’b>

let type_map f t =

match t with

| :? List<’a> -> list_map f t.a

| :? Tree<’a> -> tree_map f t.a

let (<$>) f t = type_map f t

Of course the compiler screams about our attempt to relate trees and lists. Our type_map function requires 4 concepts the F# compiler does not support.

1. Higher kinded polymorphism

2. Pattern matching over higher kinds

3. Static type tests

4. Polymorphic return types

In plain English this means we want the compiler to differentiate between ordinary types and parameterized types, pattern match over parameterized types, provide a standard way to extract the underlying type, catch invalid type tests at compile time instead of runtime, and allow us to return specific instances of Type<_> from a function.

Because F# has to use the type system of .Net, I wouldn’t expect any of these any time soon, if ever.

A Connection between Trees and Lists

Unfortunately, F# brains will never make the connection between trees and lists. Trees and lists will forever remain separate unrelated concepts. How important you regard this connection depends on your tolerance for redundant code. I guess we’ll have to learn to have a high tolerance indeed.

Untying the Recursive Knot

When a book is packed with concepts and information it’s very easy to gloss over something that in retrospect is very interesting. I often skim back over things I’ve already read hoping some of the new information I’ve accumulated will lead to deeper insights and interesting discoveries. “Untying the recursive knot” from F# for Scientists is one such concept I don’t believe I was sufficiently fluent enough in functional programming to glean its power. Let’s have a look.

Recursive Functions

The factorial function is a pretty standard function for introducing the concept of recursion to beginning functional programmers.

let rec factorial = function

| 0 -> 1

| n -> n * factorial (n – 1)

The rec keyword allows us to recursively call our factorial function passing in a number 1 less than the current call. The factorial function is a perfectly good function that accomplishes its assigned task, hence

> factorial 5;;

val it : int = 120

but as functional programmers we’re not so interested in standalone functionality as the ability to compose simple functions into more complex ones. We have no way to intercept the recursion and plug in a piece of custom functionality.

So how can we untie this recursive knot?

Higher Order Continuations

We can rewrite our factorial function to accept the function it should call next.

//val factorial : (int -> int) -> int -> int

let factorial factorial = function

| 0 -> 1

| n -> n * factorial(n – 1)

And now we need a way to jumpstart the recursion.

//val y : ((’a -> ‘b) -> ‘a -> ‘b) -> ‘a -> ‘b

let rec y f x =

f (y f) x

The y combinator will continue to generate a continuation for us as long as we ask for one. Applying y to our factorial function gives us the answer we expect

> y factorial 5;;

val it : int = 120

except now we’re able to insert some custom functionality right into the middle of the recursion.

> y (factorial >> fun f n -> printf “%d\n” n; f n) 5;;

val it : int = 120

Pretty neat! Instead of each function having its own proprietary recursion, we’ve made y our recursive combinator, and all other functions are responsible for playing nicely with it or risk being excluded from the fun.

Launch the Missiles

If you’ve been programming in F# for any length of time then undoubtedly you’ve run into the term “call by value”. Another name for “call by value” is eager evaluation as opposed to lazy evaluation and the corresponding “call by name”. Let’s throw together a fun little program to demonstrate the difference between the two.

Call By Value

type MissileCommand =

| Launch

| Disable

let a1 = printfn “%A” “KABOOM!”

let a2 = printfn “%A” “WE LIVE!”

let run cmd a1 a2 =

match cmd with

| Launch -> a1

| Disable -> a2

run Disable a1 a2

So what do you think gets printed to the screen when we run our Disable command? You may be surprised to see the following written to the console.

“KABOOM!”

“WE LIVE!”

So how did the human race get obliterated when we sent the Disable command? In a “call by value” language functions arguments are evaluated eagerly, so both a1 and a2 are evaluated before the run function is applied to them. Scary!

Call By Name

To simulate “call by name” semantics in F# we are forced to explicitly wrap our functions in a lazy wrapper.

let lazy_a1 = lazy (printfn “%A” “KABOOM!”)

let lazy_a2 = lazy (printfn “%A” “WE LIVE!”)

let safe_run cmd (a1:Lazy<_>) (a2:Lazy<_>) =

match cmd with

| Launch -> a1.Force()

| Disable -> a2.Force()

safe_run Disable lazy_a1 lazy_a2

And now the human race is saved from nuclear annihilation as we get what we expect printed to the console.

“WE LIVE!”

The lazy wrapper acts as a thunk for the actual computation which only gets computed once we force it.

Call By Value With Side Effects

Now I hope you don’t lie await at night worrying about a computer bug accidently leading to Armageddon. I’m sure our nuclear missile system is written in a lazy language. But I do hope you get a feeling for what a noxious combination “call by value” and undocumented side effects are.

What if instead of printing to the console our action updated a global counter? Or deleted records from a database? Functional languages allow us to pass functions around as if they were data, but do we really want them evaluating them behind the scenes when they do?

OCaml Functors as Interfaces Take 2

We left off in a rather unsatisfying predicament, we can simulate OCaml functors with interfaces, but at the expense of passing in two type parameters and guarding all our functions with type constraints. Yuck!

Let’s solve both these problems

OCaml Functors at the Type Level

Let’s leave the realm of regular F# and pretend we’re able to declare static members on our interfaces. This allows us to pass functions around with the type parameters themselves instead of just the instances. With this one simple enhancement to interfaces we can now declare the following signatures.

#type comparison = Less | Equal | Greater;;

type comparison = Less | Equal | Greater

#module type ORDERED_TYPE =

sig

type t

val compare: t -> t -> comparison

end;;

module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end

#module OrderedString =

struct

type t = string

let compare x y = if x = y then Equal else if x < y then Less else Greater

end;;

module OrderedString : sig type t = string val compare : ‘a -> ‘a -> comparison end

becomes

type comparison = Less | Equal | Greater

type ORDERED_TYPE<’a> =

static type t : ‘a

static abstract compare : t -> t -> comparison

type OrderedString() =

interface ORDERED_TYPE<string> with

member compare x y = if x = y then Equal else if x < y then Less else Greater

and our set signature with only the add function gets simplified to the following.

type Set<’con> when ‘con :> ORDERED_TYPE<con.t> () =

member me.add (x : con.t) (s : con.t list) =

let rec add (x : con.t) (s : con.t list) =

match s with

| [] -> [x]

| hd::tl ->

match con.compare x hd with

| Equal -> s (* x is already in s *)

| Less -> x :: s (* x is smaller than all elements of s *)

| Greater -> hd :: add x tl

add x s

By allowing functions to be passed around with type parameters, we now only have to pass a single type parameter because we can extract the underlying type by a call to t. Also, we no longer have to pass constrained types into our add function. We can simply call the static compare function on our con type parameter.

Of course, we don’t have “fancy” type level programming in F# so we’re forced to solve the problem at the instance level.

OCaml Functors at the Instance Level

Type constraints seem of little use when you can’t perform type level programming. So let’s move the type constraint from the parameter list to the constructor. Let’s redefine our interfaces and set type.

type ORDERED_TYPE<’a> =

abstract compare : ‘a -> ‘a -> comparison

type OrderedString() =

interface ORDERED_TYPE<string> with

member me.compare x y = if x = y then Equal else if x < y then Less else Greater

type Set<’a> (cf : ORDERED_TYPE<’a>) =

member me.empty : ‘a list = []

member me.add (x : ‘a) (s : ‘a list) =

let rec add (x : ‘a) (s : ‘a list) =

match s with

| [] -> [x]

| hd::tl ->

match cf.compare x hd with

| Equal -> s (* x is already in s *)

| Less -> x :: s (* x is smaller than all elements of s *)

| Greater -> hd :: add x tl

add x s

Just as with the type level example, we now only need a single type parameter and no longer have to constrain our functions with type constraints. The use of the class really isn’t too bad.

let StringSet = Set<string>(OrderedString())

let r1 = StringSet.add “do” (StringSet.add “re” (StringSet.add “mi” StringSet.empty))

printfn “%A” r1

prints [“do”;”mi”;”re”] to the console we can easily compose a different version of our set. For instance,

type OrderedStringReverse() =

let reverse (s:string) = new string(s |> Seq.to_array |> Array.rev)

interface ORDERED_TYPE<string> with

member me.compare x y =

let rev_x = reverse x

let rev_y = reverse y

if rev_x = rev_y then Equal else if rev_x < rev_y then Less else Greater

let StringSetReverse = Set<string>(OrderedStringReverse())

let r2 = StringSetReverse.add “do” (StringSetReverse.add “re” (StringSetReverse.add “mi” StringSetReverse.empty))

printfn “%A” r2

prints [“ro”;”mi”;”do”]. So by passing the constraint to the constructor we can change the structure our “functor” generates.

What Do We Lose?

Compossibility. In the second example our StringSetReverse only exists at runtime. The following declaration fails.

type StringSetReverse = Set<string>(OrderedStringReverse())

We cannot make StringSetReverse part of our type system and use it as a type in other areas of our program. We’ve lost the ability to compose complex types from simpler ones. How important you consider composing complex types from simple ones will determine how much you feel F# has lost compared to OCaml.

OCaml Functors as Interfaces

The following page describes in detail the differences between the OCaml and F# languages. It’s a good read for anyone familiar with OCaml and an even better read for those who are not. For the first line of the summary declares

Functors, OCaml-style objects, labels and option arguments are not supported. Some common functors like Set.Make and Hashtbl.Make are simulated by returning records of functions.

Simulating functors by returning records of functions sounds interesting. Let’s take a closer look at what functors in OCaml are.

OCaml Functors

Chapter 2 of the OCaml manual has a pretty good example of using functors. I have to admit that just finding a good example was somewhat of a chore, which suggests either functors aren’t used a whole lot by OCaml programmers or nobody understands them.

The example starts by declaring a signature to represent types that are orderable.

#type comparison = Less | Equal | Greater;;

type comparison = Less | Equal | Greater

#module type ORDERED_TYPE =

sig

type t

val compare: t -> t -> comparison

end;;

module type ORDERED_TYPE = sig type t val compare : t -> t -> comparison end

We’ll fall back on our object oriented upbringing and use an interface to model the same signature in F#.

type comparison = Less | Equal | Greater

type ORDERED_TYPE<’a> =

abstract t : ‘a

abstract compare : ‘a -> ‘a -> comparison

Now a structure is created for strings. Notice how there is no explicit connection between the structure and the signature.

#module OrderedString =

struct

type t = string

let compare x y = if x = y then Equal else if x < y then Less else Greater

end;;

module OrderedString : sig type t = string val compare : ‘a -> ‘a -> comparison end

We have no choice but to explicitly implement our interface signature.

type OrderedString(t : string) =

interface ORDERED_TYPE<string> with

member me.t = t

member me.compare x y = if x = y then Equal else if x < y then Less else Greater

For those paying attention you’ll see a subtle difference between the two OrderedString declarations. The F# declaration returns an instance of a string for t instead of the type of string. In fact, whereas the F# definition appears to be an instance of type the OCaml version appears to be a type of a type.

Implementing Set as a Functor

The type signature are done, let’s move on to the meat of building our functor. We’ll start with the signature.

module Set :

functor (Elt : ORDERED_TYPE) ->

sig

type element = Elt.t

type set = element list

val empty : ‘a list

val add : Elt.t -> Elt.t list -> Elt.t list

val member : Elt.t -> Elt.t list -> bool

end

And examine the implementation of the signature piece by piece.

#module Set =

functor (Elt: ORDERED_TYPE) ->

struct

type element = Elt.t

type set = element list

So a set is a functor that takes an ordered type as a parameter. The type is then extracted and stored in the element type. I have a feeling our F# definition will have to be quite different.

type Set<’a,’con> when ‘con :> ORDERED_TYPE<’a> () =

And so it is. With F# we can’t combine the constraint and underlying type as a single parameter. Unlike OCaml we have no way of extracting the underlying type from the container type. This results in an unfortunate redundant construction.

So the construction of our types are different, let’s analyze the functions.

let empty = []

let rec add x s =

match s with

[] -> [x]

| hd::tl ->

match Elt.compare x hd with

Equal -> s (* x is already in s *)

| Less -> x :: s (* x is smaller than all elements of s *)

| Greater -> hd :: add x tl

let rec member x s =

match s with

[] -> false

| hd::tl ->

match Elt.compare x hd with

Equal -> true (* x belongs to s *)

| Less -> false (* x is smaller than all elements of s *)

| Greater -> member x tl

And the corresponding F# implementation.

member me.empty : ‘con list = []

member me.add (x : ‘con) (s : ‘con list) =

let rec add (x : ‘con) (s : ‘con list) =

match s with

| [] -> [x]

| hd::tl ->

match x.compare x.t hd.t with

| Equal -> s (* x is already in s *)

| Less -> x :: s (* x is smaller than all elements of s *)

| Greater -> hd :: add x tl

add x s

member me.is_member (x : ‘con) (s : ‘con list) =

let rec is_member (x : ‘con) (s : ‘con list) =

match s with

| [] -> false

| hd::tl ->

match x.compare x.t hd.t with

| Equal -> true (* x belongs to s *)

| Less -> false (* x is smaller than all elements of s *)

| Greater -> is_member x tl

is_member x s

The fundamental difference with the F# code is we’re forced to work with the constraint instead of the underlying type. Because the compare function is only available on instances of ordered types we can only pass those types into our set.

The compare function in the OCaml example however is attached to type itself instead of an instance of the type. Remember how our OCaml structure was more analogous to a type of type rather than an instance of a type? This allows us to solve problems at the type level instead of always relying on runtime dispatch for polymorphism.

Applying the Set Functor

So we’ve built a signature for an ORDERED_TYPE. We’ve created a structure for a string type that implements the signature. We’ve created a functor called Set that can be applied to the structure. So let’s finish this off and do the application.

#module StringSet = Set(OrderedString);;

module StringSet :

sig

type element = OrderedString.t

type set = element list

val empty : ‘a list

val add : OrderedString.t -> OrderedString.t list -> OrderedString.t list

val member : OrderedString.t -> OrderedString.t list -> bool

end

The application of the functor creates a new set for ordered strings. We can now use this set with functions that only work with strings.

#StringSet.member “bar” (StringSet.add “foo” StringSet.empty);;

- : bool = false

The application of our F# “functor” is slightly messier because of the inherent redundancy.

let StringSet = Set<string,OrderedString>()

And of course we have to wrap our strings in OrderedStrings.

let result = StringSet.is_member (OrderedString(“bar”)) (StringSet.add (OrderedString(“foo”)) StringSet.empty)

Does F# Compete Against Java or Other Functional Languages

Some further tricks with interfaces or a record of functions may solve the problem encountered above, but we continue to get the sense that .Net really just isn’t designed with functional languages in mind. Here’s another situation where the F# type system doesn’t appear to be up to snuff with a fellow functional friend. I think most people would agree .Net was created to compete with Java and it shows.

So will this legacy be the stone around F#’s neck that prevents it from ever really being able to compete with Haskell or OCaml? F# may become a great replacement for C# or Java programs, but will the .Net type system ever evolve to the point where F# can solve problems at the type level? With the mutable nature of the .Net API’s and the large legacy code base that must be supported, maybe F# would have been better off staying in the lab and forging the way forward for a proper .Net 2.0.

Full Source Code

#light

type comparison = Less | Equal | Greater

type ORDERED_TYPE<’a> =

abstract t : ‘a

abstract compare : ‘a -> ‘a -> comparison

type OrderedString(t : string) =

interface ORDERED_TYPE<string> with

member me.t = t

member me.compare x y = if x = y then Equal else if x < y then Less else Greater

type Set<’a,’con> when ‘con :> ORDERED_TYPE<’a> () =

member me.empty : ‘con list = []

member me.add (x : ‘con) (s : ‘con list) =

let rec add (x : ‘con) (s : ‘con list) =

match s with

| [] -> [x]

| hd::tl ->

match x.compare x.t hd.t with

| Equal -> s (* x is already in s *)

| Less -> x :: s (* x is smaller than all elements of s *)

| Greater -> hd :: add x tl

add x s

member me.is_member (x : ‘con) (s : ‘con list) =

let rec is_member (x : ‘con) (s : ‘con list) =

match s with

| [] -> false

| hd::tl ->

match x.compare x.t hd.t with

| Equal -> true (* x belongs to s *)

| Less -> false (* x is smaller than all elements of s *)

| Greater -> is_member x tl

is_member x s

//By applying the Set functor to a structure implementing an ordered type, we obtain set operations for this type

let StringSet = Set<string,OrderedString>()

let result = StringSet.is_member (OrderedString(“bar”)) (StringSet.add (OrderedString(“foo”)) StringSet.empty)

printfn “%A” result

System.Console.ReadLine()

Using Numerals to Map Functions to Arguments

The map function is one of the most useful functions in all of functional programming. Pass a function, a list of arguments, apply the function to each argument, and return a new list of the results.

let list = [1;2;3;4;5]

let f1 = (fun a -> a)

let alist = List.map f1 list

>[1;2;3;4;5]

The map2 function does basically the same thing, except the function takes two arguments, hence we need two lists of arguments.

let list = [1;2;3;4;5]

let f2 = (fun a b -> a + b)

let alist2 = List.map2 f2 list list

>[2;4;6;8;10]

And I bet you can guess what the map3 function does.

let list = [1;2;3;4;5]

let f3 = (fun a b c -> a + b + c)

let alist3 = List.map3 f3 list list list

>[3;6;9;12;15]

But now we’ve got a problem for there is no Map4 function.

Extending the Map3 Function

The basic idea here is to put an end to the continued definitions of Map functions. Let’s see if we can “extend” the Map3 function to take one more argument list. Something like the following would be great.

let f4 = (fun a b c d -> a + b + c + d)

let alist4 = List.map3 f4 list list list << list

Where the << operator is defined as

let rec (<<) f a =

match f, a with

| fh :: ft, ah :: at -> fh ah :: (ft << at)

| _ -> []

We pass a list of functions, and the next list of arguments to apply the function to. For our f4 function we will have already applied f4 for the a b and c arguments by the time we use our << operator. So after the use of our operator we’re left with

>[4;8;12;16;20]

And if you think about it, there’s not really any reason for the Map2 or Map3 functions. Let’s “extend” our Map function for a function requiring 5 bound variables.

let f5 = (fun a b c d e -> a + b + c + d + e)

let alist5 = List.map f5 list << list << list << list << list

>[5;10;15;20;25]

Introducing Parametric Numerals

The above use of the << operator is ok. It solves our problem of having to continually define Map functions, but it’s not very readable. What if a very complex calculation requires 18 bound variables? Do you really want to count up the instances of << ? And wouldn’t it be great if there was a way to constrain the map function to precisely the number of bound varaibles you require in the first place?

Let’s define some parametric numerals.

let succ n fl al = n (fl << al)

let zero al = al

let one n a = succ zero n a

let two n a b = succ one n a b

let three n a b c = succ two n a b c

let four n a b c d = succ three n a b c d

let five n a b c d e = succ four n a b c d e

And a new map function that can use them.

let mapWith n f l = n (List.map f l)

Our map function suddenly becomes very readable and constrained to exactly the number of bound variables we require.

let blist = mapWith zero f1 list

let blist2 = mapWith one f2 list list

let blist3 = mapWith two f3 list list list

let blist4 = mapWith three f4 list list list list

let blist5 = mapWith four f5 list list list list list

The first parameter requires a parametric numeral that states how many additional bound variables our mapWith function requires.

let blist5 = mapWith four f5 list list list list list

can be read as map with four additional bound variables, if we try to write

let blist5 = mapWith four f5 list list list list list list

then the compiler catches the error of our ways. Pretty handy!

An Odd Argument Indeed

The first argument to our mapWith function really is an odd argument. Unlike traditional variables, which act as placeholders, it encodes information about how the function should behave. We’ll take more in depth look at these “odd arguments” next time.

The ideas in the blog come from the following paper, which is a pretty easy read.

Polymorphic Return Types for F#?

We used a good old fashioned subtyping and a dash of parametric polymorphism to write an eval function capable of returning different types. But surely we gave up too easily on polymorphic return types in F#? I assure you we gave them the ol’ college try.

Polymorphic Return Types Take 1

Let’s start with a pretty simple data constructor that constructs two different types.

type Term =

| Int of int

| Char of char

Now we write a rather straightforward eval function to evaluate our terms. For instance,

// Term -> int

let eval t =

match t with

| Int i -> i

//the expression has type char but here is used with type int

| Char c -> c

But because our first match returns an integer our second must also return a char.

Polymorphic Return Types Take 2

Just because the compiler doesn’t like what you’re trying to do doesn’t mean it isn’t right. Let’s take a different tact.

// Term -> obj

let eval t =

match t with

| Int i -> i :> obj

| Char c -> c :> obj

let i = eval (Int 1)

let c = eval (Char ‘c’)

printfn “%A” i

printfn “%A” c

So we sacrifice our type safety to get a couple of values printed to the console. Not what we had in mind. We want the type system to guide us instead of forcing us to throw it out the window.

Polymorphic Return Types Take 3

So if we can’t return a different type and we don’t want to lose our type safety, let’s try returning all possible types.

// Term -> Choice<int,char>

let eval t =

match t with

| Int i -> Choice2_1 i

| Char c -> Choice2_2 c

let i = eval (Int 1)

let c = eval (Char ‘c’)

So our eval function compiles and returns a different choice for each constructor. All we have to do now is extract the value out of the choice and were done.

// Term -> Choice<’a,’a>

let extract choice =

match choice with

| Choice2_1 i -> i

| Choice2_2 c -> c

// expecting a Choice<int,int> but given a Choice<int,char>

let i = extract (eval (Int 1))

And if we annotate the choice function we’ve just reinvented our original problem.

// Term -> Choice<int,char> -> int

let extract_int_char (choice : Choice<int,char>) =

match choice with

| Choice2_1 i -> i

//the expression has type char but here is used with type int

| Choice2_2 c -> c

Polymorphic Return Types Take 4

Let’s start with a function that does work.

// Term -> unit

let display t =

match t with

| Int i -> printfn “%A” i

| Char c -> printfn “%A” c

Now can’t we somehow lift the variables out of the function without changing the return type? Something along the lines of.

// Term -> ‘a ref -> unit

let eval t r =

match t with

| Int i -> r := i

//the expression has type char but here is used with type int

| Char c -> r := c

Only to be thwarted again and all we’re left with to get our values out of eval function is the following monstrosity.

// Term -> int ref -> char ref -> unit

let eval t ri rc =

match t with

| Int i -> ri := i

| Char c -> rc := c

let ri = ref 0

let rc = ref ‘a’

let ie = eval (Int 1)

let u1 = eval (Int 1) ri rc

let i = !ri

let u2 = eval (Char ‘c’) ri rc

let c = !rc

printfn “%A” i

printfn “%A” c

Eat your heart out Perl. We’ve got a new write once kid on the block.

Do Loop Until You Die

Categories

Archives

Getting Source Code into Your Blog

Consuming Fluent Interfaces

Hide your Design Decisions with Abstract Data Types

Abstracting the Map Function

Untying the Recursive Knot

Launch the Missiles

OCaml Functors as Interfaces Take 2

OCaml Functors as Interfaces

Using Numerals to Map Functions to Arguments

Polymorphic Return Types for F#?

Recent Posts

Blogroll

Meta