Neat F#: Custom Operators

F# has support for custom operators.  The best use of this I've seen so far is in the canopy web testing library.  Canopy allows you to write code like:

"#firstName" << "Kevin"
"#firstName" == "Kevin"

That code is the same as this code written with the Coypu web testing library:

browser.FillIn("#firstName").With("Kevin")
browser.FindField("#firstName").Value.ShouldEqual("Kevin")

As you've likely deduced, the "<<" operator has been overridden to lookup the field and set it's value, while the "==" operator has been overridden to lookup up the field and assert on it's value.

In this case, both of these operators do exist already in F#, but they obviously aren't usually used to drive a web browser.  So this is a powerful use of operator overloading.  But F# allows you to define custom operators that have no definition in F# as well.  They can be any combination of a certain set of characters.

For example, there is no "=~" operator in F#, but you could define one to do a regex match as follows:

open System.Text.RegularExpressions
let (=~) input pattern = Regex.IsMatch(input, pattern)

And you'd use it like:

"some input" =~ ".*input"

And you could also define one that is case insensitive:

let (=~*) input pattern = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)

These operators are not overloaded, they're just custom defined.

There is clearly a tradeoff here between explicit code and concise code.  Look back at the first example from Canopy again.  If you knew that was web testing code, and you recognized "#firstName" as a css selector, you would probably figure out what it was doing.  And this conciseness is going to be really nice in a situation where you're executing the same type of operations over and over and over again (say, like, in a Selenium web test!).  So while there's no mistaking what the Coypu code is doing, I'd rather write the Canopy code!

However, in the regular expression example, since =~ and =~* are not part of the language, how would you know what they do.  Certainly there's a similarity to ruby, but I've never seen a =~* operator.  So introducing stuff like this to your code base runs the risk of making your code harder to understand.

In the end, I think it's an awesome feature to have at your disposal.  And I think a good rule of thumb is to be willing to try some custom operators when you have a high and dense repetition of operations.  That is, it's not a one off operation, or it's not used always by itself in far flung sections of code.

In any case, this another powerful, and very neat, feature of F#.

Neat F#: Inferred Return Types

What is the return type of this F# function?

let hello name = sprintf "Hello %s" name

If you guessed string, you're correct! I know this syntax can be confusing at first glance, so here it is one element at a time:

• let hello name =
  let: the "let binding's" job is to associate a variable name with a value or function.  It BINDS things to names
  hello: hello is the name of the function
  name: hello takes one parameter, and it called name, and it's type will be inferred
• sprintf "Hello %s" name
  sprintf: basically F#'s version of .net's String.Format, it's a function that takes a format string with placeholders and values as arguments and returns a string.  In fact, this function is so neat it deserves it's own post.
  "Hello %s": the format string, %s tells the compiler a string parameter is required
  name: argument to sprintf

sprintf returns a string, therefore the hello function returns a string.  Notice there's no explicit return statement, whatever the last statement returns the function returns.  However, this is made more interesting by the fact that just about everything in F# is a statement that returns a value, including if statements:

let hello name =
    if name = "kwb" then
        "'sup KBizzle!"
    else
        sprintf "hello %s" name

This function still returns a string, because the if statement returns a string. Note this means in F# the if and the else must return the same type!

Also note, there's nothing wrong with that last code sample, but it's my impression that if statements are generally frowned upon in F# in favor of pattern matching. A true F# dev would probably have written that last using the pattern matching function syntax like this:

let hello =
    function 
        | "kwb" -> "'sup KBizzle!"
        | _ as name -> sprintf "hello %s" name

That's really outside the scope of this post, but it makes me happy!

So this brings us to the _really_ neat part: functions with changing return types.  All the functions we've seen so far have had a single static return type.  But what about this function?

let crazy f =
    f 4

What is it's return type? Maybe this will help?

let somestring x = sprintf "the number %d" x
let someint x = x

crazy somestring
crazy someint

Crazy's return type is different depending on what function we pass to it!

Neat F#: Pipe Forward

Functional programming dates back to the 1950s, but from my perspective it seems to have been garnering more attention in the software engineering community recently.  I first got really interested in it last year at CodeMash when Ben Lee introduced me to a little bit of Erlang.  It was so fascinating that I decided I had to dive in deeper.  F# being a .NET language, it was the obvious choice.  So I bought an ebook of Programming F# and started writing a few little programs.

Along the way there have been a few things that completely blew my mind, or that I thought were just flat out neat.  You could (and should) learn about these things from much better sources, but I love to share!

So to kick it off, this first post will cover the first thing in F# that really truly blew my mind: the Pipe Forward operator.  You see it used in F# all the time, and what it allows you specify the last parameter's value first, thus writing your statements in a more logical order.

So for example, this:

let testInts = [1;2;3;4;5;]
let evenInts = List.filter (fun i -> i % 2 = 0) testInts

Can be re-written as this:

let testInts = [1;2;3;4;5;]
let evenInts = testInts |> List.filter (fun i -> i % 2 = 0)

