First-Class Patterns

I recently came across Mark Tullsen's paper on First-Class Patterns, and I was wondering if anyone ever applied this work. I know there has been other work in reconciling pattern matching with abstraction, most notably Wadler's views as featured in Haskell and F#, but Tullsen's approach is an interesting contrast for its simplicity and effectiveness.

Scala

Scala's extractors are functions of type a -> Maybe a. The compiler automatically generates extractors for you when you create (G)ADTs, but you can write your own new ones or replace compiler generated ones if you wish.

That said, the libraries don't come with the pattern combinators mentioned in the paper. Pattern matching in Scala is syntactically similar to what you find in Haskell and ML and other than the use of extractors the compiler generates pretty much the same kind of code for pattern matches.

By James Iry at Wed, 2008-11-12 21:39 | login or register to post comments

Scala's extractors are

Scala's extractors are functions of type a -> Maybe a.

Should that be "a -> Maybe b"? That's the type of a pattern from the paper.

I also wonder how GADTs can fit in all this. This Maybe destruction isn't necessary, since we know in the function's type specifically which case it matches.

By naasking at Thu, 2008-11-13 14:38 | login or register to post comments

You're right

It's "a->Maybe b". And F#'s active patterns can do the same.

// Scala
object Twice {                              
   def unapply(z: Int): Option[Int] = if (z%2 == 0) Some(z/2) else None
}

// F#
let (|Twice|_|) (z: int) = if (z%2 == 0) Some z/2 else None

Usage:

// Scala
x match { case Twice(n) => Console.println(n) }

// F#
match x with Twice n -> Console.WriteLine(n)

By matthias becker at Thu, 2008-11-13 15:22 | login or register to post comments

Oops

Sorry, you're right, the input and output types don't have to be related.

I'm not sure I follow on your question about GADTs.

By James Iry at Thu, 2008-11-13 20:47 | login or register to post comments

Pattern functions are

Pattern functions are partial in the match and made total via the Maybe type + monadic composition. On the other hand, a GADT pattern function is necessarily total in its match. I was just noting there's probably a way to construct total pattern match functions on sum types if one could to treat sum cases locally as GADTs and compose the cases as in this paper. I hope this makes some kind of sense. :-)

By naasking at Thu, 2008-11-13 22:09 | login or register to post comments

"First class patterns", I would think..

would be like "First class macros".

A function from a code-object (an abstract syntax tree, or some other reification of program code) to code-object.

Obviously, some patterns translate easily into non-meta code in some languages; but others do not.

By Scott Johnson at Thu, 2008-11-13 00:07 | login or register to post comments

I had been considering a

I had been considering a first-class patterns as similar to a pattern constructed from typed code objects ala MetaOCaml, but the connection to macros hadn't occurred to me.

By naasking at Thu, 2008-11-13 00:39 | login or register to post comments

Talking about the same "patterns?"

I could be wrong, but I'm reading Scott's post as being about "design patterns" while the original paper was about "pattern matching."

By James Iry at Thu, 2008-11-13 01:21 | login or register to post comments

You would be correct

My comment has nothing to do with pattern matching; although performing pattern matching/substitution on reified code could certainly be a useful means of metaprogramming.

By Scott Johnson at Thu, 2008-11-13 01:55 | login or register to post comments

Perhaps an administrator

Perhaps an administrator could either approve a user's first post or make them go through a CAPTCHA? CAPTCHA is kind of inconvenient and unreliable. Manual verification would be better for the new user's first post, to make sure they aren't a SPAM-bot and that they are legit users. Of course, someone has to verify these first posts...

By Sean McDirmid at Mon, 2009-02-09 13:41 | login or register to post comments

Make it a community task...

Make it a community task... simply have a 'mark as spam' button for messages for 'young' users, and a few such marks from a few different readers (e.g. 3 readers) gets all those user's posts, and said user account, deleted.

I think the community can be trusted to not abuse that power, but such abuse can be audited easily enough if it occurs.

A 'young' user might be heuristically judged in days counting from first post rather than time of account creation (in order to prevent sleeper spammers).

Anyhow, it might be better to move discussion like this to a different forum.

By dmbarbour at Tue, 2009-02-10 02:15 | login or register to post comments

Question on the paper

As a FP dilettante (that's like an amateur without the talent) there's one question which, while trivial, I would like to ask.

I'm working with a language called CAL (http://openquark.org) which lacks most of Haskell's pattern matching sugar, so this approach is interesting.

In the following code, needing the explicit lambdas seems a bit ugly:


data V = A | B;

// my manually created A# and B#
matchA v = case v of A -> Just (); _ -> Nothing;;
matchB v = case v of B -> Just (); _ -> Nothing;;

showV =
       (
           (matchA `matchCompose` (\x -> "A")) `matchOr`
           (matchB `matchCompose` (\x -> "B"))
       ) `applyPattern`
       (\v -> error $ "Match failed");

matchCompose is .->, matchOr is .| and applyPattern is |>

Would something like the Monad '>>' operator be useful to combine patterns where you are only interested in success, or am I missing something?

I'm thinking of something like:


matchSeq p v x = case p x of Just r -> Just v
                             Nothing -> Nothing;

But perhaps there's a more sensible way of doing that?

By tom davies at Sun, 2009-02-22 10:52 | login or register to post comments

...something like the Monad '>>' operator...

Yes, definitely. I recommend reading Tullsen's paper referred to in the post. You can find it with Google/Citeseer (or, at least, I did). Actually, you can also just download it from the old LtU post referred to in this post.

Edit: Oops! Before hitting the post button, I just assumed this post/question was about Morten Rhiger's Functional Pearl: Type-safe pattern combinators, which was discussed here not too long ago. At any rate, as Tullsen's approach is based on Monads, you get the sequencing operator >> for free. You can of course implement >> in terms of the >>= and return operations as usual.

By Vesa Karvonen at Mon, 2009-02-23 11:07 | login or register to post comments

Lambda the Ultimate

User login

Navigation