## Purely Functional Data Structures–Part 2

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
else
true

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 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;
while(!currentTree.IsEmpty)
{
if (element.CompareTo(currentElement) == 0)
return true;
if (element.CompareTo(currentElement) == 1)
{
currentTree = currentTree.RightSubtree;
}
else
{
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>() };
switch(element.CompareTo(tree.Element))
{
case 0:
return tree;
case 1:
return new Tree<T> { RightSubtree = tree.RightSubtree, Element = tree.Element,
LeftSubtree = Set.Insert<T>(element,tree.LeftSubtree) };
default:
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.

## Purely Functional Data Structures–Part 1

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

| Empty -> failwith "Source list is empty"

let tail = function
| Empty -> failwith "Source list is empty"

let rec (++) leftList rightList =
match leftList with
| Empty -> 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)
{
}
}
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)
{
if(this.IsEmpty)
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)
{
if(leftList.IsEmpty)
return 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.

## A quick (?) retrospective on learning (and using) F#

As you may have guessed from the title, I’ve started doing some work with F#.  Initially I was somewhat reluctant to go down the F# path because some of the more interesting aspects of the other functional languages I’ve been exploring are not present…specifically the type systems behind Scala and Haskell, the laziness of Haskell, and the concurrent programming model of Erlang.  In spite of these perceived downfalls, there were some definite plusses, namely interoperability with everything .Net, immutability by default, and the wonderful concise programing model of a functional language.

Shortly after reading the book I decided to actually try writing something real and useful…this proved to be a bit more of a challenge.  There are a few reasons for this…a big part was that organizing a functional project is different than organizing an OO project.  This was complicated by the fact that the first task I set myself on was re-writing something I had in C# in F#.  This was supposed to be more than just a syntactic translation, but also an attempt to see if my hunch that the problem being solved was effectively a functional problem, and so would lend itself well to a real functional language.  The problem was I was used to thinking about the problem in terns of the classes I had already created, and in F# those concepts were not there.  Before long, though, I had adjusted my thinking, and the more time I spent working on the problem the more I found myself enjoying F#.  After that initial experience (which was mostly academic, in that it was not intended to go “live”) I found myself wanting to explore more with the language, and so I’ve been looking for reasons to use it.  I’m not going to go into all of the ways I’ve managed that here, but I did want to share some observations:

• My initial reluctance based on the perceived drawbacks were largely my own naivety.  While it is true that there are no higher-kinded types, and therefore no type constructors, this does not make the programing experience that much worse.  Granted there are some kinds of things that will be duplicated, which folks using Haskell would be able to do away with by harnessing the power of the type system, but this does not make F# useless by any stretch.  As a matter of fact F# exposes some capabilities of the CLR that C# does not, including being able to specify wildcard types, which allow you to say “I have a parameterized type, but I don’t care about the specific type of the parameter”, and even some Structural Typing, which provides a way to constrain types by specifying the methods those types should have.
• The let construct is deceptively simple when you first encounter it.  Initially it seems like just a way to specify a variable or function name…it becomes interesting though when you realize that the fact that there is a single construct for both means that the two are effectively the same thing. Combine with this the fact that they can be nested, and you have an extremely versatile construct.  I assume this comes directly from the OCaml heritage of F#
• Pattern matching is just awesome.
• Working with Object Oriented concepts is jarring, and feels….awkward.  I have no proof, but I can’t help but think this is intentional. While F# is not a “pure” language like Haskell, it still tries to be “functional by default”.  The standard types that you work with all the time, like tuples and lists, are immutable, as are the let bindings.  You have to be specific if you want the mutable versions of any of these.  I can’t help but think the fact that it is easier (or should I say more natural) to work with pure functional types and immutable data structures is a design feature of the language.

The biggest problem I have with F# at this point is that it is clear that it is still a second-class citizen in the VisualStudio world.  While it shipped with VS 2010, a lot of the other tooling doesn’t support it.  Things like the built in analysis tools, just don’t work.  Even the syntax highlighting is less impressive than C#.  There is also the fact that there are no built-in refactorings for F#.  Event third-party tools like Resharper and CodeRush don’t have support.  This is really sad, since the language itself is really a joy to work with.  There is still a perception that it is largely academic, and you can’t do any real work in it.  This is unfortunate, since in our normal day-to-day programming lives there are some problems that are just functional in nature.  In general, functional programing is all about asking questions and getting answers.  Contrast this with OO, which stresses a “Tell don’t ask” paradigm.  If you divide your application into sections which are suited to “telling” vs “asking” then you may find that you can write certain parts functionally very easily, and others OO equally easy.  Wouldn’t it be amazing if people started choosing their languages based on the nature of the problem to be solved, rather than simply because “I’m a C# developer”.

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.

## Sometimes doing the right thing is still not the right thing

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>();
try
{
myService.DoWork();
}
finally
{
_container.Release(myService);
}```

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.

## I think Scala may be a gateway drug

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.

## Making the Climb Part 4–Pattern Matching

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.

#### Deconstruction

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.

#### Extractors

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)] = {
Some(x.one,x.two)
}
}

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 `object`s 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 MyThing(y,z) => "MyThing with two items: "+y+" and "+z
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.

#### Guards

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.

## Grappling with multiple remotes in git-tfs

If you happen to be one of the many people in the unfortunate situation to be stuck working with TFS source control on a daily basis and gaze longingly at the folks using Git or Mercurial wishing you could have some of that distributed goodness for your very own self, I am here to tell you that all is not lost.  There are a couple ways you can work with a distributed version control system along side TFS and try and reduce the pain associated with TFS.  One way I wrote about here as an answer to a question on StackOverflow.  This technique worked fairly well for me dealing with a small codebase with only a few branches.  However, it became unmanageable once I started working in an environment which had a large TFS repo with several different branches that I needed to switch between on a regular basis.  You can read about some of the issues I ran into within the updated section of the answer, but overall things got messy quickly.

The solution I have arrived at, and one which seems to be working out reasonably well so far, is to use Git and git-tfs rather than Mercurial.  This could actually apply equally to Mercurial if such a thing as hg-tfs existed, but alas no such animal can be found.

#### Quick introduction to git-tfs

The git-tfs project can be found out on Github (of course), and is based on the also very awesome git-svn project.  It takes advantage of the fact that git allows for custom commands by looking for anything on the path that has the form `git-<command>` and executing it when you type in `git <command>`.  The project is a C# project that compiles into an EXE named `git-tfs.exe`.  You drop this in your path and you’re off to the races.

Under the covers git-tfs will tag commits that come from TFS with the repository information and changeset ID, and then when you want to put your changes into TFS (as a shelfset or a commit) it creates a new workspace, adds changes not associated with a changeset from your git repo, and then when it is all done the workspace gets deleted.

Rather than go through the details of getting git-tfs installed and your repository set up I’m going to refer you to the documentation, which is not too bad, and get to the more involved scenario that this post is all about.

#### TFS Branches and Remotes

If you take a look at the config information on your git-tfs repo you are likely to see a section that looks something like

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

As you might expect this defines your TFS server and branch information. You can edit your configuration and add as many of these as you want, as long as they have unique fetch paths. The problem is that there really isn’t any documentation that talks about how this works, and so that is what I’m hoping to illuminate. For starters, I’m going to assume you have just the “default” tfs-remote configured.

#### Working with a new branch

The first thing to do is to create a new remote in your git config.  As you might guess that simply means creating a new `tfs-remote` section with a unique name.  Lets add something like:

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

This creates a new remote name “release”. The next step is to set up a git branch for this TFS branch. To do that simply create the branch the way you would any git branch:

`git checkout -b release`

Now comes the good part, we want to pull in the changes from our TFS branch into this git branch.   Git-tfs includes a “pull” command, but it has a fairly big limitation when working in this particular scenario.  It does not allow you to specify a merge strategy.  That means that there is no way to say “pull in everything and use the versions of the files on TFS if there is a conflict”, which is what we want to do.  To accomplish this, we’ll want to deconstruct the “pull” command into it’s discrete steps.  The first step is to do a get-tfs fetch against the new remote.  You do that using this command:

`git tfs fetch -i release`

This will pull in all of the changesets from the TFS branch and apply them to the object tree that sits under the covers in git. Once that is done we’ll want to merge those changes into our git branch by doing:

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

You can actually specify whichever merge strategy you want, but this is the one I generally choose (merge recursive, take the remote changes for any conflicts). Pay special attention to where we are merging from. This is the remote location that points to the HEAD of the commit tree that we just pulled from TFS. The general format of this is: `refs/remotes/tfs/<tfs-remote name>` Once you have done the initial fetch/merge you will have better luck using the get-tfs pull command, though you can still run into merge conflicts if there are a lot of changes between pulls.

The way I have been working, and a way that seems to work well, is to have a primary branch that mirrors each of your TFS branches that you may be working in, with topic branches created from there. That gives you at least one git branch for every TFS branch that is “pure”, and that you can potentially mess up without feeling too bad, since you can always fetch everything from TFS again (this assumes you have some time to kill, since fetching a lot of changes from TFS takes a while).

By the way, when you’re working with multiple TFS branches in git-tfs, the `–i <remote-name>` switch will become your constant companion.  You will need to use it on any command which may have an ambiguous parent….meaning when git-tfs goes through you’re history to find out which TFS remote to use, it’s going to look at those git-tfs-id tags on the commits, and if there is more than one source it will ask you which one you want.  When you have several branches you’ve created that represent different TFS branches, you are most likely going to have the history of the original branch lurking somewhere, so you will be needing the switch.

#### Committing your work back to TFS

Now that you have branches in git you can work with, you can use whatever topic-branching strategy makes sense when your doing your day-to-day work.  Once you are ready to commit things back to TFS, the simplest way to do that is to check your changes into git, and then issue a git-tfs check-in command (There are three, “checkin”, ‘”rcheckin” and “ct”.  I personally like the “ct” command, which brings up the TFS dialog that lists changes and allows you to specify commit messages).  When you do this, git-tfs will look through your commit history, and find the last commit with a git-tfs-id tag, and then take every commit from that point and apply it to a workspace that it creates behind the scenes. Once you check-in git-tfs then does a pull/merge from TFS (to get any changes since your last fetch), and leaves your branch with your commit on top.

Notice I said that it goes through the commit history, and looks for the first commit with a git-tfs-id tag?  This is important if your working in a scenario where you have a reasonably large change you’re working on, and you are doing periodic tfs fetches and merges into your topic branch to keep up to date with what your colleges are doing.

Lets say you’ve been working on something for 5 hours, doing periodic commits as your go, and one of your teammates tells you they’ve made a change to one of the common libraries that you are using.  At this point you’ll want to switch back to your TFS tracking branch, get the latest changes, and them merge those in to your working branch.  Doing this, though, means that git-tfs is not going to see the changes you made over the last 5 hours.  So what do you do?

You remember that you’re using git :).  Lets continue with our scenario and say you work for another two hours and complete your feature making commits along the way.  Now, you’re ready to check in to TFS.  What I’ve found works best for me is to go back to my TFS tracking branch, make sure it’s up to date, and then create a new branch for my pending check-in.  Then I do a merge into the new branch from the topic branch I had been working in, and throw a –squash on there (this is not strictly necessary, but in my environment it’s handy to have a change in a single changeset that is associated with a single change request, that way roll-back is easier).  Once the merge is done, I can issue my `git tfs ct –i release` command and all is good.  I’ve got all of my changes in a nice neat little package.

Another option available is to use the git-tfs rcheckin command, which essentially does a rebase against your TFS branch.  I’ve actually not done this, since it doesn’t fit in with how changes are handled in my organization.

I’m glad you asked.  We actually use shelf-sets for code-reviews (which are required before code goes to production).  Fortunately git-tfs has nice support for shelfsets. For starters un-shelving changes puts them in a topic branch, which is exactly what I would hope for.  To do this use the following command:

`git tfs unshelve -i <remote> [-u <username>] <shelfset name> <branch>`

(Just a quick note, the master branch of the git-tfs github repo does not contain support for the –I argument at this point.  I’ve got a pull-request in place to add it, since it was just a one-liner.  You can track it here if you need to.  You can also grab my fork of the git-tfs project here (there is a branch called UnshelveTweak that has the change) Looks like the pull request has been merged into the main git-tfs project.  If you clone/fork and do a build you should be good to go)

Hopefully this is pretty self-explanatory. The `-u` option is not required if your pulling from one of your own shelfsets. If you’re shelfset has a name with spaces in it, you should surround it with double quotes.

Shelving changes is equally easy, you just issue the shelve command:

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

Again, if you’ve got a shelfset name with spaces be sure to put quotes around it.

#### A few more tips

I’ve found on occasion that things get a little out of whack when shelving or committing changes back to TFS, and some files are included that shouldn’t be.  This usually happens when things are not merged 100% after a git tfs fetch, and there are some files that need to be committed separately.  So how do you deal with this?  Well, you rely on our friend the get-tfs-id tag.  The simplest process is to do a `git log` to see your list of changes, and copy the line that starts with `git-tfs-id:`. Then, if you’ve not committed your changes yet, add that to a new line at the end of your commit message. If you have committed you can use the `git commit --amend` command to update the last commit. Once you’ve done this you will only get new changes checked in or shelved to TFS

Another useful bit of kit is a script I whipped together that sets up a git bash shell with all of the .Net/Visual Studio 2010 tools on the path, so I can build my projects from within the git-tfs bash shell. The script looks like (I’m running a 64-bit OS, so you may need to adjust the paths):

```@echo off
call "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat" x86

I use the most excellent Console2 project, so I can just save that script to a .bat or .cmd file and add a new tab that has that file as the shell.  Now I can see which branch I’m working in while on the command line, and still build everything.

So there you have it.  It’s not 100% hassle free, but it is a lot less hassle than dealing with TFS all of the time.  I probably save several hours a week simply by not needing to wait on TFS fetches and branch changes.

## Making the Climb Part 3 – Generics of a Higher Kind

This is part 3 in a series.  If you’ve not followed-along so far, you may want to check out Part 1 and Part 2 first.

It’s time to start digging in to some of the crazy-goodness that makes Scala such a glorious and wonderful thing.  First things first, though, we have to talk a little bit about this history of Generics in Java and the JVM.

#### Type Erasure and you…

Back around the time that .Net was adding support for generics, the folks in Java land were doing the same…sort of.  The biggest difference between the way Generics were implemented in .Net and Java is the fact that in .Net generics are supported directly in the CLR (sometimes called reified generics), whereas the JVM did not include direct support for generics.  Ok, so what does that actually mean?  Well, for starters it means that when you’re dealing with Generics in Java you run into Type Erasure.  Type Erasure means that when Java code with generics are compiled, the generic type information is removed at compile time, so while you’re looking at an ArrayList<String> in Java, the JVM sees this as just an ArrayList, and things get cast as needed.  There are a couple of types which get reified into actual types (Arrays are the best example), but for the most part this doesn’t happen.  In contrast in the .Net world a List<string> gets compiled into a List`1<System.String> which is a real type at the IL level.  Now, I’m not going to get into the argument about whether or not type erasure is good or bad, but it is a fundamental difference between the two platforms.

One very interesting effect of Type Erasure is that it allows you to specify a wildcard type argument for a generic type parameter.  In Java this looks something like ArrayList<?>, in Scala this same type would be ArrayList[_].  Now, this is interesting because it allows you to side-step the whole issue of providing type arguments when you really don’t care what they are.  Now, lets back up one step real quick and talk about syntax for a moment.

Those of you with sharp eyes will have noticed that Scala uses square brackets for type arguments.  You can limit types (in a way similar to generic constraints in C#) based on other types by using the following syntax: MyType[T <: AnyRef].  In this case we’re saying the Type argument T is a subtype of AnyRef (which you may recall is the supertype for all classes).  This is known as a Type Bound, and specifically in this case an Upper Type Bound.  You could speculate (and would be correct to do so) that a Lower Type Bound works in the opposite direction, so MyType[T >: A] means T is a supertype of A.  Now, this is interesting from a theoretical perspective, but there are practical uses for this when you bring in covariant and contravariant type parameters.  Scala allows you to denote a covariant type like this: MyType[+T], and a contravariant type like this: MyType[-T].  These are equivalent to the .Net 4 variance modifiers in and out.  So the .Net version of our MyType declarations would be IMyType<in T> and IMyType<out T> respectively.  Note I added the I to the type names since in .Net type variance declarations are limited to interfaces and methods.  This limitation does not exist in Scala, so you’re free to add variance modifiers wherever you like.  Ok, so why do I say type variance becomes interesting when you combine it with type bounds?  Well, lets look at some real live Scala code and see:

```sealed abstract class Option[+A] extends Product {
...
def getOrElse[B &gt;: A](default: =&gt; B): B =
if (isEmpty) default else this.get
...
}```

So this is a chunk of code from the Scala library. This is a sample of the Option class, which is an implementation of the Null Object Pattern, that is used everywhere within the Scala libraries. If you look at the type declaration you can see that Option takes a single type parameter `A` that happens to be covariant. This is because when you have an Option of a specific type you expect to be able to get that type back out of it. However, there is also this `getOrElse` method, which will either return the item, or return the value of the function you pass in (which should return the type `A`). Now if you were to try and make the argument to the function something like `=> A` you would get a compiler error because a covariant type is appearing in a contrvariant position. This happens in C# as well, if you were to do the same thing. So the solution to this is to give the `getOrElse` method a TypeParameter, and specify a lower bound of `A`, which means `B` has to be a supertype (or the same type as) `A`.  This is particularly awesome since we would like that to be a contravariant operation anyway.  This is a very nice trick, and one I wish it were possible to use in C#.

#### Types of Types of Types…..

But the goodness does not stop there.  We’re going to head off into the land where Scala really asserts itself in terms of it’s type system.  In Scala it is possible to specify that the Type Parameter of your class/method/whatever should itself also have a type parameter (which could also have a type parameter, that could have a type parameter….you get the idea).  This is known as Higher Kinded Types (from the idea of Higher Order Functions in Functional Programing, which are functions that take functions as arguments).  A Kind in type theory is basically a higher-level abstraction over types which relates to types in basically the same way types relate to variables in terms of regular code (I know this didn’t actually help explain anything, but it sounds good right?).

You may be wondering why this is a big deal, or even what use it may have….well, lets turn to another example from the Scala library.  In this case we’re going to talk about the Map function that exists on pretty much every Scala collection (or collection-like) object.  This is a method that allows you to take a collection of one type, and turn it in to a collection of a different type…more or less equivalent to the Select() method from Linq on IEnumerable.  Now, what is really cool about the Scala Map method is that when you call it on a `List<y>` for example, and pass it a function to transform `y` into `x`,  you will get back a `List<x>`.  The important part here is the fact that it is a `List`…not an `Iterable`, not an Enumerable, not any other supertype in the heirarchy, but a `List`.  And to top it all off this method is defined at the top level of the Collections type hierarchy.  So if you create a new collection that inherits from one of the existing collection types, you get a Map method that behaves the right way free of charge.  This is impossible to do in C# without creating an implementation of the method for each object (and if you did that you would have no contract at the IList or IEnumerable level for the method).  I’ll let that sink in for a moment.  Now, there is a lot of very cool things going on in the type system which will get their own posts (or twenty) at some point, as a matter of fact Scala’s type system is actually Turing Complete in and of iteself, which makes my head hurt to thing about. But apart from that there is one more thing I want to share about Scala’s type parameters before wrapping this up.

#### A quacking all the way…..

In addition to specifying type arguments as parameters, you can actually get more granular and tell Scala you’ll take any object it’s got as a parameter, as long as it has some specific method declaration(s).  This is effectively duck typing, and makes testing really, really easy when you can use it.  The syntax for doing this looks like:

`def MyMethod(thing: { def that(x:Int) }) = thing.that(2)`

Take a long look at that for a sec, let it sync in.  Now, this is pretty good stuff by itself, but Scala’s type system gives us even more goodness.  One of the nifty things you can do is declare new types in terms of other types.  Something like aliasing….but with a lot more power, particularly when you take into account the fact that you can use the same “duck typing” syntax to define a type.  So here is what that would look like:

```class Test {
type Dog: { def bark; }

def itBarks(dog:Dog) = dog.bark
}

class Wolf {

def bark = println("Actually, I tend to howl more")

}

class Poodle {

def bark = prinln("Le bark, Le bark")
}

val test = new Test()
test.itBarks(new Wolf())
test.itBarks(new Poodle())```

So, as you can see, you can use type definitions as a form of shorthand for the duck-typed references. What’s even cooler is that you can actually define types at a package level as well, which means you can define them once in your project, and use them wherever you need them. This is something like the `using` aliases you can set up at the file level, only you can declare them at a much broader level. As a matter of fact, Scala has a special file called `Predef` that gets run before anything else in a Scala program. This file defines a lot of nifty things, like the `println` method, including several types that can be used in any Scala program (check our the source if you’d like). Pretty groovy, no?

## Making the Climb Part 2–Object-Oriented Programming in Scala

In Part 2 of this series we’re going to move into some of the object-oriented aspects of Scala.  For a primer on what Scala is, and a quick primer on syntax, check out part 1.

Like C# and Java, Scala has a built-in object hierarchy, and a standard library full of goodies.  Unlike Java and C#, Scala tackled the issue of reference types and value types head-on, so while the root type in the Scala type system is the `Any` type, there are two descendants of `Any` that come into play before any other type. The two are: `AnyRef`, and `AnyVal`. As you might guess `AnyRef` is the base type for all reference types (including types made available from Java), and `AnyVal` is the base type for all value types. This is a little bit like the `class` and `struct` type constraints in C#, only you can use these as variables. They can also be used to limit type parameters, but Scala Generics are going to have to get their own post.

There is one other interesting class that makes Scala unique from C# and Java (and maybe even other OO languages…I don’t think Ruby does this….pretty sure python doesn’t either….Smalltalk probably had it, but then Smalltalk had everything).  There is a class called `Nothing`, which is a Subclass of every class. I’ll give that a second to sink in.  Ok, got that? There is also another class called `Null` that is similar in that it is a Subclass of every reference type.  Here is a diagram of the Scala class hierarchy to make things a little clearer.

With this information fresh in our minds, lets take a look at actually putting together some Object-Oriented code.

#### The Trinity….Classes, Objects, and Traits

This was actually one of the first areas that made me go “Wow” in Scala land. Being on the JVM, you would expect it to use Java’s notion of classes and interfaces. But, interestingly, while it is built to support interoperability with Java directly, Scala starts asserting itself early on in the following way: In Scala you have three basic building blocks for OO, the Class, the Object, and the Trait. Taking these in order of most like what C# devs are used to up to the least, we’ll start with the Class. Classes in Scala are basically like C# classes…only with one significant difference: Scala classes do not have Statics. As a matter of fact there is no way to make a Class static in Scala. That’s where Object comes in. Object is basically a singleton, which you reference using static-like syntax (so Name.Method). You can create something which looks like statics on classes by using a Companion Object, that is an Object which has the same name as the Class (and is in the same file). Objects have a couple special things going on like the ability to be used as Factories for other classes, and the special apply() and unapply() methods, which allow you to get instances of object, and come into play in nifty ways when we start talking about Pattern Matching. But before we get into that lets talk about the last of the Scala OO Trinity, the Trait. So Traits are really cool….they are effectively Interfaces, only they can contain implementation. I say can, but they don’t have to. So you can use Traits in a way that is similar to the way interfaces are used, or you can add implementation, and they become Mixins. What’s more, you can create a Trait that inherits from a Class, as well as a Class that extends a Trait. You can also create Objects that inherit from classes and extend Traits. You can also attach a Trait to an instance of a class at the time you instantiate the class, which means you can add behavior to a class declaratively at the time you need it. So lets get some code samples going here, just to give an idea of what this all looks like. Lets put together a totally non-realistic example of an Animal class hierarchy:

`class Animal`

Ok, that was maybe no so helpful (but I will point out that this is valid, code…it compiles people, try it out). Lets move on to some categorization

```class Feline extends Animal {
var _lives:Int = 9

def creep {
}
def scratch {
}
def hunt {
}
def livesLeft:Int = _lives
}

class Canine extends Animal {
def howl {
}
def hunt {
}
def chaseFeline(cat:Feline) {
}
}
```

So now we have a little more to work with…not much, but it’s a start. Before we get too far, we have some duplication, so lets do a little refactoring…since both classes have a `hunt` method, we’re going to pull this out into a Trait:

```trait Hunting {
def hunt {
}
}
```

And to actually make use of this, our classes are now:

```class Feline extends Animal with Hunting {
var _lives = 9

def creep {
}

def scratch {
}

def livesLeft:Int = _lives
}

class Canine extends Animal with Hunting {
def howl {
}

def chaseFeline(cat:Feline) {
}
}
```

There, isn’t that nice? The Trait is added to the class in this case with the addition of the `with` keyword (though if there was not a base class, we would need to use the `extends`. The rule is the first item is `extends`, and any other traits use `with`). We could also do this declaratively at instantiation time if we wanted. Like this:

`val canine = new Canine() with Hunting`
` `

Before we finish up (cause I think this is plenty to chew on for a while), I want to talk briefly about visibility and overrides.  By default in Scala, everything is public…as a matter of fact there isn’t a `public` keyword at all. There are actually some really interesting options for scoping which give you more control than the `public,private,protected,internal,protected internal` options available in C#, but those will have to wait for a bit. As far as overrides, Scala does not have a `virtual` keyword. So everything is overridable (sort of). Unlike Java, if you want to override something you have to use the `override`keyword. Lets put together a quick example:

```class Animal {
def sleep {
}
}

class FruitBat extends Animal {
override def sleep {
if(isNighttime)
super.sleep()
}
}```

Again, contrived, but so are most samples on blogs. Naturally we’ll ignore the fact that `isNighttime` has no implementation, cause we can, and look at the fact that overriding existing functionality is pretty familiar to the C# dev, except for the call to `super` rather than `base`. The interesting thing to note here is that, by default, all methods can be overridden in Scala (using the `final` keyword on a method def will keep it from being overridden), and you must be explicit when you do it. This actually takes care of the complaints from folks, particularly when discussing testability, about C# requiring the `virtual` keyword to allow it to be overridden (and since everything is public by default, there is that argument too). It also takes care of complaints people have about the fact you can “accidentally” override methods in Java, since you don’t have an `override`keyword (Some IDEs will look at an @Overrides annotation, but there is nothing checked at compile time for this).

We’ve covered quite a bit, and there are still some things we could talk about, but this takes care of the basics. You can now create Object Oriented code in Scala. In our next installment we’ll dig in to the Scala concept of Generics, which actually makes C# generics look like a sad and feeble attempt at doing something interesting (while still dealing with type erasure in the JVM).