Prior art

A few weeks ago, I outlined an implementation of pattern matching in Factor. But just recently, I found a paper with a remarkably similar pattern matching system in Haskell. It's entitled "First Class Patterns" by Mark Tullsen, published in 2000 with a grant from the NSF.

On the surface, it looks completely different, but underneath, it's the same. This Haskell pattern matching system defines inverses for constructor words, with the versions Constructor for the normal constructor and Constructor# for the inverse. The inverse is failable, and can be represented as a -> Maybe b. Just x indicates a successful inverse, with the data which it yields, and Nothing indicates failure. This is analogous to what I did with exceptions. You can define your own inverse for functions as well as constructors, much like what I did with define-inverse.

Tullsen did something really cool when he generalized pattern matching to MonadPlus m => a -> m b, allowing more complex things like backtracking using the list monad. You could also give your own semantics for pattern sequencing. I haven't investigated this fully, but it may be possible to do backtracking pattern matching in Factor, also, using call/cc and, from that, amb. Another extension that we both may be able to use is more involved unification semantics along the lines of Prolog or Erlang.

A couple things about it annoyed me, though. First, it didn't really provide a good-looking syntax and wouldn't work as a drop-in replacement for existing Haskell pattern matching. Second, the implementation required a language extension for the syntax to work properly. This is a symptom of a general problem with Haskell, that the language isn't as extensible as people like to think it is. It is much more common seeing a paper which proposes a language extension than a paper which proposes an idea and provides a Template Haskell implementation of it. My last problem with the paper is that it skipped over multiargument (curried) constructors, saying "Curried constructors are allowed, but the pattern law is much more straightforward when constructors are uncurried."

But if you're interested in models of pattern matching, the paper is definitely worth a read. It's rigorous where my blog post made blind implicit assertions that something works correctly. And it provides several combinators for processing and composing patterns in a manner somewhat broader than existing pattern matching techniques. It's also interesting to look at how the type system of Haskell interacts with pattern matching, and how pattern matching based on inverses works out in an applicative language.

Anyway, I just thought that it was necessary for people to know that I wasn't the first person to come up with that version of pattern matching.

Update: I kinda rushed this blog post out initially, so I went back and edited it.