The Functional Language Gateway Drug

Feb 15, 2009 code suggest edit

Alternate Title: Linq, it’s not just for SQL.

I admit, I’m not very proficient with functional programming. It almost feels like a gang war at times - on one side of the tracks is Turing’s crew, sporting their imperative ways. On the other side is the Church group, luring wayward souls onto their turf with the promise of code salvation in the form of functional language.

Matt Podwysocki is one of those Church evangelists, constantly reaching out to me, a lost soul, with the promises of eternal code salvation in the form of F#. I keep meaning to check it out, but you know how that goes.

What I’ve slowly come to realize though is that the more I use and understand the Linq extensions in C#, the more functional my programming has become in certain cases.

It turns out that C# is the ultimate gateway drug for functional programming^1^. It has just enough functional elements to give you a taste for functional, but with enough friction at times (for example, the type inference is not as good as F#) that it may slowly push me over.

Let me give you a recent concrete example using Subtext. One of the features Subtext has is the ability to take the title of a blog post, and automatically generate a URL slug from the title.

Slugs have to be unique, so we want to make sure that the slug we generate doesn’t conflict. For fun, I implemented it in such a way that we could handle up to 6 conflicts.

For example, suppose you wrote a blog post entitled “Hello World”. The first time you published it, you would have the slug “hello-world”. When you wrote and published a new blog post with the same title, we’d append “again” to the end. Here’s what would happen if you kept repeating this process.

hello-world
hello-world-again
hello-world-yet-again
hello-world-and-again
hello-world-once-again
hello-world-to-beat-a-dead-horse
We throw an exception

Yeah, it’s kind of a stupid feature. I doubt anyone would ever post more than two blog posts with the same title. In a way, it’s a bit of an easter egg. The original code for this was very imperative. Here’s the gist of the code:

string EnsureUniqueSlug(string slug, string separator) {
  Entry currentEntry = Repository.GetEntry(slug);
  int tryCount = 0;
  string newSlug;
  while (currentEntry != null) {
    switch (tryCount) {
      case 0:
        newSlug = slug + separator + "Again";
        break;
      case 1:
        newSlug = slug + separator + "Yet" + separator + "Again";
        break;
      case 2:
        newSlug = slug + separator + "And" + separator + "Again";
        break;
      case 3:
        newSlug = slug + separator + "Once" + separator + "More";
        break;
      case 4:
        newSlug = slug + separator + "To" + separator + "Beat" 
          + separator + "A" + separator + "Dead" 
          + separator + "Horse";
        break;
      case 5:
        throw new InvalidOperationException();
    }
    tryCount++;
    currentEntry = Repository.GetEntry(newslug);
  }
  return newSlug;
}

I was revisiting this code today, and I realized I could write this more succinctly using Linq extensions.

When you step back a moment, what I have to start with is an enumeration of suffixes. What I want to do is transform them into potential slugs, and then find the first slug where there is no matching slug in the database.

Functional languages are great for working with sets and doing transformations over sets. At least that’s what Matt tells me. Here’s what I ended up doing.

string EnsureUniqueness(string originalSlug, string separator) {
  string[] suffixFormats = new[] { 
    string.Empty, "{0}Again", "{0}Yet{0}Again", "{0}And{0}Again"
      , "{0}Once{0}Again", "{0}Once{0}More"
      , "{0}To{0}Beat{0}A{0}Dead{0}Horse" };
  var slugs = suffixFormats.Select(
    s => originalSlug + String.Format(s, separator));
  return slugs.First(slug => Repository.GetEntry(slug) == null);
}

The first line is a static array of the potential suffixes. At this point, I should really move this line outside of this method and perhaps even have this list be configurable. But for this blog post, let’s leave it here.

The second line converts the suffixes into an enumeration of slugs. I then simply call the First method on that list of slugs passing in a lambda which specifies a condition. The First method will return the first element in the enumeration where the lambda returns true.

In other words, it’ll return the first slug where the repository tells me there is no blog post with a matching slug. If there is no match, the First method throws an InvalidOperationException.

For those who are not familiar with lambdas and and the extension methods I used, the second code might be a bit confusing. But once you know what’s going on, I think it’s much more readable, simple, and shows my intent better.

It reads how I think about the problem.

Convert the list of suffixes into a list of potential slugs
Grab the first slug where there is no matching entry in the database