This example is trivial of course, but where this really starts to shine is when you can effectively describe an entire program in one chain of function calls:

let oddPrimes = 
    testInts
    |> filterOdds
    |> filterPrimes

Basically what's happening here is that the value on the left of the pipe forward operator is being passed as the last parameter to the function on the right. In the first example, List.filter takes two parameters. The first is a function, and the second is a list. You'll find that all the functions in F# modules are structured so that the parameter most likely to be passed down a chain like this is defined as the last parameter.

At first I didn't think this was mind blowing at all. It just looked like a simple compiler trick. But then I learned this isn't in the compiler at all. In fact, |> is just a single line F# function. It's definition is nothing more than:

let (|>) x f = f x

F# also has a pipe backward operator:

let evenInts = List.filter (fun i -> i % 2 = 0) <| testInts

And it is defined as:

let (<|) f x = f x

If you've followed along this far, I hope you are boggling your mind as to what possible purpose this could serve! I know I was. The answer comes from the fact that operators have higher precedence in F#. So the pipe backwards operator allows you to avoid wrapping an expression in parenthesis. For example:

let output = "the result is: %d" (2 + 2)

Those parenthesis are such a drag. So we can rewrite this without them as:

let output = "the result is: %d" <| 2 + 2

Word Ladder in F#

Anthony Coble sent me his solution to this in Haskell before his Haskell talk at Burning River Developers.  The problem was to find a Word Ladder between two words.  A word ladder is a chain of words, from a start word to an end word, in which each word in the chain is one letter different from the word before it and is a real word.  The goal is to find the shortest ladder between the start and end word.  It's a neat problem, made even neater by the fact that it was invented by Lewis Carroll!  So I couldn't resist giving it a try in F#.  And fortunately, I don't know Haskell so I couldn't understand Anthony's solution, so I had to figure it out all on my own.

Speaking of which, this is a fun problem.  So if you want to give a try, you should stop reading here and come back after you've solved it!

I found this problem to be surprisingly difficult.  I kept coming up with ideas but inevitably they were over simplified and wouldn't work.  I was visualizing it as a tree.

It's an interesting problem because it has three different cases to consider.  It's normal for a problem to have two cases, like the first item in the list, and every other item.  But at least with the way I approached it, this problem had three cases: the first node (which has no parent node), the nodes in the first level of the tree (which all have the same parent), and every level after that (where there are many different parents).  This kept causing me to come up with ideas that only worked for the first level, or ideas that worked for one of those levels and not the others...

I knew that I needed a breadth first search but I was really struggling with how to implement it while also keeping track of the path to each node.  Usually a breadth first search effectively just loops over all the nodes in each level, and then calls the next level recursively.  But I need to know what the parent of each node is, and what that parent's parent is, etc up to the root.  My solution to this was to represent each node as a tuple containing the list of it's full path from root to that node, and the word of that node.  This is what I passed through the recursive calls, therefore I always knew the full path to each node.  This was simple, but has the downside of wasting memory since it duplicates a significant portion of the parent list on each node.

