The Functional Language Gateway Drug

code 0 comments 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.

450px-Native_American_tobacco_flowerIt 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.

  1. Convert the list of suffixes into a list of potential slugs
  2. 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. ;)

Tags: functional , linq

Found a typo or error? Suggest an edit! If accepted, your contribution is listed automatically here.

Comments

avatar

23 responses

  1. Avatar for Jonas
    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

  2. Avatar for haacked
    haacked February 15th, 2009

    @Jonas yeah, I think it's really a matter of preference and being accustomed to the different style.

  3. Avatar for Ayende Rahien
    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.

  4. Avatar for Leniel Macaferi
    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

  5. Avatar for Derek
    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)

  6. Avatar for haacked
    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.

  7. Avatar for Joe Chung
    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.

  8. Avatar for Aaron S.
    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.

  9. Avatar for Boris Callens
    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.

  10. Avatar for Victor Kornov
    Victor Kornov February 15th, 2009

    In your first code snippet I don't see where you increment tryCount. Bug?

  11. Avatar for nefajciar
    nefajciar February 15th, 2009

    should't you increment tryCount int the imperative example?

  12. Avatar for Yaron
    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?

  13. Avatar for Craig Lebowitz
    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

  14. Avatar for Aaron Erickson
    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.

  15. Avatar for Chris hynes
    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?

  16. Avatar for Justin Chase
    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.

  17. Avatar for haacked
    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.

  18. Avatar for David Fowler
    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()

  19. Avatar for Matt Ellis
    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.

  20. Avatar for Pat Gannon
    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

  21. Avatar for meisinger
    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

  22. Avatar for Helen
    Helen February 24th, 2009

    For me javascript was my gateway functional language. :)

  23. Avatar for Rob
    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);
    }