If you recall a while back when I was demonstrating some Functional Data Structures, I mentioned the fact that some of the functions were not tail recursive, and that this is something that we would probably want to do something about. Which raises the question: How exactly do we go about making a function tail-recursive? I am going to attempt to address that question here.

One of the first problems with creating a tail recursive function is figuring out whether a function is tail recursive in the first place. Sadly this isn’t something that is always obvious. There has been some discussion about generating a compiler warning if a function is not tail recursive, which sounds like a dandy idea since the compiler knows enough to know how to optimize tail recursive functions for us. But we don’t have that yet, so we’re going to have to try and figure it out on our own. So here are some things to look for:

  1. When is the recursive call made? And more importantly, is there anything that happens after it? Even something simple like adding a number to the result of the function can cause a function to not be tail-recursive
  2. Are there multiple recursive calls? This sort of thing happens when processing tree-like data structures quite a bit. If you need to apply a function recursively to 2 sub-sets of elements and then combine them, chances are they are not tail-recursive
  3. Is there any exception handling in the body of the function? This includes use and using declarations. Since there are multiple possible return paths then the compiler can’t optimize things to make the call recursive.

Now that we have a chance of identifying non-tail-recursive functions lets take a look at how to make a function tail-recursive. There may be cases where its not possible for various reasons to make a function tail-recursive, but it is worthwhile trying to make sure recursive functions are tail-recursive because a StackOverflowException cannot be caught, and will cause the process to exit, regardless (yes, I know this from previous experience Smile)


One of the primary ways of making a function tail-recursive is to provide some kind of accumulator as one of the function parameters so that you an build the final result and pass it on using the accumulator, so when the recursion is complete you return the accumulator. A very simple example of this would be creating a sum function on a list of ints. A simple non-tail-recursive version of this function might look like:

let rec sum (items:int list) =
    match items with
    | [] –> 0
    | i::rest –> i + (sum rest)

And making it tail-recursive by using an accumulator would look like this:

let rec sum (items:int list) acc =
    match items with
    | [] –> acc
    | i::rest –> sum rest (i+acc)



If you can’t use an accumulator as part of your function another (reasonably) simple approach is to use a continuation function. Basically the approach here is to take the work you would be doing after the recursive call and put it into a function that gets passed along and executed when the recursive call is complete. For an example where we’re going to use the insert function from my Functional Data Structures post. Here is the original function:

let rec insert value tree =
    match (value,tree) with
    | (_,Empty) –> Tree(Empty,value,Empty)
    | (v,Tree(a,y,b)) as s –>
        if v < y then
            Tree(insert v a,y,b)
        elif v > y then
            Tree(a,y,insert v b)
        else snd s

This is slightly more tricky since we need to build a new tree with the result, and the position of the result will also vary. So lets add a continuation function to this and see what changes:

let rec insert value tree cont =
    match (value,tree) with
    | (_,Empty) –> Tree(Empty,value,Empty) |> cont
        if v < y then
            insert v a (fun t –> Tree(t,y,b)) |> cont
        elif v > y then
            insert v b (fun t –> Tree(a,y,t)) |> cont
        else snd s |> cont

For the initial call of this function you’ll want to pass in the built-in id function, which just returns whatever you pass to it. As you can see the function is a little more involved, but still reasonably easy to follow. The key is to make sure you apply the continuation function to the result of the function call, otherwise things will fall apart pretty quickly

These two techniques are the primary means of converting a non-tail-recursive function to a tail-recursive function. There is also a more generalized technique known as a “trampoline” which can also be used to eliminate the accumulation of stack frames (among other things). I’ll leave that as a topic for another day, though.

Another thing worth pointing out, is that the built-in fold functions available in the F# standard library are already tail-recursive. So if you make use of fold you don’t have to worry about how to make your function tail recursive. Yet another reason to make fold your go-to function.

Let’s say that you’ve been working hard on this really awesome data structure. Its fast, its space efficient, its immutable, its everything anyone could dream of in a data structure. But you only have time to implement one function for processing the data in your new miracle structure, so what would it be?

Ok, not a terribly realistic scenario, but bare with me here, there is a point to this. The answer to this question, of course, is that you would implement fold. Why you might ask? Because if you have a fold implementation then it is possible to implement just about any other function you want in terms of fold. Don’t believe me? Well, I’ll show you, and in showing you I’ll also demonstrate how finding the right abstraction in a functional language can reduce the size and complexity of your codebase in amazing ways.

