wiki:ViewPatternsAlternative

Version 2 (modified by augustss, 3 years ago) (diff)

--

Alternative view patterns: lightweight views for Haskell

This is a copy of the ViewPatterns page, but with a different syntax.

Basic view patterns

View patterns are a convenient way of pattern-matching against values of abstract types. For example, in a programming language implementation, we might represent the syntax of the types of the language as follows:

   type Typ
 
   data TypView = Unit
                | Arrow Typ Typ

   view :: Typ -> TypView

   -- additional operations for constructing Typ's ...

The representation of Typ is held abstract, permitting implementations to use a fancy representation (e.g., hash-consing to manage sharing).

In current Haskell, using this signature is a little inconvenient:

   size :: Typ -> Integer
   size t = case view t of
     Unit -> 1
     Arrow t1 t2 -> size t1 + size t2

It is necessary to iterate the case, rather than using an equational function definition. And the situation is even worse when the matching against t is buried deep inside another pattern. In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against.

View patterns permit calling the view function inside the pattern and matching against the result:

   size (x | Unit <- x) = 1
   size (x | Arrow t1 t2 <- ) = size t1 + size t2

That is, we add a new form of pattern, written

   pattern | qual,,1,, , ..., qual,,n,,

This has the same meaning as pattern guard at the top level, but here they are allowed to be part of a pattern, and thus nested inside other patterns. So first the pattern is matched, then the qualifiers are matched in order. An expression qualifier has to evaluate to True, and for a pat <- exp the pattern must match the expression.

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').
  • No new syntax, the existing pattern guard syntax is simply generalized to be allowed inside patterns.
  • 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 would be an excellent thing.

Semantics

Scoping for pat | quals:

  • The variables bound by the view pattern are the variables bound by pat and quals.
  • Variables bound by patterns to the left of a view pattern expression are in scope. For example:
    • In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments.
         example :: (String -> Integer) -> String -> Bool
         example f (x | f x == 4) = True
      
    • Variables can be bound to the left in tuples and data constructors:
         example :: ((String -> Integer,Integer), String) -> Bool
         example ((f,_), x | f x == 4) = True
      

Typing If pat | quals has same type as pat, and the "quals" must be well typed in the same way as for pattern guards.

Evaluation To match a value v against a pattern (pat | quals), match "v" against pat and then match the quals.

Examples

We discuss some examples of pattern-matching abstract types and of other uses of view patterns here.

Join lists

The requisite join-list example:

   data JList a = Empty 
                | Single a
                | Join (JList a) (JList a)
 
   data JListView a = Nil
                    | Cons a (JList a)

Here we've chosen that the view type only exposes the cons/nil structure one level at a time: the second argument to Cons is a join-list, not a view of it---but that's of course up to the programmer.

The implementation of the view:

  view :: JList a -> JListView a
  view Empty = Nil
  view (Single a) = Cons a Empty
  view (Join (l | Cons xh xt <- view l) y) = Cons xh $ Join xt y
  view (Join (l | Nil <- view) l) = view y

Note the recursive uses of the view function in view patterns within its own definition.

An example of using it:

  length :: JList a -> Integer
  length (l | Nil <- view l) = 0
  length (l | Cons x xs <- l) = 1 + length xs

For more general sequences, Data.Sequence already defines the views from the left and from the right

   data ViewL a
   = EmptyL
   | (:<) a (Seq a)

   viewl :: Seq a -> ViewL a

   data ViewR a
   = EmptyR
   | (:>) (Seq a) a

   viewr :: Seq a -> ViewR a

that now may be used in view patterns.

Partial views

Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections optionally inverting each constructor:

   type Typ

   outUnit  : Typ -> Maybe ()
   outArrow : Typ -> Maybe (Typ, Typ)

   -- additional operations for constructing Typ's ...

This view is used as follows:

   size (t | Just _ <- outUnit t) = 1
   size (t | Just (t1, t2) <- outArrow t) = size t1 + size t2

This style should be discouraged when the view is in fact a total operation, as it moves the documentation of this fact out of the type system, making it harder for both people and the compiler to check exhaustiveness. However, it may be a useful idiom for defining a partial matching function with several constructors (e.g., in XML processing).

Sets

Here is a small module that allows to decompose sets with respect to a given element, deleting it hereby.

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 (r | Just s <- has r) = s
  delete x s                     = s
  
  insert :: a -> Set a -> Set a
  insert x (s | Just _ <- has x s) = s
  insert x (S xs)                = S (x:xs)

Note the use of the previous argument x in later view patterns.

Erlang-style parsing

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 -> Maybe (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 (p1 |  Just (n, (p2 | Just (val, bs) <- bits n p2)) <- bits 3 p1) = ...

This parses 3 bits to get the value of n, and then parses n bits to get the value of val. Note that this example uses the left-to-right scoping in the inner tuple: the first component is jused in the view expression in the second.

N+k patterns

(n+k) patterns use the following view function:

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

They are used as follows:

   fib :: Num a -> a -> a
   fib 0 = 1
   fib 1 = 1
   fib (n2 | Just n <- np 2 n2) = fib (n + 1) + fib n

Note the integration with type classes: the view function can be overloaded, and its use in a view pattern gives rise to a type-class constraint (in this case, that in turn makes fib overloaded).

Alternatively it can be written without an auxiliary function

   fib :: Num a -> a -> a
   fib 0 = 1
   fib 1 = 1
   fib (n2 | let n = n2-2, n >= 0) = fib (n + 1) + fib n

n+k patterns are another a good opportunity for passing view data at run-time, as in:

   example k (m | m > k) = ...

Named constants

View patterns can be used to pattern match against named constants:

    errorVal :: Int -> Bool
    errorVal = (== 4)
    f (x | errorVar x) =  ...

Both patterns

A "both pattern" pat1 & pat2 matches a value against both pat1 and pat2 and succeeds only when they both succeed. A special case is as-patterns, x@p, where the first pattern is a variable. Both patterns can be programmed using view patterns:

And used as follows:

   f (x | xs <- x, h : t <- x) = h : (xs ++ t)

Comparison with existing view patterns

There are straightforward translations between old and new style view patterns:
pat <- exp
translates to
x | pat <- exp x where x is a fresh variable.