Found 1 comment on HN
tikhonj · 2012-07-15 · Original thread
Instead of giving you an example that anybody actually uses, I'm going to tell you about a cool idea I've been reading about that hasn't gotten much actual use.

The basic idea is to use a generalization of pattern matching. Languages like ML and Haskell support pattern matching, but in rather limited ways. Crucially, patterns are not first-class citizens of the language. (For Haskell, at least, there are some libraries to remedy this, but I don't know how effective they are.)

So how can we generalize pattern matching to help you solve your book problem? Normal patterns allow you to match data types in the form C x₁ x₂... where C is some constructor and x₁ x₂... are either matchable symbols or arbitrary patterns. An example of a pattern would be Chapter (Cons (Section content) rest). We differentiate between the matchable symbols and the constructors on case: lowercase means matchable, uppercase means constructor. This is somewhat limited: you cannot easily write code that is generic over the constructor at the head of the pattern. You could write a function that counts the sections in a chapter, but you could not write a function that counts the sections in anything.

So let's relax the restriction that patterns have to be headed by a constructor. We can now have patterns in the form x y. These are static patterns: you can match data against them without evaluating the pattern. With this, we can imagine writing a function to count sections generically:

    count_sections x = 0 -- If this is some terminal, it cannot be a section
    count_sections (Section content) = 1 + count_sections content
    count_sections (x rest) = count_sections rest
This goes through the entire data type you passed in and counts all the sections it sees. It assumes sections can be nested. This will let you count the sections in a Book or a Chapter or a Series or whatever you want.

So, this is generic over the data you pass in. However, if you wanted a function to count Chapters or Sentences or what have you, you would be forced to write it. This calls for another extension to pattern matching: dynamic patterns. Patterns are now in the form x ŷ where x is a variable and ŷ is a matchable symbol. Constructors are still uppercase, so Section is a constructor and not a variable.

A variable in a pattern can be instantiated with another pattern. So now we can write a truly generic count function:

    count constructor (constructor) = 1
    count constructor (constructor x̂) = 1 + count x̂
    count _ (x̂ ŷ) = count ŷ
So now if you want to count chapters in your book, you would just invoke count Chapter book. If you want to count sections in your chapter? Easy: count Section chapter.

You can also use patterns and constructors for polymorphism by overloading functions on different constructors. One interesting idea is to allow adding cases to functions after their definition. This way you could have an existing toString function and then, when you've defined a book, add a new case to it:

    toString += | Book title content -> "Book: " ++ title 
This way you can have a toString function that works on any type of data.

All my examples are obviously in pseudocode. (And hey, it looks nothing like Python! The whole "runnable pseudocode mantra annoys me.) I haven't covered all the edge-cases, and I haven't even begun talking about a type system for this mess. Happily, there's somebody who has, and wrote a book about it (that's where I got all these ideas): Pattern Calculus by Barry Jay[1].


I'm also not sure whether this is the best possible approach. However, I think it's certainly very neat. If you like this idea, the book is definitely worth a look.

Get dozens of book recommendations delivered straight to your inbox every Thursday.