What would be really cool is if I could somehow switch to F# inline with a C# file. Kind of crazy, but it would be the thing that would probably get me to actually use it in a project.

For those of you who have been doing functional programming for a long time, you’ll probably scoff at this simple example, but for an old imperative programmer like me, it feels like a new world opening up.

^1^After I wrote this, I realized that Ruby might actually be the ultimate gateway drug for functional programming. But I’m kind of focusing on static typed language afficionados, so forgive me. ;)

Found a typo or mistake in the post? suggest edit

Comments

23 responses

Jonas • February 15th, 2009
As an imperative programmer myself I think the first implementation is easier for interpreting your intent. Maybe it's the fact I spent many more years writing imperative programming than lambdas, but I really have to spend a greater deal of time interpreting them than imperative code.
Just my $0.02
haacked • February 15th, 2009
@Jonas yeah, I think it's really a matter of preference and being accustomed to the different style.
Ayende Rahien • February 15th, 2009
Both version suffer from one problem.
The error that they generate don't give you any information about the actual problem.
Oh, and I am pretty sure that I would hit that particular exception at some point.
After 3,800+ posts, I am bound to repeat the titles.
Leniel Macaferi • February 15th, 2009
Hi Phil,
I think that functional programming really rocks!
For example, in your first implementation using imperative programming you have 30 lines of code. With the second and more fluent functional programming implementation you have only 9 lines of code, that is, 1/3 of code reduction.
To me the second implementation is far better to understand! As you said: it reads how I think about the problem. This is the point.
Yeah, C# with LINQ is being transformed in a good functional gateway drug. :)
I'm an old reader of your blog. It's a great source of information.
Keep up the great work.
Leniel Macaferi
Derek • February 15th, 2009
F# doesn't save you too much here ...
let EnsureUniqueness originalSlug separator = let suffixFormats = [ String.Empty; "{0}Again"; "{0}Yet{0}Again"; "{0}And{0}Again"; "{0}Once{0}Again"; "{0}Once{0}More"; "{0}To{0}Beat{0}A{0}Dead{0}Horse" ] in let format s = String.Format(s, (separator:string)) in Seq.map ((+) originalSlug << format) suffixFormats |> Seq.find ((=) null << Repository.GetEntry)
haacked • February 15th, 2009
@ayende, yeah, this isn't the final version of the code. It's just meant to illustrate. I could call FirstOrDefault instead and if the result is null, throw a more descriptive exception.
Joe Chung • February 15th, 2009
There's a bug in your imperative version. What if currentEntry is null before it enters the while loop? You should set newSlug to slug when you declare it in case this happens.
Aaron S. • February 15th, 2009
I find your second code sample bit more confusing. Perhaps it is because I have been an imperative programmer all my life. I think I should spend some time looking into the functional paradigm.
Boris Callens • February 15th, 2009
At Univ we worked with Scheme (a functional programming language). After a few months the programs became more and more complex. I don't know if it was because Visual Studio just beats all other IDE's out of the park , but I never found it easy to keep more complex code readable. I always ended up spending way more time to get something usefull running then I could do so in C#.
Maybe I should have a look at F# some day to see what a functional language is like in a real IDE.
Victor Kornov • February 15th, 2009
In your first code snippet I don't see where you increment tryCount. Bug?
nefajciar • February 15th, 2009
should't you increment tryCount int the imperative example?
Yaron • February 15th, 2009
Not relevant to the functional programming issue, but in the case of post slugs why not simply add numbers? Sure, nobody is likely to do more than 6 "Hello World" posts, but there are plenty of people who like to post around "Weekly Review", "Monthly update", "Happy Birthday to Me", etc, etc.
Now, it may be nicer to stick full dates into the title of those posts, but why force people to do so if they don't want to?
Craig Lebowitz • February 15th, 2009
Having cut my teeth on Scheme I am also a fan of the functional approach and Linq.
For this function, I was thinking a recursive approach could work nicely. Just keep suffixing with "-again" or incrementing numbers
e.g.
void Main()
{
var existingSlugs = new List<string>
{
"i-was-haacked",
"i-was-haacked-again"
};
Func<string, bool> isUniqueSlug = (slug) => !existingSlugs.Contains(slug);

existingSlugs.Add(GetUniqueSlug(isUniqueSlug, "i-was-haacked"));
Console.WriteLine(GetUniqueSlug(isUniqueSlug, "i-was-haacked"));
}
string GetUniqueSlug(Func<string, bool> isUnique, string slug)
{
return (!isUnique(slug))
? GetUniqueSlug(isUnique, slug += "-again")
: slug.ToString();
}
Thanks for the great blog, Phil and MVC rocks
Aaron Erickson • February 15th, 2009
I've been saying for over a year to anyone that would listen that C# and Linq is the gateway drug that will lead you to shooting up F# in a dark alley in a couple of months :)
Most complexity in our code comes down to loops, conditionals, and transformations, which is exactly what functional approaches make simple.
Chris hynes • February 16th, 2009
In this case at least you can do this just as succinctly, and maybe more understandably with imperative code:
foreach (string format in suffixFormats) { string slug = originalSlug + String.Format(s, separator); if (Repository.GetEntry(slug) == null) return slug; } throw new InvalidOperationException("couldn't auto generate slug");
I never use Linq expressions when imperative code functions just as well. Why make the code more complicated and have possible unknown overhead calling into Linq?
Justin Chase • February 16th, 2009
This probably isn't why you wrote this post but I would just like to say that it is probably advisable to have more than just six variations for your "slugs". For example, the pharyangula blog regularly has a blog post entitied "I get emails", where he features some crazy emails he received recently. So it's totally reasonable to have many posts with the same title.
haacked • February 16th, 2009
@Justin it is possible to manually set the slug when you write a blog post, so there's always that option. I wonder if I should just append a number at the end after the first six cases so there's an infinite possible titles for those who are lazy. ;)
@others, yeah I need to increment tryCount.
David Fowler • February 16th, 2009
How about using the query syntax to mash it into one big query.
(from format in suffixFormats
let slug = originalSlug + String.Format(format, separator)
let notExists = Repository.GetEntry(slug) == null
where notExists
select slug).First()
Matt Ellis • February 16th, 2009
var results = from slug in GetAllSlugs(originalSlug)
where Repository.GetEntry(slug) == null
select slug;
return results.FirstOrDefault();
Even easier, and very easy to read.
Pat Gannon • February 17th, 2009
If you were using Linq2Sql or Linq2NHibernate, I wonder if it would be possible to re-write your call to First() as a Linq query that hits the DB only once by joining your list of slugs with your data source. Make sense? That would be a pretty kick-ass implementation!
Alternatively, I wonder if you could specify your slugs in an XML file, and then write a query that joins that to the data source... perhaps that's going too far. ;-)
Take care,
Pat
meisinger • February 17th, 2009
wouldn't it be easier to return a count from a StartsWith() (or a like '{0}%') with the title and if the count is greater than n throw an error other wise look for a string in a dictionary where the key is (count+1)?
e.g.
// this dictionary could be loaded from
// an xml file or csv file from a static class
Dictionary<int, string> slugMap = new Dictionary<int, string>();
slugMap.Add(2, "{0}{1}again");
slugMap.Add(3, "{0}{1}yet{1}again");
...
string EnsureUniqueSlug(string slug, string separator) {
var entryCount = (from e in context.Entries
where e.Slug.StartsWith(slug)
select e.EntryId).Count();
if (entryCount > slugMap.Count)
throw new InvalidOperationException("Ouch...");
if (entryCount > 0) {
var slugFormat = slugMap[entryCount+1];
return string.Format(slugFormat, slug, separator);
}
return slug;
}
i'm sure there are several ways to skin that cat
or you could leverage the yield return to iterate
Helen • February 24th, 2009
For me javascript was my gateway functional language. :)
Rob • March 1st, 2009
I looked at the comments to say the same as Chris Hynes; the problem isn't that you're programming imperatively, the problem is you're using a switch where you don't need to: inside a while loop when you know that options will gradually be eliminated.
You could do it in 4 lines (IRL you'd add 4 for formatting, though, and 1 more to pull out "slug + String.Format(s, separator)" into a temp var). But here it is (half of this is Mr Hynes' - I take no credit!):
string EnsureUniqueSlug(string slug, string separator) { string[] suffixFormats = new[] { string.Empty, "{0}Again", "{0}Yet{0}Again", "{0}And{0}Again", "{0}Once{0}Again", "{0}Once{0}More", "{0}To{0}Beat{0}A{0}Dead{0}Horse" }; foreach (string s in suffixFormats) if (Repository.GetEntry(slug + String.Format(s, separator)) == null) return slug + String.Format(s, separator); }