... | ... | @@ -15,7 +15,7 @@ View patterns were introduced in GHC 6.10. This page has been revised to reflec |
|
|
|
|
|
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:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
type Typ
|
|
|
|
|
|
data TypView = Unit
|
... | ... | @@ -32,7 +32,7 @@ The representation of `Typ` is held abstract, permitting implementations to use |
|
|
|
|
|
In current Haskell, using this signature is a little inconvenient:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size :: Typ -> Integer
|
|
|
size t = case view t of
|
|
|
Unit -> 1
|
... | ... | @@ -46,7 +46,7 @@ In response, programmers sometimes eschew type abstraction in favor of revealing |
|
|
|
|
|
View patterns permit calling the view function inside the pattern and matching against the result:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size (view -> Unit) = 1
|
|
|
size (view -> Arrow t1 t2) = size t1 + size t2
|
|
|
```
|
... | ... | @@ -54,7 +54,7 @@ View patterns permit calling the view function inside the pattern and matching a |
|
|
|
|
|
That is, we add a new form of pattern, written
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
expression -> pattern
|
|
|
```
|
|
|
|
... | ... | @@ -76,8 +76,6 @@ However, sometimes modest syntactic sugar can have profound consequences. In thi |
|
|
|
|
|
### Semantics
|
|
|
|
|
|
|
|
|
|
|
|
**Scoping** for *expr `->` *pat:
|
|
|
|
|
|
|
... | ... | @@ -86,13 +84,13 @@ However, sometimes modest syntactic sugar can have profound consequences. In thi |
|
|
|
|
|
- In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments.
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
example :: (String -> Integer) -> String -> Bool
|
|
|
example f (f -> 4) = True
|
|
|
```
|
|
|
- Variables can be bound to the left in tuples and data constructors:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
example :: ((String -> Integer,Integer), String) -> Bool
|
|
|
example ((f,_), f -> 4) = True
|
|
|
```
|
... | ... | @@ -117,7 +115,7 @@ We discuss some examples of pattern-matching abstract types and of other uses o |
|
|
|
|
|
The requisite join-list example:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
data JList a = Empty
|
|
|
| Single a
|
|
|
| Join (JList a) (JList a)
|
... | ... | @@ -132,7 +130,7 @@ Here we've chosen that the view type only exposes the cons/nil structure one lev |
|
|
|
|
|
The implementation of the view:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
view :: JList a -> JListView a
|
|
|
view Empty = Nil
|
|
|
view (Single a) = Cons a Empty
|
... | ... | @@ -146,7 +144,7 @@ Note the recursive uses of the view function in view patterns within its own def |
|
|
|
|
|
An example of using it:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
length :: JList a -> Integer
|
|
|
length (view -> Nil) = 0
|
|
|
length (view -> Cons x xs) = 1 + length xs
|
... | ... | @@ -155,7 +153,7 @@ An example of using it: |
|
|
|
|
|
For more general sequences, `Data.Sequence` already defines the views from the left and from the right
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
data ViewL a
|
|
|
= EmptyL
|
|
|
| (:<) a (Seq a)
|
... | ... | @@ -177,7 +175,7 @@ that now may be used in view patterns. |
|
|
|
|
|
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:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
type Typ
|
|
|
|
|
|
outUnit : Typ -> Maybe ()
|
... | ... | @@ -189,7 +187,7 @@ Here's an alternate style of view definition: rather than mapping the abstract t |
|
|
|
|
|
This view is used as follows:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size (outUnit -> Just _) = 1
|
|
|
size (outArrow -> Just (t1, t2)) = size t1 + size t2
|
|
|
```
|
... | ... | @@ -202,7 +200,7 @@ This style should be discouraged when the view is in fact a total operation, as |
|
|
|
|
|
Here is a small module that allows to decompose sets with respect to a given element, deleting it hereby.
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
module Set(Set, empty, insert, delete, has) where
|
|
|
|
|
|
newtype Set a = S [a]
|
... | ... | @@ -228,7 +226,7 @@ Note the use of the previous argument `x` in later view patterns. |
|
|
|
|
|
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](http://user.it.uu.se/~kostis/Papers/index.html#Conference)). Suppose we had a parsing function thus:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
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
|
... | ... | @@ -237,7 +235,7 @@ Sagonas et al describe an extension to Erlang that supports pattern-matching on |
|
|
|
|
|
Then we could write patterns like this:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
parsePacket :: ByteString -> ...
|
|
|
parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ...
|
|
|
```
|
... | ... | @@ -249,7 +247,7 @@ This parses 3 bits to get the value of `n`, and then parses `n` bits to get the |
|
|
|
|
|
`(n+k)` patterns use the following view function:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
np k n | k <= n = Just (n-k)
|
|
|
| otherwise = Nothing
|
... | ... | @@ -258,7 +256,7 @@ This parses 3 bits to get the value of `n`, and then parses `n` bits to get the |
|
|
|
|
|
They are used as follows:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
fib :: Num a => a -> a
|
|
|
fib 0 = 1
|
|
|
fib 1 = 1
|
... | ... | @@ -270,7 +268,7 @@ Note the integration with type classes: the view function can be overloaded, and |
|
|
|
|
|
`n+k` patterns are another a good opportunity for passing view data at run-time, as in:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
example k (np k -> Just n) = ...
|
|
|
```
|
|
|
|
... | ... | @@ -279,7 +277,7 @@ Note the integration with type classes: the view function can be overloaded, and |
|
|
|
|
|
View patterns can be used to pattern match against named constants:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
errorVal :: Int -> Bool
|
|
|
errorVal = (== 4)
|
|
|
f (errorVal -> True) = ...
|
... | ... | @@ -290,7 +288,7 @@ View patterns can be used to pattern match against named constants: |
|
|
|
|
|
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:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
both : a -> (a,a)
|
|
|
both x = (x,x)
|
|
|
```
|
... | ... | @@ -298,7 +296,7 @@ A "both pattern" `pat1 & pat2` matches a value against both `pat1` and `pat2` an |
|
|
|
|
|
And used as follows:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
f (both -> (xs, h : t)) = h : (xs ++ t)
|
|
|
```
|
|
|
|
... | ... | @@ -310,7 +308,7 @@ And used as follows: |
|
|
|
|
|
View patterns permit programming in an iterator style, where you name the result of a recursive call but not the term the call was made on. E.g.:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
length [] = 0
|
|
|
length (_ : length -> n) = 1 + n
|
|
|
|
... | ... | @@ -335,7 +333,7 @@ Next, we describe two further syntactic extensions that we will implement. |
|
|
|
|
|
Above, we saw several examples of view functions that return a `Maybe`, including:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
np k n | k <= n = Just (n-k)
|
|
|
| otherwise = Nothing
|
... | ... | @@ -344,7 +342,7 @@ Above, we saw several examples of view functions that return a `Maybe`, includin |
|
|
|
|
|
which were used as follows:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
fib (np 2 -> Just n) = fib (n + 1) + fib n
|
|
|
```
|
|
|
|
... | ... | @@ -352,14 +350,14 @@ which were used as follows: |
|
|
We may implement a special syntax that makes the `Just` implicit, using *expr* `=>` *pat* for *expr* `-> Just` *pat*. An example use:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
fib (np 2 => n) = fib (n + 1) + fib n
|
|
|
```
|
|
|
|
|
|
|
|
|
This syntax works very nicely with partial views:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size (outUnit => _) = 1
|
|
|
size (outArrow => (t1, t2)) = size t1 + size t2
|
|
|
```
|
... | ... | @@ -369,7 +367,7 @@ This syntax works very nicely with partial views: |
|
|
|
|
|
A further syntactic extension would be to have implicit Maybes with implicit tupling: multiple patterns after the `=>` are implicitly tupled. Then you could write:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size (outArrow => t1 t2) = size t1 + size t2
|
|
|
```
|
|
|
|
... | ... | @@ -381,7 +379,7 @@ Total views have one syntactic disadvantage relative to the iterated-case style |
|
|
|
|
|
The idea is that we distinguish a particular type class as a hook into the pattern compiler. The class has the following interface:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
class View a b where
|
|
|
view :: a -> b
|
|
|
```
|
... | ... | @@ -390,7 +388,7 @@ The idea is that we distinguish a particular type class as a hook into the patte |
|
|
Then, you can leave off the expresion in a view pattern, writing (`->` *pat*), to mean `view -> ` *pat*. For example:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size (-> Unit) = 1
|
|
|
size (-> Arrow t1 t2) = size t1 + size t2
|
|
|
```
|
... | ... | @@ -398,7 +396,7 @@ Then, you can leave off the expresion in a view pattern, writing (`->` *pat*), t |
|
|
|
|
|
means
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size (view -> Unit) = 1
|
|
|
size (view -> Arrow t1 t2) = size t1 + size t2
|
|
|
```
|
... | ... | @@ -409,7 +407,7 @@ for the overloaded `view`. |
|
|
|
|
|
To use this mechanism, you add instances to `view`, as in:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
instance View Typ TypView where
|
|
|
view = (the view function from above)
|
|
|
```
|
... | ... | @@ -425,7 +423,7 @@ Of course, you can only use one view function for each hidden-type/view-type pai |
|
|
|
|
|
The above implementation of `size` is given the following type:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
size :: View a TypView => a -> Int
|
|
|
```
|
|
|
|
... | ... | @@ -435,7 +433,7 @@ which may or may not be what you want. (For example, with nested view patterns, |
|
|
|
|
|
Thus, it may be better to make one parameter of the type class determine the other (using associated type synonyms):
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
class View a where
|
|
|
type View a
|
|
|
view :: a -> View a
|
... | ... | @@ -444,7 +442,7 @@ Thus, it may be better to make one parameter of the type class determine the oth |
|
|
|
|
|
or
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
class View b where
|
|
|
type Hidden b
|
|
|
view :: Hidden b -> a
|
... | ... | @@ -461,7 +459,7 @@ The downside of these versions is that you can only have one view for a type (wh |
|
|
|
|
|
Due to type classes, checking for the "same" view pattern must be type-aware; the same source syntax cannot necessarily be commoned up:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
class View a b where
|
|
|
view :: a -> b
|
|
|
|
... | ... | @@ -534,7 +532,7 @@ view constructors to appear in patterns only. |
|
|
This proposal is substantially more complicated than the one above; in particular it
|
|
|
requires new form of top-level declaration for a view type. For example:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
view Backwards a of [a] = [a] `Snoc` a | Nil
|
|
|
where
|
|
|
backwards [] = Nil
|
... | ... | @@ -562,7 +560,7 @@ to the different host language. Again, the value input feature is not supported |
|
|
|
|
|
Erwig's proposal for active patterns renders the Set example like this:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
data Set a = Empty | Add a (Set a)
|
|
|
|
|
|
pat Add' x _ =
|
... | ... | @@ -591,7 +589,7 @@ Active Destructors (ADs) are defined by a new form of top-level declaration. |
|
|
|
|
|
Where we'd write
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
sing :: [a] -> a option
|
|
|
sing [x] = x
|
|
|
```
|
... | ... | @@ -599,7 +597,7 @@ Where we'd write |
|
|
|
|
|
The equivalent active destructor would be
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
Sing x match [x]
|
|
|
```
|
|
|
|
... | ... | @@ -616,7 +614,7 @@ The value-input feature is supported, but only via a sort of mode declaration (i |
|
|
They also introduce a combining form for ADs, to make a kind of and-pattern. For
|
|
|
example, suppose we had
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
Head x match (x:_)
|
|
|
Tail x match (_:xs)
|
|
|
|
... | ... | @@ -628,7 +626,7 @@ example, suppose we had |
|
|
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:
|
|
|
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
headV (x:xs) = Just x
|
|
|
headV [] = Nothing
|
|
|
|
... | ... | @@ -641,7 +639,7 @@ Here `(Head x)@(Tail ys)` is a pattern that matches *both* `(Head x)` and `(Tail |
|
|
|
|
|
An alternative to duplicating the value is to compose the functions:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
(@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c)
|
|
|
(f @ g) x = do { b <- f x; c <- g x; return (b,c) }
|
|
|
|
... | ... | @@ -677,7 +675,7 @@ Here is [a full paper describing the design](http://blogs.msdn.com/dsyme/archive |
|
|
|
|
|
The feature is implemented in F\# 1.9. Some code snippets are below.
|
|
|
|
|
|
```wiki
|
|
|
```fsharp
|
|
|
let (|Rect|) (x:complex) = (x.RealPart, x.ImaginaryPart)
|
|
|
let (|Polar|) (x:complex) = (x.Magnitude , x.Phase)
|
|
|
|
... | ... | @@ -697,7 +695,7 @@ The feature is implemented in F\# 1.9. Some code snippets are below. |
|
|
|
|
|
And for views:
|
|
|
|
|
|
```wiki
|
|
|
```fsharp
|
|
|
open System
|
|
|
|
|
|
let (|Named|Array|Ptr|Param|) (typ : System.Type) =
|
... | ... | @@ -743,7 +741,7 @@ Reppy & Aiken, TR 92-1290, Cornell, June 1992. |
|
|
|
|
|
The one way in which pattern synonyms are better than view patterns is thatn they define by-construction bi-directional maps. Example
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
data Term = Var String | Term String [Term]
|
|
|
|
|
|
-- 'const' introduces a pattern synonym
|
... | ... | @@ -757,7 +755,7 @@ The one way in which pattern synonyms are better than view patterns is thatn the |
|
|
|
|
|
With pattern views, we'd have to write two functions for the "plus" view:
|
|
|
|
|
|
```wiki
|
|
|
```haskell
|
|
|
plus :: Term -> Term -> Term
|
|
|
plus a b = Term "+" [a,b]
|
|
|
|
... | ... | |