wiki:ViewPatterns

Version 4 (modified by simonpj, 7 years ago) (diff)

--

View patterns: lightweight views for Haskell

This page describes a rather lightweight proposal for adding views to Haskell Prime. I'm thinking of prototyping the idea in GHC, so I'm looking for feedback.

This page is open to editing by anyone. (Chase the "Wiki notes" link in the sidebar to find out how.)

The problem

We are keen on abstraction, but pattern matching is so convenient that we break abstractions all the time. It's our dirty little secret. Looked at this way, object-oriented folk are much more obsessive about abstraction than we are: everything (including field access these days) is a method.

Views have, in one form or another, repeatedly been proposed as a solution for this problem. (See the end for a comparison with related work.)

The proposal informally

The proposal introduces a new form of pattern, called a view pattern Here are some function definitions using view patterns. To read these definitions, imagine that sing is a sort of constructor that matches singleton lists.

  f :: [Int] -> Int
  f (sing -> n) = n+1	-- Equiv to: f [n] = ...
  f other     = 0

  g :: [Bool] -> Int
  g (sing -> True)  = 0		-- Equiv to: g [True] = ...
  g (sing -> False) = 1		-- Equiv to: g [False] = ...
  g other           = 2

  h :: [[Int]] -> Int	
  h (sing -> x : sing -> y : _) = x+y
			-- Equiv to: h ([x]:[y]:_) = ...
  h other = 0

So what is sing? It is just an ordinary Haskell function that returns a Maybe type:

  sing :: [a] -> Maybe a
  sing [x]   = Just x
  sing other = Nothing