Now, to get started, let’s take a look at what exactly the fold function is:

val fold:folder('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

In simple terms it iterates over the items in the structure, and applies a function to each element which in some way processes the element and returns some kind of accumulator. Ok, maybe that didn’t come through quite as simply as I would have hoped. So how about start with a pretty straight-forward example: sum.

let sum (list:int list)= List.fold (fun s i -> s + i) 0 list 

Here we are folding over a list of integers, but in theory the data structure could be just about anything. Each item in the list gets added to the previous total. The first item is added with the value passed in to the fold, so for items [1;2;3] we start by adding 1 to 0, then 2 to 1, then 3 to 3, the result is 6. We could even get kinda crazy with the point-free style and use the fact that the + operator is a function which takes two arguments, and returns a third…which happens to exactly match our folding function.

let sum (list:int list) = List.fold (+) 0 list

So that’s pretty cool right? Now it seem like you could also very easily create a Max function for your structure by using the built in max operator, or a Min function using the min operator.

let max (list:int list) = List.fold (max) (Int32.MinValue) list 
let min (list:int list) = List.fold (min) (Int32.MaxValue) list

But I did say that you could create any other processing function right? So how about something a little trickier, like Map? It may not be quite as obvious, but the implementation is actually equally simplistic. First let’s take a quick look at the signature of the map function to refresh our memories:

val map: mapping ('T –> 'U) –> list:'T list –> 'U list

So how do we implement that in terms of fold? Again, we’ll use List because its simple enough to see what goes on internally:

let map (mapping:'a -> 'b) (list:'a list) = List.fold (fun l i –> mapping i::l) [] list

Pretty cool right? Use the Cons operator (::) and a mapping function with an initial value of an empty list. So that’s pretty fun, how about another classic like filter? Also, pretty similar

let filter (pred:'a -> bool) (list:'a list) = List.fold (fun l i –> if pred I then i::l else l) [] list

Now we’re on a roll, so how about the choose function (like map, only returns an Option and any None value gets left out)? No problem.

let choose (chooser:'a –> 'b option) (list:'a list) = List.fold (fun l i –> match chooser i with | Some i –> i::l | _ –> l) [] list

Ok, so now how about toMap?

let toMap (list:'a*'b list) = List.fold (fun m (k,v) –> Map.add k v) Map.empty list

And collect (collapsing a list of lists into a single list)?

list collect (list:'a list list) = List.fold (fun l li –> List.fold (fun l' i' –> i'::l') l li) [] list

In this case we’re nesting a fold inside a fold, but it still works. And now, just for fun, list exists, tryFind, findIndex, etc

let exists (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i || b) false list
let tryFind (pred:'a -> bool) (list:'a list) = List.fold (fun o i -> if pred i then Some i else o) None list
let findIndex (pred:'a -> bool) (list:'a list) = List.fold (fun (idx,o) i -> if pred i then (idx + i,Some idx) else (idx + 1,o)) (-1,None) list |> snd |> Option.get
let forall (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i && b) true list
let iter (f:'a -> unit) (list:'a list) = List.fold (fun _ i -> f i) () list
let length (list:'a list) = List.fold (fun c _ -> c + 1) 0 list
let partition (pred:'a -> bool) (list:'a list) = List.fold (fun (t,f) i -> if pred i then i::t,f else t,i::f) ([],[]) list

Its worth pointing out that some of these aren’t the most efficient implementations. For example, exists, tryFind and findIndex ideally would have some short-circuit behavior so that when the item is found the list isn’t traversed any more. And then there are things like rev, sort, etc which could be built in terms of fold, I guess, but the simpler and more efficient implementations would be done using simpler recursive processing. I can’t help but find the simplicity of the fold abstraction very appealing, it makes me ever so slightly giddy (strange, I know).

So here we are at part 2 in the series of posts looking at Functional Data Structures from the book of the same name by Chris Okasaki. Last time we looked at what is perhaps the simplest of the functional data structures, the List (also useful as a LIFO stack).  Up next we’ll continue in the order that Chris Okasaki used in his book, and take a look at implementing a Set using a Binary Tree.

Diving right in, here is implementation for a Set using a binary tree in F#:

module Set

    type Tree<'a when 'a:comparison> =
        | Empty
        | Tree of Tree<'a>*'a*Tree<'a> 

    let rec isMember value tree =
        match (value,tree) with
        | (_,Empty) -> false
        | (x,Tree(a,y,b)) ->
            if value < y then
                isMember x a
            elif value > y then
                isMember x b

    let rec insert value tree = 
        match (value,tree) with
        | (_,Empty) -> Tree(Empty,value,Empty)
        | (v,Tree(a,y,b)) as s -> 
            if v < y then
                Tree(insert v a,y,b)
            elif v > y then
                Tree(a,y,insert v b)
                snd s

This is pretty simple, like the List we’re working with a Discriminated Union, this time with an Empty, and then a Tree that is implemented using a 3-tuple (threeple?) with a Tree, an element, and a Tree. There is a constraint on the elements that ensures they are comparable, since this is going to be an ordered tree.

We only have two functions here, one isMember, which says whether or not the element exists in the set, and the other insert, which adds a new element. If you look at the isMember function, its not too difficult, a recursive search of the tree attempting to find the element. Since this is a sorted tree, each iteration will compare the element being searched for with the element in the current node of the tree. If its less than the current node we follow the right-hand side of the tree, otherwise we follow the left-hand side of the tree. If we find an empty tree, the element doesn’t exist. Update is a little more difficult…it’s recursive like isMember, but it is also copying some of the paths. The bits that are copied are the bits that are not being traversed, so in reality the majority of the tree returned from the update function is actually shared with the source tree, its root is just new. Take a hard look at that for a moment, and see if the pain begins to subside…then we’ll look at the C# version.

public static class Tree
    public static EmptyTree<T> Empty<T>() where T: IComparable
        return new EmptyTree<T>();

public class EmptyTree<T> : Tree<T> where T: IComparable
    public override bool IsEmpty { get { return true; }}

public class Tree<T> where T: IComparable
    public Tree<T> LeftSubtree { get; internal set; }
    public Tree<T> RightSubtree { get; internal set; }
    public T Element { get; internal set; }
    public virtual bool IsEmpty
        get { return false; }

public static class Set
    public static bool IsMember<T>(T element, Tree<T> tree) where T: IComparable
        if (tree.IsEmpty)
            return false;
        var currentElement = tree.Element;
        var currentTree = tree;
            if (element.CompareTo(currentElement) == 0)
                return true;
            if (element.CompareTo(currentElement) == 1)
                currentTree = currentTree.RightSubtree;
                currentTree = currentTree.LeftSubtree;
            currentElement = currentTree.Element;
        return false;

    public static Tree<T> Insert<T>(T element, Tree<T> tree) where T: IComparable
        if (tree.IsEmpty)
            return new Tree<T> { LeftSubtree = Tree.Empty<T>(), Element = element, 
                                 RightSubtree = Tree.Empty<T>() };
            case 0:
                return tree;
            case 1:
                return new Tree<T> { RightSubtree = tree.RightSubtree, Element = tree.Element, 
                                     LeftSubtree = Set.Insert<T>(element,tree.LeftSubtree) };
                return new Tree<T> { LeftSubtree = tree.LeftSubtree, Element = tree.Element, 
                                     RightSubtree = Set.Insert<T>(element, tree.RightSubtree) }; 

This is a reasonable chunk of code, so lets work it from the top down. We start off by defining the Tree data structure. We use inheritance in this case to make an Empty tree, since we don’t have Discriminated Unions in C# (If I were a good person I would update that right now to return a singleton of the EmptyTree class, but alas, I’m lazy). The Static Tree class provides the convenience method for creating the empty tree, and the Tree type is our parameterized tree.

The methods in the Set class do the work of checking for an existing member in the set, and inserting a new member in the set.  I took the opportunity to convert the recursive isMember function to a looping construct in C# (which is what the F# compiler will do for you).  This is not really possible with the Insert method because it is not tail recursive.  The logic is the same in both versions, but the C# version is a bit more verbose (though having LeftSubtree and RightSubtree makes things a little clearer in my opinion).  Again, the biggest difference between the two is the amount of code (since we don’t have Discriminated Unions and Pattern Matching in C# land)

Summing Up Persistent Structures

Interestingly this is where the first section of Okasaki’s book ends (Its actually chapter 2, but chapter 1 is more of a foundational thing…no code).  These two implementations show the basic ideas behind what are described as “Persistent” data structures…meaning bits of the structures are re-used when creating new structures are part of an operation that would mutate the original structure in a non-functional (mutable) data structure.  In the case of a List/Stack we are referencing the old list as the “Tail” of the new list, so each time we add a new item we are simply allocating space for the new item.  In the case of the Tree/Set we create a new root tree on Add, and then reference all paths except for the new node that gets added (or, if the item already exists, we just have the new root…this is actually something Okasaki suggests the reader should solve as an additional exercise).  These concepts are fundamental to the more complex data structures that fallow, and present the basic ideas that are employed to make the structures efficient within the context of functional programming.

Up next in the book is a look at how more traditional data structures, such as heaps and queues, can be converted to a more functional setting.  Expect more goodness in the area, but I would also like to revisit some of the basics here.  The more observant readers may have noticed that the majority of the functions used on these simple types were not Tail Recursive, which means the compiler and JIT cannot optimize them, which ultimately means they are going to cause your stack to blow up if you’re dealing with large structures.  It might be worth exploring how to go about converting these to make them Tail Recursive.

I thought it might be fun to explore a little bit of CS as it applies to functional programming, by looking at the idea of Functional Data Structures.  This is actually an area that is still getting a lot of active research, and is pretty interesting stuff overall.  The general idea is to try and figure out ways to provide immutable data structures which can be efficiently implemented in a functional setting.  So you look at some standard data structures, like a linked list, and find a way to implement that as an immutable linked list.  One of the really cool features of Functional Data Structures is that because your dealing with them in an immutable setting, you can actually get a lot of re-use out of them….specifically for something like a list, you can add an item to the list, and return a “new” list that consists of the old list and the new item, and literally provide a structure that points to the old list instead of copying items.  Even if you have other parts of the code referencing older versions of the list without the new item, you don’t have to worry since none of them can mutate the list.

The biggest body of research on this topic was published by Chris Okasaki in 1998, and is still the definitive reference on the subject today.  Just for fun I’m going to look at some of the structures discussed in the original book and see what the implementations would look like in F# and C#.  The original text provided samples in Standard ML, with an eppendix containing Haskell versions.  I won’t go into too much depth on the theory behind the structures, but I will try to point out the interesting bits.

Without further ado, lets get rolling with our first data structure, which is also Okasaki’s first: Lists

Specifically, we’re going to implement a singly-linked list, which can be used rather effectively as a LIFO stack.  To start off lets look at the F# version of the list, which is closest to what Okasaki listed in his book.  The basic list type looks like this:

type List<'a> =
| Empty
| Cons of 'a * List<'a>

This is a simple Discriminated Union, with two options, Empty, and something I’ve called Cons in honor of the Lisp folks. The Cons option is basically a tuple containing an element of type type ‘a, and a List of ‘a.  This by itself is reasonably uninteresting, so lets actually do something with this.

let isEmpty = function
    | Empty -> true
    | _ -> false

let cons head tail= Cons(head,tail)

let head = function
    | Empty -> failwith "Source list is empty"
    | Cons(head,tail) -> head

let tail = function
    | Empty -> failwith "Source list is empty"
    | Cons(head,tail) -> tail

let rec (++) leftList rightList = 
    match leftList with
    | Empty -> rightList
    | Cons(head,tail) -> Cons(head,tail ++ rightList)

let rec update list index value =
    match (list,index,value) with
    | (Empty,_,_) -> failwith "Source list of empty"
    | (Cons(_,tail),0,v) -> Cons(v,tail)
    | (Cons(_,tail),i,v) -> update tail (i - 1) v

Here we have some basic functions, an isEmpty check, a cons method (which creates a list), the head and tail functions, along with a ++ function, which appends two lists, plus an update method which changes the value of a particular element in the list.  Notice the update and ++ functions are both recursive, and in the case of the ++ function, it is not tail recursive. This is probably ok in this case since the performance of the ++ function is O(n) where n = length of the left list.  Both of these functions are also interesting because the F# compiler is unable to optimize them by converting them into a loop.

If we look at the C# version of these same structures things look pretty much the same:

public static class List
    public static List<T> Empty<T>()
        return new EmptyList<T>();

    public static List<T> Cons<T>(T head, List<T> tail)
        return new List<T> { Head = head, Tail = tail };
public class EmptyList<T> : List<T>
    public bool IsEmpty { get { return true; } }

public class List<T> : List
    public T Head {get; set; }
    public List<T> Tail {get; set; }

    public bool IsEmpty 
        get { return false; }

    public List<T> Update(int index, T value)
            throw new InvalidOperationException("You can't update an empty list");
        if(index == 0)
            return List.Cons<T>(value,this.Tail);
        return this.Tail.Update(index - 1, value);


    public static List<T> operator +(List<T> leftList, List<T> rightList)
            return rightList;

        return List.Cons<T>(leftList.Head, leftList.Tail + rightList);

Other than being almost twice as long, there are not many differences between the C# version of this structure and the F# version In this version I’ve opted to make the empty list a subclass of the List that has the IsEmpty property return true all the time.  There is also a static Empty<T>() method which returns an empty list.  A reasonable improvement could be to make this a singleton, so that empty lists would also share reference equality. Since the ++ operator in C# is not overloadable (and is a unary operator to boot) I’ve used an overload of the + operator for concatenating two lists.  The implementations are the same as the F# versions, though honestly recursion is a little strange in C#.  We still have the same performance characteristics, where appending an element is an O(n) operation, We also have the same issues with recursion, namely a stackoverflow if we have a large enough list.  Though, honestly with the performance of the update operation overall, you should probably find a new structure before you get to the point where your going to overflow your stack.

One very nice use for this particular structure is the LIFO stack.  Rather than the typical “push” and “pop” operations, we have the “cons” and “head”/”tail” operations (in the case of pop, you have “head” which gives you the elements, and “tail” which gives you the rest of the list).  This works well because pushing and popping are O(1).  This structure is not all that different than the built-in List type in F#, without the benefit of the additional functions (filter, map, tryFind, etc).  Thought it would be reasonably trivial to implement these in a recursive fashion.


That’s it for this segment…up next we’re going to look at using an immutable binary tree to implement a Set….good stuff for sure.




  • Pattern matching is just awesome.


As of yesterday the comments on the blog here are now officially hosted by Disqus. If anyone has tried leaving comments in the past only to have them never show up (or disappear at some point), I apologize for that. The spam was a little crazy….and by a little crazy I mean effing insane, It got to the point where I was unable to separate the wheat from the chaff, and went through a couple different strategies to try and get things under control…Disqus is the latest (and hopefully last) of these strategies.

So I hope you enjoy the new and improved, and not quite so spammy comment system.

Tentatively subtitled: “How scale can make fools of us all”

This is going to be a real life war story…cause I haven’t done one of those in a while, and this particular case really ticked me off.  Here’s the scoop:  I’ve got a “service” which is called by other parts of the system.  And by “service” I don’t mean something running in its own process and waiting for SOAP/REST requests or messages, I simply mean something that has a defined entry point (a static method in this case), where you pass in some data, and get something back.

Like many others, I’m sure, I’m using an IoC container to wire up bits so that I can have a big ball of interfaces “to make testing easier” (one of these days I’ll break that rather nasty habit and figure out a better way to do thing, but I’m getting off topic).  Specifically, I’m using Windsor for my dependency injection because it seems to have become the Container de jure among the devs that actually are using containers at work (StructureMap was in there for a while too, but it seems to have faded).  As many of you may know, Windsor is one of those containers that tracks instances for you so that it can use a Lifecycle rule to decide whether to give you an already existing instance of an object, or create a new one for you. It will also automatically call Dispose() on IDisposable objects that it may be tracking, thus helping ensure proper cleanup of resources.

In my case I had everything set up using the Transient lifestyle, because each request was essentially stateless, and there really wasn’t a lot of expense involved in creating a new instance of the objects.  Because I’ve done my homework, I know that if you’re using Transient objects in Windsor, you should explicitly call Release on the container to release the object when you’re done with it, otherwise you’re likely to get a memory leak, since the container would be holding on to an instance of the object, not letting the GC do its thing.  So, I made sure I did that, and my code looked something like this:

var myService = _container.GetService<IMyService>();

The one thing to point out here, is that my reference to _container was a singleton, so I would get it set up the first time and then use the pre-configured container after that. So, where is the problem? Anyone? Well, I didn’t see anything wrong with it. And neither did the person doing the code review.  But, as you might guess from the fact that I’m writing about this, there was a problem, and here’s how it manifested itself:

Approximately 6 days after this went to production, one particular set of servers in one of our data centers (lets say for the sake of this post we have 2) started kicking out OutOfMemoryExceptions during calls to the service.  My first thought was, “strange, but I’m doing the right thing here and releasing, so its probably just something else eating up memory and my code is suffering”.  To help demonstrate this I even set up a test running 1000 calls to the service in a while loop and watching the memory…nothing unusual, hovered around 33MB.  So I fired up the most excellent dotTrace memory profiler, and it confirmed.

4 more days go by and our operations folks come and beat the crap out of me because they have had to reboot production servers every couple of hours.  Ok, they didn’t beat the crap out of me, but they wanted to, and they did send along a dump, which one of the other devs who is a wiz with windbg was able to translate into something meaningful for me.  The dump showed thread contention in ReaderWriterLockSlim.WaitOnEvent(), and about 200MB worth of an object called Castle.Microkernel.Burden.  And here are some other interesting details:  The service is called by all kinds of different servers; Web servers, SOAP servers, REST servers, but none of these were showing problems.  The only one that was having issues was a server that was set up to process asynchronous SOAP requests (don’t ask).  And each server could process up to 20 at a time.

Armed with this information I did some googling, and discovered that the Burden object is the thing you leak when you don’t call Release() on the container in Windsor….But I was calling release!  I found a blog post by Davy Brion that talked about getting leaks when using your own Windsor container with NServiceBus, and how to deal with it….seemed interesting, but it also seemed like something that didn’t apply, since the problem there was that NServiceBus didn’t know about calling Release() since it was written with a container that didn’t keep references.  It did lead me to the source code for the release policy, which showed me something very interesting.

The Windsor object tracking is basically doing some reference counting.  The ReaderWriterLockSlim is being used to manage the count of instance references, so when you create a new instance it is incremented, and when you release an instance it is decremented.  In either case you’re doing a write, so you’re calling a ForWriting() method on a lock wrapper, which is effectively trying to do a write lock (at some point down the call stack)….very interesting.  At this point I decided to see if I could reproduce the problem, and so I took my earlier test running 1000 calls in a loop, and kicked it up a few notches on the concurrency scale, and set it up to run calls in a while loop until the thread was canceled. I fired up 25 threads to do this, launched the little console app and waited.  Sure enough I was able to see in process monitor that memory was rising….there were some spots where a large collection was taking place, but it wouldn’t release everything, and so soon my little app which started at around 40 MB was using 50 MB, then 60 MB.  It was the concurrency!  The multiple requests were stacking up new instances of object, and new instances of the Burden object faster than they could be collected because the whole thing was bottle-necked by the ReaderWriterLockSlim!

So I plugged in a version of Davy’s code to fix the NServiceBus issue, only I decided since I was managing this container local to my service, and I was also dealing with any Disposables myself, that I would not let it track anything (there is actually a built-in policy object for not tracking anything…just realized that).  Plugged it in, fired up the test, and I had a little console app that ran for about an hour and hovered at about 40MB of memory in use.

We actually did an emergency deployment to push this to the effected set of servers in production, and I’m happy to say that so far I’ve not seen an issue….of course our logs stopped showing the OutOfMemory exceptions about 24 hours before we pushed the fix, so we have that to help out our feeling of doubt that the issue is resolved.  And even though I could create something suspicious locally, we were never able to recreate the production issue in QA.  One of the interesting things about our environment is that we have a lot of customers who do things that we don’t exactly expect, or want, them to do.  It looks like in this case we had some customers who were doing a lot of asynchronous calls and they just managed to stack up in a way where things got ugly.

As I have been trying to learn more about Scala, there have been several paths that I’ve had to follow.  One is getting acquainted with the state of Java development, since ultimately Scala exists within the Java ecosystem.  Another is finding my way around the Scala libraries, tools, and idioms.  But there is a third that seems to be somewhat deeper, and that is coming to grips with the functional nature of the language.

Being a hybrid object-oriented/functional language means that for people used to imperative development, you can start with the idioms you already know, and add in the things you don’t.  In my case I’m really comfortable with OO programming, and I’ve gotten over the initial paradigm shift that C#/.Net 3.5 brought in with Lambdas, Closures, and Linq-style functional composition.  With that I could quickly latch on to some of the basics in Scala, like using the map method on a list to transform it, since it is effectively the same as select in C#.

Thing began to get a little shakier once I started digging deeper into some of the functional aspects of the language.  List Comprehensions in Scala took me rather off-guard until I realized that in .Net, list comprehensions are called “Linq queries”, though the syntax was still tripping me up.  I also started digging in to Higher Kinded Types aka Type Constructor Polymorphism, and in looking for examples inevitably I was led to more functional constructs.  Eventually I found myself looking at things like Functors, Monoids, and the dreaded Monad. The problem I ran into, though, was that for the most part, these concepts were described in the various blogs in terms of their equivalents from purely functional languages, and the most often cited purely functional language was Haskell.

Clearly the only way I was really going to understand these concepts was to learn Haskell….if nothing else I needed to at least be able to understand those crazy type signatures with all of their arrows pointing all over the place. Almost against my own will I’ve been forced to read a lot about Haskell, and to be honest I’m really glad that I did.

As strange as functional concepts are when coupled with the already familiar Object Oriented world, getting your head around a purely functional language is harder.  You have to forget about things like “classes” for containing data, and encapsulation within objects, not to mention polymorphism via sub-classes (or interfaces).  The concepts of encapsulation and polymorphism still exist in Haskell, they’re just different.  More importantly there are elements of the language that are brilliantly simple and elegant (at least to me).  The default style seems to be taking small pieces of functionality, and composing them to make something that is powerful (something of the holy grail in the OO space).  The downside to this is that you can have very small segments of code which are extremely dense, and as a noob it’s difficult to understand why some things happen in the way they do.  But things are getting easier with more exposure.

At this point I’m wanting to really grok the language and the idioms used to build software in a purely functional way, and I’ve gone well beyond just learning enough to understand references in blog posts about Scala.  As such I’ve set myself a goal of completing a project in Haskell that I’m keeping under my hat for the time being…mostly because I don’t know that I’ll ever actually finish it.  One of the more interesting aspect of this for me is the fact that I really don’t know where to begin to build something in Haskell.  Normally I would start thinking about objects and relationships, and that doesn’t apply here.  It’s an interesting state to be in.

So now the question is “do I abandon Scala/C#/Wahtever?”  Of course not.  As impressive and powerful as Haskell is (and trust me, it is a lot of both), and in spite of the fact that there are native compilers for every platform known to man (more or less), and the libraries available are extensive, it doesn’t seem to have a huge footprint.  It’s kind of a shame, since there are things like STM and compile-time parallelization (yes, that’s right), and seems like a good fit distributed computing in general.  For now I’ll let it open the door to new and different ways of solving problems….and maybe eventually see if I can sneak something small into production.

Continuing our journey down the path from the familiar to the down-right bizarre, we find ourselves at Pattern Matching.  This is a feature of the Scala language that shows it’s functional side in a strong way.  Pattern Matching is a fundamental part of functional languages in general, and provides a way to write very concise and expressive code.  On the surface, pattern matching in Scala looks an awful lot like switch statements in C# (and Java for that matter), but you shouldn’t cling too hard to that association.

The Basics

Let’s start with a basic example that mimics the behavior of a switch statement.  Here is a quick sample entered directly into the Scala interpreter:

scala> val x = "Hi"
x: java.lang.String = Hi
scala> x match {
     | case "Hi" => "Hi yourself"
     | case "Ho" => "Am Not!"
     | case _ => "What?"
     | }
res1: java.lang.String = Hi yourself

Yes, this looks really boring…but the syntax should be clear. The Pattern Match is invoked using the match keyword, followed by a block containing case expressions. It’s worth pointing out at this point that the match is an expression, which means it has a value when evaluated (which is why the result from the interpreter is a string, and we don’t have/need any return statements). This means that the results of the match can be assigned to a variable, or used as the return value of a function. The case statements in this example are simple, they match against string literals. The exception being the last, which uses the special wildcard match expression _.  As may be expected, evaluation happens in order, and the first expression which contains a matching pattern is the one that is executed.  Had the previous example placed the wildcard pattern first, then that would be evaluated every time, regardless of what value is passed in.

Now if this is all you could do with Pattern Matching, it wouldn’t be all that interesting, and I probably wouldn’t be sharing it with you.  The cool thing about Pattern Matching expressions is that you are not limited to literals or enum values like you are with C#.  One of the things you can do is match based on type:

x match {
    case x:String  => "You gave me a string: "+x
    case x:Int     => "You gave me a number: "+x.toString
    case x:MyThing => "You gave me some thing: "+x.toStirng

A contrived example to be sure, but as you can see it is really easy to handle different types using the standard Scala type notations.  The return value of the match expression will be the most specific type that is the result of all possible expressions.  You need to be a little careful with this, since if a match expression appears at the end of a function, then the function’s return value will be the same as the match expressions.


Now, type based matching is pretty cool, and honestly I’ve wished for this kind of functionality in C# before, but there is more.  One of the primary uses for Pattern Matching in purely functional is for deconstruction of data structures.  By this I mean extracting values from data structures so you can use the data elements directly.  A quick example using a basic tuple would look like:

x match {
    case (y,z) => "A tuple with "+y+" and "+z
    case _     => "Something else"

If x is a tuple, then this expression will print the values of both elements. The pattern (in this case (y,z)) binds the variable y to the first element in the tuple, and z to the second. If, for example, you didn’t care about the value of the second element in the tuple, then you could use the wildcard character in the pattern:

x match {
    case (y,_) => "The first element from the tuple is "+y
    case _     => "Something else"

A common use for Pattern Matching in functional languages is to split a list into it’s head (fist element) and tail (every other element). You can do this in Scala with a pattern that looks like:

list match {
    case Nil      => "Empty list"
    case x :: Nil => "Single element list: "+x
    case x :: xs  => "List has a head of "+x +" and tail: "+xs.map(_.toString).reduce(_ + ","+ _)
    case _        => "Not a list"

Looking at the patterns here, we have some interesting options. The first matches agains Nil, which is an empty list. The second uses the pattern x :: Nil, which is a list with a single element (and binds that element to x). The next pattern x :: xs divides the list into head (bound to x) and tail (bound to xs) segments. These are the standard three types of matches you see when pattern matching against lists.


This ability to deconstruct objects is not limited to standard built-in types.  Scala has a generalized pattern called Extractor Objects which provide a way to create objects that can be used in Pattern Matching.  Lets put together another cheesy example to demonstrate this:

class MyThing(val one:Int, val two:String)

object MyThing {
    def apply(thing1:Int,thing2:String) = {
        new MyThing(thing1,thing2)
    def unapply(x:MyThing):Option[(Int,String)] = {

val m = MyThing(2,"one")

m match {
    case MyThing(y,z) => "MyThing with two items: "+y+" and "+z
    case _            => "Not a MyThing"

For sake of completeness I’ve included the apply method, which (you may recall) is how you create objects in Scala. It also provides some context for the unapply method so things are a little less confusing  Since Pattern Matching performs deconstruction, it seems only logical that the method that does this work is called unapply. This method may look a little funny, but basically this is what happens. The item you are doing the match against is passed into the unapply method. If the method returns a Some value, then that is the expression that is evaluated, otherwise it moves on to the next. Also, if the item doesn’t match the type of the argument to the unapply method, then it will skip that expression. If you’re unapply returns a Some[x] then that value gets bound to the variables. In this case we have two, so we’re returning them in a tuple.

Case Classes

Now, this is cool, but there is a lot of typing involved. Scala has a handy-dandy short-cut for doing this sort of thing called Case Classes. A Case Class allows you to define a basic class, and it automatically adds the companion object type with apply and unapply methods, along with accessesors for any constructor arguments. So, using Case Classes we can rewrite the previous example as:

case class MyThing(one:Int, two:String)

val m = MyThing(2,"one")

m match {
    case _            => "Not a MyThing"

As you can see, this removed the need for the companion object all together. Granted, all of the code is still there after the magic from the compiler, but there is way less typing involved.


As if Pattern Matching wasn’t cool enough, you can further refine results from the match using Guards. This basically gives you a way to add additional conditions to a pattern using standard expressions which evaluate to a bool. Building on our previous example, we can do some more complex matching on the individual properties of the object within the pattern. It looks something like this:

x match {
    case MyThing(y,z) if y &gt; 10 =&gt; "MyThing.one is more than 10"
    case MyThing(y,z) if y &gt; 5  =&gt; "MyThing.one is more than 5"
    case _                      =&gt; "MyThing doesn't meet criteria"

The if right after the pattern defines the guard. You can use standard boolean operators like || or && as well, but the more complex things get the less readable things tend to be.

Hopefully I’ve given at least a little glimpse into the coolness of Pattern Matching in Scala.  The coolness of patterns is used in several different places in the language, including in the Regular Expression library, which gives a really easy way to check against regex matches, and extract elements from the regex if that’s the sort of thing you’re into.  We’ll be seeing more Pattern Matching as we start delving into more functional aspects of Scala.  Hopefully you’ll be able to appreciate the elegance and simplicity it can provide.



Quick introduction to git-tfs




TFS Branches and Remotes


[tfs-remote "default"]
    url = http://mytfsserver:8080/tfs
    repository = $/TFS/repo
    fetch = refs/remotes/default/master


Working with a new branch


[tfs-remote "release"]
    url = http://mytfsserver:8080/tfs
    repository = $/TFS/release
    fetch = refs/remotes/release/master


git checkout -b release


git tfs fetch -i release


git merge -X theirs refs/remotes/tfs/release





Committing your work back to TFS






What about Shelf-Sets?






git tfs shelve -i <remote> <shelfset name>



A few more tips



@echo off

