Skip to content
October 4, 2009 / cdsmith

View Patterns as Pattern Matching for Records

I’ve learned a lot in the last day about record systems for Haskell built as libraries.  I came up with what seemed like an obvious answer, and indeed it was essentially the same as two existing packages on Hackage — fclabels and data-accessor — the second of which is among the more popular downloads out there.  That’s always a good sign, that a significant number of people needed the same thing, and liked the same answer.  But there are some things, still, that are provided by the built-in package system, either as standard features or GHC extensions, that it’s unclear how to accomplish as a library.

The one that’s intriguing me most right now is pattern matching, because I think it almost got inadvertently solved a couple years ago.

Right now, I can write this for a record type in Haskell.

foo :: MyRecord -> Int
foo (MyRecord { field1 = Just k, field2 = 4, field3 = (x:_) }) = 4*k - x

That’s a pattern match that disassembles the record, by named fields, and matches each field using the full variety of patterns available in any other context.  Pretty powerful stuff.  Unfortunately, it’s built in to Haskell’s rather limited record system, and is among the casualties incurred when switching to a different system.  One needs to fall back to the underlying “native” record.  In the case of the fclabels and data-accessor packages, for example, this means using a whole separate set of names involving underscores, further polluting the namespace with symbols related only by similarity of name.  Not a purely practical disadvantage, perhaps, but one that I’m sure grates against the nerves of anyone looking for neat, elegant answers.

Fortunately, as I mentioned briefly in my last post, the answer already exists, and has already been added to GHC.  The answer here is view patterns.  In data-accessor package language, one can actually write the following to express part of the above.

foo ((^. field1) -> Just k) = k

(Admittedly, one does obtain a warning about pattern matching overlaps when doing this.  I’m unsure why.)

Unfortunately, this very nice approach doesn’t appear to currently extend as nicely to pattern matching on several fields at the same time.  A view pattern has one view, which matches an argument; a second view pattern matches a second argument, which isn’t what we want.  The best we can do is to define a view that selects several fields…

foo ((^. field1) &&& (^. field3) -> (Just k, (x:_))) = 4*k

Barely passable for two fields… but add a third field, and suddenly you have to know about the associativity of &&& (which, by the way, we took from the Control.Arrow package).  Besides, the distance and way that conditions on different fields are mixed together isn’t terribly appealing.  We’d really like to just be able to pattern match the same argument multiple times, requiring that all of them succeed.

Ironically, this is hardly a new problem.  It’s actually the same thing encountered in @-patterns.  One wants to pattern match twice there, too — once to bind a name to the entire value, and again to deconstruct it and bind names or match pieces.  Without view patterns, that was the only situation in which one might want to pattern match the same value in several ways; the only choice was to either open up a data constructor and match on it, or else don’t.  With view patterns, though, the possibility arises any number of ways.  (Data.FingerTree contains both the functions viewl and viewr, for instance; I’m not personally aware of an application that would like to pattern match on both at once, but it doesn’t seem terribly hard to imagine that it might occur.)

It makes sense to propose, in lieu of trying to invent a way to extend record pattern-matching syntax to a new kind of records, to simply provide a mechanism for simultaneously pattern-matching the same argument in several ways.  What we would obtain from this is to generalize the problems solved by @-patterns and record syntax at once, as well as potential future as-yet-unidentified problems.

In other words, the real feature we want is simultaneous patterns — multiple patterns that are matched side-by-side with a single value.  The semantics are that the pattern match succeeds only if all of them do, in which case all of the variables occurring in the pattern are appropriately bound.

In my last post, I proposed using a semicolon to separate the patterns.  Here’s the previous example in this form, using data-accessor syntax.

foo :: MyRecord -> Int
foo ((^.field1) -> Just k ; (^.field2) -> 4 ; (^.field3) -> (x:_)) = 4*k - x

With that, we’d have solved one of the outstanding issues in building a library replacement for Haskell’s distinguished record syntax.  Essentially, there’d just be no more need for a “special” record syntax for pattern matching.  We’d have done it not by adding a new distinguished record syntax, but rather by opening up the existing pattern matching features (including view patterns, of course) to accomodate a rather straight-forward extension.

If I don’t see an obvious reason not to pursue this, I may try to determine how difficult it would be to implement this as a GHC extension.

About these ads

7 Comments

Leave a Comment
  1. Derek Elkins / Oct 4 2009 10:45 am

    foo :: MyRecord -> Int
    foo r | Just k <- r ^. field1, 4 <- r ^. field2, x:_ <- r ^. field3 = 4*k – x

  2. Ben Moseley / Oct 4 2009 11:23 am

    That’s an interesting idea. Derek’s is a nice interim solution, but I agree with Chris that simultaneous pattern-matching seems like a nice thing. Maybe @ could be reused rather than ; …

  3. Edward Kmett / Oct 9 2009 12:07 pm

    @Ben:

    Note that @ bindings currently only allow for a simple variable name to be bound on the left hand side of the @, so allowing @ bindings in this setting would require a fairly invasive retooling of how @ works inside patterns.

  4. Ravi / Oct 17 2009 10:30 pm

    I think that would be very interesting. I’d love to see you try to implement this extension (and, of course, as someone on the Haskell’ committee, to see you turn this into a proposal for a future revision of Haskell if it works out well).

  5. Dan Licata / Nov 7 2009 9:31 am

    You can already kind of match on a value multiple times with view patterns: just define a function that pairs the value with itself the appropriate number of times.

    Instead of

    foo :: MyRecord -> Int
    foo ((^.field1) -> Just k ; (^.field2) -> 4 ; (^.field3) -> (x:_)) = 4*k – x

    write

    three x = (x , x , x)
    foo (three -> ((^.field1) -> Just k , (^.field2) -> 4 , (^.field3) -> (x:_))) = 4*k – x

    • Dan Licata / Nov 7 2009 9:37 am

      Also I meant to mention that this use of view patterns is very cool! Nice idea! :)

    • Anonymous / Nov 7 2009 12:46 pm

      Oh, I like that one… without the special function, one can still do (slightly more messy)

      foo (replicate 3 -> [ (^.field1) -> Just k, (^.field2) -> 4, (^.field3) -> (x:_) ]) = 4*k – x

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 74 other followers

%d bloggers like this: