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: ...
fold - The greatest thing that ever happened to your data structure
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. ...
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. ...
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. ...
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. ...
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. ...
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. ...
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. ...
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. ...
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 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 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. ...