So sing simply identifies singleton lists, and returns the payload (that is, the singleton element; otherwise it returns Nothing. It is very important that there is nothing special about sing. It is not declared to be a view; it can be called as a normal Haskell function; the author of sing might not have intended it to be used in pattern matching.


The proposal more formally

The only special stuff is in the pattern. The sole change is this: add a single new sort of pattern, of the form

(expr -> pat)

where expr is an arbitrary Haskell expression. I'll call a pattern of this form a view pattern.

From a scoping point of view, the variables bound by the pattern (expr -> pat) are simply the variables bound by pat. Any variables in expr are bound occurrences.

The rule for pattern-matching is this: To match a value v against a pattern (expr -> p),

  • Evaluate (expr v)
  • If the result is (Just w), match w against p
  • If the result is Nothing, the match fails.

The typing rule is similarly simple. The expression expr must have type t1 -> Maybe t2. Then the pattern pat must have type t2, and the whole pattern (expr -> pat) has type t1.

The value input feature

Note that the expr is an arbitrary Haskell expression. For example, suppose you wrote a regular expression matching function:

  regexp :: String -> String -> Maybe (String, String)
  -- (regexp r s) parses a string matching regular expression r 
  --	the front of s, returning the matched string and remainder of s

then you could use it in patterns thus:

  f :: String -> String
  f (regexp "[a-z]*" -> (name, rest)) = ...

Of course, the argument does not need to be a constant as it is here.

This ability to pass arguments to the view function, to guide its matching behaviour, is a key feature of this proposal, shared by some, but by no means all view proposals. I'll call it the value input feature.

Indeed, in a sense, patterns become first class. For example, one could pass a pattern as an argument to a function thus:

  g :: (Int -> Maybe Int) -> Int -> ...
  g p (p -> x) = ...

Here the first argument p can be thought of as a pattern passed to g, which is used to match the second argument of g.

Possible extension 1: multi-argument view patterns

It would be quite useful to allow more than one sub-pattern in a view pattern. To do this we'd need a Maybe data type that returns more than one result, thus:

  data Maybe2 a b   = Nothing2 | Just2 a b
  data Maybe3 a b c = Nothing3 | Just3 a b c
  	-- ..etc..., up to 8 perhaps (sigh)

With this in hand we can extend the views story to have multiple sub-patterns. Example:

  snoc :: [a] -> Maybe2 [a] a
  snoc [] = Nothing2
  snoc (x:xs) = case snoc xs of
		  Nothing2   -> Just2 [] x
		  Just2 ys y -> Just2 (x:ys) y

  last :: [Int] -> Int
  last (snoc -> xs x) = x
  last other = error "empty list"

It is tiresome that we need types Maybe2, Maybe3 etc, but we already have that in Haskell; consider zip3, zip4 and so on. We could always get away without it, by sticking to unary view patterns and using tuples, thus:

  snoc :: [a] -> Maybe ([a], a)
  snoc [] = Nothing
  snoc (x:xs) = case snoc xs of
		  Nothing     -> Just ([], x)
		  Just (ys,y) -> Just (x:ys, y)

  last :: [Int] -> Int
  last (snoc -> (xs, x)) = x
  last other = error "empty list"

But the tuple looks a bit clumsy.

Under this proposal, the number of sub-patterns in the view pattern determines which return type the view function should have. E.g. in the pattern '(e -> p1 p2 p3)', 'e' should return a Maybe3.

If n=0, then we want Maybe0, which is called Bool. Thus

  even :: Int -> Bool
  even n = n `div` 2 == 0

  f (even ->) = ...	-- Matches even numbers
  f other     = ...

Here even is used as a nullary view pattern, with no sub-patterns following the ->.

Possible extension 2: the implicit Maybe

Thus far, the view function is required to return a Maybe type, with Nothing to indicate match failure. An alternative, presented in the Erwig paper on transformational patterns (see Related work below), this implicit matching is not performed; instead, the sub-pattern is matched against whatever the view function returns. So you'd have to write:

f (snoc -> Just2 xs x) = ...

(Note the tiresome Just2.) The benefit of not having the implicit matching is that you can write functions that are, perhaps, more view-like. Example:

data Product = ....some big data type...

data Size = Small | Medium | Big	-- View type
prodSize :: Product -> Size
prodSize = ....

f :: Product -> ...
f (prodSize -> Small)  = ...
f (prodSize -> Medium) = ...
f (prodSize -> Big)    = ...

With the built-in Maybe proposal, you'd instead write something like this:

smallProd, medProd, bigProd :: Product -> Bool
smallProd p = ...
medProd   p = ...
bigProd   p = ...

f :: Product -> ...
f (smallProd ->) = ...
f (medProd   ->) = ...
f (bigProd   ->) = ...

This is not obviously worse, except that the first version is more obviously exhaustive. Incidentally, both should generate the same code.

I can think of three alternatives:

  • The Maybe stuff is built-in. This is the main proposal, because I think it is often exactly what you want.
  • No built-in Maybe stuff. Arguably this is more consistent with pattern-guards.
  • Both are available, with different syntax. For example
    • (expr -> pat) for the built-in Maybe story
    • (expr => pat) with no bulit-in Maybe

Efficiency

View patterns can do arbitrary computation, perhaps expensive. So it's good to have a syntactically-distinct notation that reminds the programmer that some computation beyond ordinary pattern matching may be going on.

It's reasonable to expect the compiler to avoid repeated computation when pattern line up in a column:

  f (snoc -> x xs) True  = ...
  f (snoc -> x xs) False = ...

In pattern-guard form, common sub-expression should achieve the same effect, but it's quite a bit less obvious. We should be able to give clear rules for when the avoidance of repeat computation is guaranteed.


More examples

Erlang-style parsing

The expression to the left of the -> can mention variables bound in earlier patterns. For example, Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ("Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07). Suppose we had a parsing function thus:

  bits :: Int -> ByteString -> Maybe2 Word ByteString
  -- (bits n bs) parses n bits from the front of bs, returning
  -- the n-bit Word, and the remainder of bs

Then we could write patterns like this:

  parsePacket :: ByteString -> ...
  parsePacket (bits 3 -> n (bits n -> val bs)) = ...

This parses 3 bits to get the value of n, and then parses n bits to get the value of val.

Sets as lists

Here is a module implementing sets as lists:

module Set( Set, empty, insert, delete, has) where

  newtype Set a = S [a]
  
  has :: Eq a => a -> Set a -> Maybe (Set a)
  has x (S xs) | x `elem` xs = Just (xs \\ x)
               | otherwise   = Nothing
  
  delete :: a -> Set a -> Set a
  delete x (has x -> s) = s
  delete x s            = s
  
  insert :: a -> Set a -> Set a
  insert x s@(has x -> _) = s
  insert x (S xs)         = S (x:xs)

Notice that in the left-hand side delete x (has x -> s), the first x is a binding occurrence, but the second is merely an argument to has and is a bound occurrence.

N+k patterns

You can test for values. For example here's a view function that tests for values greater than or equal to n:

   np :: Num a => a -> a -> Maybe a
   np k n | k <= n    = Just (n-k)
	  | otherwise = Nothing

   f :: Num a => a -> Int
   f (np 10 -> n) = 0		-- Matches values >= 10
   f (np 4  -> n) = 1		-- Matches values >= 4
   f other        = 2

You will recognise these as (n+k) patterns, albeit with slightly different syntax. (Incidentally, this example shows that the view function can be overloaded, and that its use in a view pattern gives rise to a type-class constraint (in this case, that in turn makes f overloaded).

Naming constants in one place

We are always taught to write magic numbers, or constants, in one place only. In C you can write

  #define ERRVAL 4

and then use ERRVAL in switch labels. You can't do that in Haskell, which is tiresome. But with view pattern you can:

  errVal :: Int -> Bool
  errVal = (== 4)

  f (errVal ->) = ...

Concrete syntax

Here are some other possible syntax choices I've considered:

  f ($snoc x xs) = ...		-- Use prefix "$"
  g ($(bits 3) x bs) = ...	-- Extra parens for the value input feature

  f (%snoc x xs) = ...		-- Or use prefix "%" instead

  f (.snoc x xs) = ...		-- Or use prefix "." instead

  f (snoc | x xs) = ..		-- Use "|" instead of "->"
  g (bits 3 | b bs) = ...

Another possibility is to use a backward arrow, more like pattern guards:

  f ((x,xs) <- snoc) = ...  -- More like pattern guards

But that messes up the left-to-right flow that is useful in some cases. For example, compare these:

  parsePacket1 (bits 3 -> n (bits n -> val bs)) = ...

  parsePacket2 (n (val bs <- bits n) <- bits 3) = ...

I also thought about infix view patterns, where the view function appears between its (pattern) arguments, but I could not think of a nice syntax for it, so it is not provided by this proposal.

Remarks

The key feature of this proposal is its modesty, rather than its ambition:

  • There is no new form of declaration (e.g. 'view' or 'pattern synonym').
  • The functions used in view patterns are ordinary Haskell functions, and can be called from ordinary Haskell code. They are not special view functions.
  • Since the view functions are ordinary Haskell functions, no changes are needed to import or export mechanisms.
  • Both static and dynamic semantics are extremely simple.

It is essentially some simple syntactic sugar for patterns. However, sometimes modest syntactic sugar can have profound consequences. In this case, it's possible that people would start routinely hiding the data representation and exporting view functions instead, which might be an excellent thing.

All this could be done with pattern guards. For example parsePacket could be written

  parsePacket bs | Just (n, bs')    <- bits 3 bs
                 | Just (val, bs'') <- bits n bs'
		 = ...

Indeed, one might ask whether the extra syntax for view patterns is worth it when they are so close to pattern guards. That's a good question. I'm hoping that support for view patterns might encourage people to export view functions (ones with Maybe return types, and encouage their use in patten matching). That is, just lower the barrier for abstraction a bit.

Completeness. It is hard to check for completeness of pattern matching; and likewise for overlap. But guards already make both of these hard; and GADTs make completness hard too. So matters are not much worse than before.


Related work

Wadler's original paper (POPL 1987)]

Wadler's paper was the first concrete proposal. It proposed a top-level view declaration, together with functions in both directions between the view type and the original type, which are required to be mutually inverse. This allows view constructors to be used in expressions as well as patterns, which seems cool. Unfortunately this dual role proved problematic for equational reasoning, and every subsequent proposal restricted view constructors to appear in patterns only.

Burton et al views (1996)

This proposal is substantially more complicated than the one above; in particular it rquires new form of top-level declaration for a view type. For example:

  view Backwards a of [a] = [a] `Snoc` a | Nil
     where
     backwards [] = Nil
     backwards (x:[]) = [] `Snoc` x
     backwards (x1:(xs `Snoc` xn)) = (x1:xs) `Snoc` xn

Furthermore, it is in some ways less expressive than the proposal here; the (n+k) pattern, Erlang bits pattern, and regexp examples are not definable, because all rely on the value input feature.

I think this proposal is substantially the same as "Pattern matching and abstract data types", Burton and Cameron, JFP 3(2), Apr 1993.

Okasaki: views in Standard ML

Okasaki's design is very similar to Burton et al's, apart from differences due to the different host language. Again, the value input feature is not supported.

Erwig: active patterns

Erwig's proposal for active patterns renders the Set example like this:

data Set a = Empty | Add a (Set a)

pat Add' x _ =
  Add y s => if x==y then Add y s
             else let Add' x t = s
                  in Add x (Add y t)

delete x (Add' x s) = s
delete x s          = s

This requires a new top-leven declaration form pat; and I don't think it's nearly as easy to understand as the current proposal. Notably, in the first equation for delete it's ahrd to see that the second x is a bound occurrence; this somehow follows from the pat declaration.

Still the proposal does support the value input feature.

Palao et al: active destructors (ICFP'96)

Active Desctructors (ADs) are defined by a new form of top-level declaration. Our singleton example would look like this:

  Sing x match [x]

Here match is the keyword, and Sing is the AD. ADs are quite like view patterns: the can do computation, and can fail to match. But they are definitely not normal Haskell functions, and need their own form of top-level declaration. They even have a special form of type to describe them.

The value-input feature is supported, but only via a sort of mode declaration (indicated by a down-arrow) on the new form of type.

They also introduce a combining form for ADs, to make a kind of and-pattern. For example, suppose we had

  Head x match (x:_)
  Tail x match (_:xs)

  f :: [a] -> [a]
  f ((Head x)@(Tail ys)) = x:x:ys

Here (Head x)@(Tail ys) is a pattern that matches both (Head x) and (Tail ys) against the argument, binding x and ys respectively. We can model that with view patterns, only a bit more clumsily:

  headV (x:xs) = Just x
  headV []     = Nothing

  tailV (x:xs) = Just xs
  tailV []     = Nothing

  (@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c)
  (f @ g) x = do { b <- f x; c <- g x; return (b,c) }

  f :: [a] -> [a]
  f (headV @ tailV -> (x,ys)) = x:x:ys

The clumsiness is that the "@" combines functions, with a kind of positional binding; the pattern (x,ys) is separated from the combiner so that it's less clear that headV binds x and tailV binds y.

In exchange, although view patterns are a bit less convenient here, they are a much, much smaller language change than ADs.

Erwig/Peyton Jones: transformational patterns

This paper describes pattern guards, but it also introduces transformational patterns. (Although it is joint-authored, the transformational-pattern idea is Martin's.) Transformational patterns are very close to what we propose here. In particular, view functions are ordinary Haskell functions, so that the only changes are to patterns themselves.

There are two main differences (apart from syntax). First, transformational patterns didn't have the value input feature, althought it'd be easy to add (indeed that's what we've done). Second, transformational patterns as described by Erwig do no stripping of the Maybe (see "Possible extension 2" above).

Emir, Odersky, Williams: Matching objects with patterns

Scala is an OO language with lots of functional features. It has algebraic data types and pattern matching. It also has a form of view called extractors, which are pretty similar to view patterns, albeit in OO clothing. Notably, by packaging a constructor and an extractor in a class, they can use the same class name in both expressions and terms, implicitly meaning "use the constructor in expressions, and use the extractor in patterns".

The paper does a comparative evaluation of various OO paradigms for matching, and concludes that case expressions and extractors work pretty well.

Pattern synonyms

Pattern synonyms are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see Abstract value constructors, Reppy & Aiken, TR 92-1290, Cornell, June 1992.

The one way in which pattern synonyms are better than view patterns is that they define by-construction bi-directional maps. Example

  data Term = Var String | Term String [Term]
  
  -- 'const' introduces a pattern synonym
  const Plus a b = Term "+" [a,b]

  f :: Term -> Term
  f (Plus a b) = Plus (f a) (f b)
  f ... = ...

With pattern views, we'd have to write two functions for the "plus" view:

  plus :: Term -> Term -> Term
  plus a b = Term "+" [a,b]

  isPlus :: Term -> Maybe2 Term Term
  isPlus (Term "+" [a,b]) = Just2 a b
  isPlus other		  = Nothing

  f :: Term -> Term
  f (isPlus -> a b) = plus (f a) (f b)

But perhaps that is not so bad. Pattern synonyms also require a new form of top level declaration; and are much more limited than view patterns (by design they cannot do computation).

First class abstractions

Several proposals suggest first class abstractions rather that first-class patterns. Here are the ones I know of

All these proposals are more or less orthogonal to this one. For example, Reinke proposes a compositional syntax for lambda abstractions (\p -> e) where pattern matching failure on p can be caught and composed with a second abstraction. Thus

   (| Just x -> x+1 ) +++ (| Nothing -> 0 )

combines two abstractions, with failure from the first falling through to the seoond.

Blume and Tullsen have a similar flavour. None of these proposals say anything about the patterns themselves, which in turn is all this proposal deals with. Hence orthgonal.