Another interesting element of this solution is that I prune words out of the tree that I've already seen, like the two red nodes in the picture above.  This means I don't have to worry about "infinite loops" (they're not really loops, but you get what I mean) in the graph, so I can search until I run out of nodes.  And its safe, because I need to find the shortest ladder, so if I've already encountered a word earlier in the graph, that same word can't be part of the solution later in the graph.

The git repo with my solution is here: https://github.com/kberridge/word-ladder-kata-fs
And here's the code:


Here are some notes on some of the things I found interesting about this code:

• The array slicing code in the findChildren function was fun.
• And using the range operator in the generateCandidates ['a'..'z'] was fun too.
• The findValidUniqueChildren function is an excellant example of something I've been struggling with in F#.  What parameters does this function take?  What does it return?  It's NOT easy to figure this out, is it?  This is also the first time I've used function composition for real!
• Notice in the queuechildren method how I'm using the concatenate list operator: "let newSearchNodes = searchNodes @ childnodes"?  The Programming F# book says if you find yourself using this it probably means you're doing something in a non-idiomatic way...  I suppose I could have written buildNodes to append the nodes to a provided list, but that seemed awkward.
• The match of findLadderWorker is pretty typical, but demonstrates another little pattern I keep finding.  For the second match, I created a function to call since it's longer than 1 line, so I had to make up a name.  I went with "testnode" which I don't really like, but I had to name it something!

Here's Anthony Coble's Haskell solution.  His is very different and shows a great example of a different way to approach the problem.

Ben Lee also solved it in Erlang.  His is async!

If you solve it, in any language, send me the link to your solution and I'll add it to the post!

Finding Connected Graphs in F#

I've been learning F# and functional programming.  I first got interested in functional languages when Ben Lee introduced me to Erlang at CodeMash by doing the greed kata with me.  Then I bought Programming F# and started to learn the F# language.  As I was going through the book, I was playing with a little Team City/FogBugz integration script in F#.  Then Anthony Coble told me he wanted to do a talk at Burning River Developers on Falling In Love With Haskell.  His talk was great, and Haskell looks like a mind-blowing language.

So that is how I got interested in playing with this stuff.  In order to actually learn it, and not just read about it, I've been finding and inventing little exercise problems and solving them in F#.  F# is a multiparadigm language, but I've been focusing on the pure Functional portions of the language for now.  I thought I'd share these problems and my solutions on the blog.  The best thing that could come from this is if you, dear reader, would also solve these problems in the language of your choice and share back your solution.  Or if you know F# but don't want to actually fully implement a solution to these, I'd love feedback on how you might have solved the problems differently.

The first problem I want to share is a Graph parsing problem:

Given a graph G, return a list of all the connected graphs in G: [G1, G2, ...].

Here's an example input graph and the expected output:

 The git repo with my solutions is here: https://github.com/kberridge/find-connected-graphs-kata-fs

And here's the code:

Some of things I really enjoy about this code:

• I love nesting simple little functions inside other functions to give names to boilerplate code (ex: isSeen and notSeenOnly)
• The recursive walk method is stunningly elegant
• "Map.ofList g" is a cool line of code.  g is a Graph record, but it's defined as a list, and so can be treated like a list.
• List.collect combines all the returned lists into one list
• It's also cool that the map variable is in scope inside of the walk function because it's closed over from the findConnectedGraph method.
• The recursive list comprehension of findAllConnectedGraphsWorker totally blows my mind.  Using yield as expected, but then calling itself with yield! is crazy!

I'm sure there is a lot about this code that could be improved.  There are probably better algorithms too. I'd love to hear your ideas and read your implementations of this problem!

Minor Issues: Constructors and MVC Controllers

Recently I've been getting into F# a little.  It's a really cool language which has been broadening my perspective on problem solving with code.  It's a .NET language, and is mostly compatible with C#, but it does do some things differently.  For example, it has more rigorous rules around constructors:

type Point(x : float, y : float) =

  member this.X = x
  member this.Y = y

  new() = new Point(0.0, 0.0)

  new(text : string) =
    let parts = text.Split([|','|])
    let x = Double.Parse(parts.[0])
    let y = Double.Parse(parts.[1])
    new Point(x, y)

It may not immediately jump out at you, but there are some really cool things here that C# doesn't do:

1. This actually defines 3 constructors, the "main" constructor is implicitly defined to take in floats x and y
2. Constructors can call other constructors!  Note the empty constructor, new().
3. All constructors ARE REQUIRED to call the "main" constructor

I fell in love with this immediately.  This requirement forces me to be keenly aware of what my class's core data really is.  And it communicates that knowledge very clearly to any consumers of the class as well.  This was especially refreshing because I have found that since C# added object initialization syntax (new Point { X = 1.0, Y = 2.0 }) I've started writing far fewer constructors.  Constructors are boilerplate and annoying to type, so I largely stopped typing them.  But now that I have done that for awhile and I have a few real world examples of classes without constructors, I find that I miss the constructors.  They communicate something nice about the core, and most important data, of the class that a whole lot of properties doesn't communicate.

So, that sounds pretty straight forward, and I should start writing constructors on my classes again.  And if I want to be really strict (which I kind of do), I shouldn't provide a default constructor either.  Then I'll be living in the rigorous world of class constructors, just like F#.

But this is where MVC Controllers finally make their first appearance in this post.  Because these controllers exert there own pressure on my classes and down right require a default (parameter-less) constructor.  At least that's the case with the way my team writes our controllers.  Why?  Here's an example.

Let's talk about CRUD.  Typically there's a controller action we call "New", it returns an empty form so you can create a new record.  This form posts to a controller action we call "Create", which binds the form data to a model, and calls .Save().  We're using MVC's standard form builder helpers, which generate form field names and IDs based on the model expression you provide as a lambda.  This is how it knows how to bind the form back to your model on "Create".  But this means you have to pass an empty model out the door in the "New" to generate the empty form.  An empty model requires a default constructor!  So the code looks like this:

public ActionResult New()
{
  ViewData.Model = new Point();
  return View();
}

[HttpPost]
public ActionResult Create(Point point)
{
  point.Save();
  return View();
}

Obviously, real code is more complicated than that, but you get the idea.

And so I find myself with a minor issue on my hands.  On the one hand, I want to create F# inspired rigorous classes.  But on the other hand I want simple controllers that can just send the Model out the door to the view.  Alas, I can't have both, something has to give.

Obviously I could give up on the Constructors.  Or, I could give up on passing my model directly to the view.  There are other approaches well documented in this View Model Patterns post.  The quick description is I could NOT pass my model, and instead pass a View Model that looks just like my model.  And then I'd have to map that View Model back onto my Model somehow...  But that comes with it's own minor issues.

So how about it?  How do you deal with this issue?