|
|
# View patterns: lightweight views for Haskell
|
|
|
|
|
|
[Basic view patterns](#Basicviewpatterns)[Semantics](#Semantics)[Examples](#Examples)[Further Syntactic Extensions](#FurtherSyntacticExtensions)[Implicit Maybe](#ImplicitMaybe)[Implicit View Functions](#ImplicitViewFunctions)[Compilation](#Compilation)[Features views can have](#Featuresviewscanhave)[Related work](#Relatedwork)
|
|
|
|
|
|
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.
|
|
|
**We are about to begin prototyping this extension in GHC, so speak now if you have comments or suggestions'''
|
|
|
This page has been revised to reflect what we're going to implement. For the previous discussion, see [ViewPatternsArchive](view-patterns-archive).
|
|
|
**
|
|
|
|
|
|
## Basic view patterns
|
|
|
|
|
|
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.
|
|
|
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
|
|
|
type Typ
|
|
|
|
|
|
data TypView = Unit
|
|
|
| Arrow Typ Typ
|
|
|
|
|
|
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.)
|
|
|
view :: Type -> TypeView
|
|
|
|
|
|
---
|
|
|
-- additional operations for constructing Typ's ...
|
|
|
```
|
|
|
|
|
|
## The lightweight view proposal
|
|
|
|
|
|
### Informally
|
|
|
The representation of `Typ` is held abstract, permitting implementations to use a fancy representation (e.g., hash-consing to managage sharing).
|
|
|
|
|
|
|
|
|
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.
|
|
|
In current Haskell, using this signature a little inconvenient:
|
|
|
|
|
|
```wiki
|
|
|
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
|
|
|
size :: Typ -> Integer
|
|
|
size t = case t of
|
|
|
Unit -> 1
|
|
|
Arrow t1 t2 -> size t1 + size t2
|
|
|
```
|
|
|
|
|
|
|
|
|
So what is `sing`? It is just an ordinary Haskell function that
|
|
|
returns a `Maybe` type:
|
|
|
|
|
|
```wiki
|
|
|
sing :: [a] -> Maybe a
|
|
|
sing [x] = Just x
|
|
|
sing other = Nothing
|
|
|
```
|
|
|
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.
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
### More formally
|
|
|
View patterns permit calling the view function inside the pattern and matching against the result:
|
|
|
|
|
|
```wiki
|
|
|
size (view -> Unit) = 1
|
|
|
size (view -> Arrow t1 t2) = size t1 + size t2
|
|
|
```
|
|
|
|
|
|
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*)
|
|
|
That is, we add a new form of pattern, written
|
|
|
|
|
|
```wiki
|
|
|
expression -> pattern
|
|
|
```
|
|
|
|
|
|
where *expr* is an arbitrary Haskell expression. I'll call a pattern
|
|
|
of this form a **view pattern**.
|
|
|
|
|
|
that means "apply the expression to whatever we're trying to match against, and then match the result of that application against the pattern". The expression can be any Haskell expression of function type, and view patterns can be used wherever patterns are currently used.
|
|
|
|
|
|
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 key feature of this proposal is its modesty, rather than its ambition:
|
|
|
|
|
|
The rule for **pattern-matching** is this:
|
|
|
To match a value *v* against a pattern *(expr -\> p)*,
|
|
|
- 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.
|
|
|
- No changes are needed to import or export mechanisms.
|
|
|
- Both static and dynamic semantics are extremely simple.
|
|
|
|
|
|
- Evaluate *(expr v)*
|
|
|
- If the result is *(`Just` w)*, match *w* against *p*
|
|
|
- If the result is `Nothing`, the match fails.
|
|
|
|
|
|
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.
|
|
|
|
|
|
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*.
|
|
|
### Semantics
|
|
|
|
|
|
### Features
|
|
|
**Scoping** for *expr `->`*pat:
|
|
|
|
|
|
- The variables bound by the view pattern are the variables bound by *pat*.
|
|
|
- Any variables in *expr* are bound occurrences. Variables bound by patterns to the left of a view pattern expression are in scope. For example:
|
|
|
|
|
|
For the different features this proposal (and others) have, see [Features views can have](#Featuresviewscanhave).
|
|
|
The proposal
|
|
|
- In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments.
|
|
|
|
|
|
- has the value input feature
|
|
|
- has the implicit `Maybe` feature
|
|
|
- doesn't have the transparent ordinary patterns feature
|
|
|
- has the nesting feature
|
|
|
```wiki
|
|
|
example :: (String -> Integer) -> String -> Bool
|
|
|
example f (f -> 4) = True
|
|
|
```
|
|
|
- Variables can be bound to the left in tuples and data constructors:
|
|
|
|
|
|
### Possible extension 1: multi-argument view patterns
|
|
|
```wiki
|
|
|
example :: ((String -> Integer,Integer), String) -> Bool
|
|
|
example ((f,_), f -> 4) = True
|
|
|
```
|
|
|
|
|
|
**Typing**
|
|
|
If *expr* has type *t1*`->`*t2* and *pat* matches a *t2*, then the whole view pattern has type *t1*.
|
|
|
|
|
|
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:
|
|
|
**Evaluation**
|
|
|
To match a value *v* against a pattern (*expr*`->`*pat*), evaluate *(expr v)* and match the result against *pat*.
|
|
|
|
|
|
```wiki
|
|
|
data Maybe2 a b = Nothing2 | Just2 a b
|
|
|
data Maybe3 a b c = Nothing3 | Just3 a b c
|
|
|
-- ..etc..., up to 8 perhaps (sigh)
|
|
|
```
|
|
|
### Examples
|
|
|
|
|
|
|
|
|
With this in hand we can extend the views story to have multiple sub-patterns.
|
|
|
Example:
|
|
|
We discuss some examples of pattern-matching abstract types and of other uses of view patterns here.
|
|
|
|
|
|
```wiki
|
|
|
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"
|
|
|
```
|
|
|
#### Join lists
|
|
|
|
|
|
|
|
|
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:
|
|
|
The requisite join-list example:
|
|
|
|
|
|
```wiki
|
|
|
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"
|
|
|
data JList a = Empty
|
|
|
| Single a
|
|
|
| Join (JList a) (JList a)
|
|
|
|
|
|
data JListView a = Nil
|
|
|
| Cons a (JList a)
|
|
|
```
|
|
|
|
|
|
|
|
|
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`.
|
|
|
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.
|
|
|
|
|
|
|
|
|
If n=0, then we want `Maybe0`, which is called `Bool`. Thus
|
|
|
The implementation of the view:
|
|
|
|
|
|
```wiki
|
|
|
even :: Int -> Bool
|
|
|
even n = n `div` 2 == 0
|
|
|
|
|
|
f (even ->) = ... -- Matches even numbers
|
|
|
f other = ...
|
|
|
view :: JList a -> JListView a
|
|
|
view Empty = Nil
|
|
|
view (Single a) = Cons a Empty
|
|
|
view (Join (view -> Cons xh xt) y) = Cons xh $ Join xt y
|
|
|
view (Join (view -> Nil) y) = view y
|
|
|
```
|
|
|
|
|
|
|
|
|
Here `even` is used as a nullary view pattern, with no sub-patterns
|
|
|
following the `->`.
|
|
|
|
|
|
|
|
|
Another variation (call it "extension 1b"), which avoids the tiresome need to define new types, is this: supplying multiple sub-patterns in a view pattern is synonymous with tupling. Thus `(f -> p1 p2)` would be synonymous with `(f -> (p1,p2))`. Here the effect is purely syntactic, allowing you to omit parens and commas without confusion. No new types. The power-to-weight ratio is probably better for this alternative.
|
|
|
Note the recursive uses of the view function in view patterns within its own definition.
|
|
|
|
|
|
### 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:
|
|
|
An example of using it:
|
|
|
|
|
|
```wiki
|
|
|
f (snoc -> Just2 xs x) = ...
|
|
|
length :: JList a -> Integer
|
|
|
length (view -> Nil) = 0
|
|
|
length (view -> Cons x xs) = 1 + length xs
|
|
|
```
|
|
|
|
|
|
|
|
|
(Note the tiresome `Just2`.)
|
|
|
For more general sequences, `Data.Sequence` already defines the views from the left and from the right
|
|
|
|
|
|
```wiki
|
|
|
data ViewL a
|
|
|
= EmptyL
|
|
|
| (:<) a (Seq a)
|
|
|
|
|
|
For more one the consequences of removing the implicit `Maybe`, see the [Implicit \`Maybe\` feature](#Implicit`Maybe`feature)
|
|
|
viewl :: Seq a -> ViewL a
|
|
|
|
|
|
data ViewR a
|
|
|
= EmptyR
|
|
|
| (:>) (Seq a) a
|
|
|
|
|
|
I can think of three alternatives:
|
|
|
viewr :: Seq a -> ViewR a
|
|
|
```
|
|
|
|
|
|
- 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`
|
|
|
that now may be used in view patterns.
|
|
|
|
|
|
### Concrete syntax
|
|
|
#### Partial views
|
|
|
|
|
|
|
|
|
A disadvantage of the arrow syntax is that it looks a bit confusing
|
|
|
when it appears in a case expression:
|
|
|
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
|
|
|
last xs = case xs of
|
|
|
(snoc -> x xs) -> x
|
|
|
```
|
|
|
type Typ
|
|
|
|
|
|
outUnit : Typ -> Maybe ()
|
|
|
outArrow : Typ -> Maybe (Typ, Typ)
|
|
|
|
|
|
(Also that "x xs" looks a bit like `x` applied to `xs`.)
|
|
|
-- additional operations for constructing Typ's ...
|
|
|
```
|
|
|
|
|
|
|
|
|
Here are some other possible syntax choices I've considered:
|
|
|
This view is used as follows:
|
|
|
|
|
|
```wiki
|
|
|
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) = ... -- Or use prefix "?" instead
|
|
|
|
|
|
f (snoc? x xs) = ... -- Postfix "?"
|
|
|
g ((bits 3)? x bs) = ... -- With parens
|
|
|
|
|
|
f (snoc | x xs) = .. -- Use "|" instead of "->"
|
|
|
g (bits 3 | b bs) = ...
|
|
|
size (outUnit -> Just _) = 1
|
|
|
size (outArrow -> Just (t1, t2)) = size t1 + size t2
|
|
|
```
|
|
|
|
|
|
|
|
|
Another possibility is to use a backward arrow, more like pattern guards:
|
|
|
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).
|
|
|
|
|
|
```wiki
|
|
|
f ((x,xs) <- snoc) = ... -- More like pattern guards
|
|
|
```
|
|
|
#### Sets
|
|
|
|
|
|
|
|
|
But that messes up the left-to-right flow that is useful in some cases.
|
|
|
For example, compare these:
|
|
|
Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby.
|
|
|
|
|
|
```wiki
|
|
|
parsePacket1 (bits 3 -> n (bits n -> val bs)) = ...
|
|
|
module Set(Set, empty, insert, delete, has) where
|
|
|
|
|
|
parsePacket2 (n (val bs <- bits n) <- bits 3) = ...
|
|
|
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 -> Just 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)
|
|
|
```
|
|
|
|
|
|
|
|
|
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
|
|
|
Note the use of the previous argument `x` in later view patterns.
|
|
|
|
|
|
#### Erlang-style parsing
|
|
|
|
|
|
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
|
|
|
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
|
|
|
parsePacket bs | Just (n, bs') <- bits 3 bs
|
|
|
| Just (val, bs'') <- bits n bs'
|
|
|
= ...
|
|
|
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
|
|
|
```
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
---
|
|
|
|
|
|
## Features views can have
|
|
|
|
|
|
|
|
|
The main goal of views is to introduce computations into pattern matches thus introducing abstraction from hard wired constructors. To distinguish between the different proposals, we pick out the key features
|
|
|
|
|
|
### Value input feature
|
|
|
|
|
|
|
|
|
This features allows to introduce additional parameters into the computation. Perhaps the most basic example are (n+k) patterns
|
|
|
Then we could write patterns like this:
|
|
|
|
|
|
```wiki
|
|
|
fib :: Int -> Int
|
|
|
fib 0 = 1
|
|
|
fib 1 = 1
|
|
|
fib (n + 2) = fib (n + 1) + fib n
|
|
|
parsePacket :: ByteString -> ...
|
|
|
parsePacket (bits 3 -> Just (n, (bits n -> Just (val, bs)))) = ...
|
|
|
```
|
|
|
|
|
|
|
|
|
Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc.
|
|
|
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
|
|
|
|
|
|
Of course, the real power unfolds when the extra parameter can be given at runtime
|
|
|
`(n+k)` patterns use the following view function:
|
|
|
|
|
|
```wiki
|
|
|
f :: Int -> Int -> ...
|
|
|
f n (n + m) = m -- f a b = (b - a)
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
np k n | k <= n = Just (n-k)
|
|
|
| otherwise = Nothing
|
|
|
```
|
|
|
|
|
|
|
|
|
In the proposed view pattern (*expr*`->`*pat*), *expr* is an arbitrary Haskell expression. Thus, the lightweight proposal has the **value input feature**. For another example, suppose you wrote a regular expression matching function:
|
|
|
They are used as follows:
|
|
|
|
|
|
```wiki
|
|
|
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
|
|
|
fib :: Num a -> a -> a
|
|
|
fib 0 = 1
|
|
|
fib 1 = 1
|
|
|
fib (np 2 -> Just n) = fib (n + 1) + fib n
|
|
|
```
|
|
|
|
|
|
|
|
|
then you could use it in patterns thus:
|
|
|
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).
|
|
|
|
|
|
`n+k` patterns are another a good opportunity for passing view data at run-time, as in:
|
|
|
|
|
|
```wiki
|
|
|
f :: String -> String
|
|
|
f (regexp "[a-z]*" -> (name, rest)) = ...
|
|
|
example k (np k -> Just n) = ...
|
|
|
```
|
|
|
|
|
|
|
|
|
Of course, the argument does not need to be a constant as it is here.
|
|
|
#### Named constants
|
|
|
|
|
|
|
|
|
With the value input feature, in a sense, patterns become first class. For example, one could pass a pattern as an argument to a function thus:
|
|
|
View patterns can be used to pattern match against named constants:
|
|
|
|
|
|
```wiki
|
|
|
g :: (Int -> Maybe Int) -> Int -> ...
|
|
|
g p (p -> x) = ...
|
|
|
errorVal :: Int -> Bool
|
|
|
errorVal = (== 4)
|
|
|
f (errorVal -> True) = ...
|
|
|
```
|
|
|
|
|
|
|
|
|
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`.
|
|
|
#### Both patterns
|
|
|
|
|
|
|
|
|
Here is another rather cute example:
|
|
|
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
|
|
|
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
|
|
|
unfoldr f (f -> (a, b)) = a : unfoldr f b
|
|
|
unfoldr f other = []
|
|
|
both : a -> (a,a)
|
|
|
both x = (x,x)
|
|
|
```
|
|
|
|
|
|
### Implicit `Maybe` feature
|
|
|
|
|
|
|
|
|
In functional languages, pattern matching is used to inspect a sum types like `Either Int String` and to proceed with the matching alternative. We can always project a choice between multiple alternatives to choice between one alternative (`Just`) and failure (`Nothing`):
|
|
|
And used as follows:
|
|
|
|
|
|
```wiki
|
|
|
maybeLeft :: Either a b -> Maybe a
|
|
|
maybeRight :: Either a b -> Maybe b
|
|
|
f (both -> (xs, h : t)) = h : (xs ++ t)
|
|
|
```
|
|
|
|
|
|
|
|
|
Some proposals build their patterns entirely from from such single alternative de-constructors functions of type `a -> Maybe b`, while some allow projection to multiple alternatives.
|
|
|
(However, this might cause a loss of sharing.)
|
|
|
|
|
|
#### Iterator Style
|
|
|
|
|
|
|
|
|
By restricting de-constructors to be of type `a -> Maybe b`, the Maybe can be made implicit, it doesn't show up in the pattern. Example:
|
|
|
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
|
|
|
data Product = ....some big data type...
|
|
|
type Size = Int
|
|
|
|
|
|
smallProd, medProd, bigProd :: Product -> Maybe Size
|
|
|
smallProd p = ...
|
|
|
medProd p = ...
|
|
|
bigProd p = ...
|
|
|
|
|
|
f :: Product -> ...
|
|
|
f (smallProd -> s) = ...
|
|
|
f (medProd -> s) = ...
|
|
|
f (bigProd -> s) = ...
|
|
|
```
|
|
|
length [] = []
|
|
|
length (x : length -> xs) = x + xs
|
|
|
|
|
|
map f [] = []
|
|
|
map f (x : map f -> xs) = x : xs
|
|
|
|
|
|
foldr f z [] = z
|
|
|
foldr f z (x : foldr f z -> xs) = x `f` xs
|
|
|
|
|
|
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
|
|
|
unfoldr f (f -> Just (a, unfoldr f -> b)) = a : b
|
|
|
unfoldr f other = []
|
|
|
```
|
|
|
|
|
|
Projection to multiple alternatives requires a new (or existing) data type for every group of alternatives introduced.
|
|
|
## Further Syntactic Extensions
|
|
|
|
|
|
```wiki
|
|
|
data Dimensions = Small | Medium | Big -- View type
|
|
|
prodSize :: Product -> Dimensions
|
|
|
prodSize = ...
|
|
|
|
|
|
f :: Product -> ...
|
|
|
f (prodSize -> Small) = ...
|
|
|
f (prodSize -> Medium) = ...
|
|
|
f (prodSize -> Big) = ...
|
|
|
```
|
|
|
|
|
|
Next, we describe two further syntactic extensions that we will implement.
|
|
|
|
|
|
Using a fixed set of multiple alternatives makes it more obvious whether the match is exhaustive or not.
|
|
|
### Implicit Maybe
|
|
|
|
|
|
|
|
|
While the implicit `Maybe a` is more compositional and nicely integrates with already existing uses of the `Maybe`-type, it cannot share expensive computations across multiple alternatives. This is a strong argument against the implicit `Maybe a`. To illustrate the problem, suppose that
|
|
|
Above, we saw several examples of view functions that return a `Maybe`, including:
|
|
|
|
|
|
```wiki
|
|
|
data Graph
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
np k n | k <= n = Just (n-k)
|
|
|
| otherwise = Nothing
|
|
|
```
|
|
|
|
|
|
|
|
|
represents a graph and that we want a function
|
|
|
which were used as follows:
|
|
|
|
|
|
```wiki
|
|
|
g :: Graph -> [...]
|
|
|
g (forest -> xs) = concatMap g xs
|
|
|
g (tree ->) = ...
|
|
|
g (dag ->) = ...
|
|
|
fib (np 2 -> Just n) = fib (n + 1) + fib n
|
|
|
```
|
|
|
|
|
|
|
|
|
These three properties are expensive to calculate but all three only
|
|
|
depend on the result of a single depth first search. By projecting the
|
|
|
disjoint sum to several `Maybe`s, the depth first search has to be
|
|
|
repeated every time. More importantly, there is \*no way\* for the compiler to optimize this because that would mean common subexpression elimination across
|
|
|
functions.
|
|
|
|
|
|
|
|
|
Some would argue that implicit the 'Maybe a' is *less* compositional than the explicit version. If no 'Maybe' is required, then the result of the view function can be any type at all, which can be pattern-matched in the ordinary way. Some examples of cute programming of well-known combinators:
|
|
|
We may implement a special syntax that makes the `Just` implicit, using *expr*`=>`*pat* for *expr*`-> Just`*pat*. An example use:
|
|
|
|
|
|
```wiki
|
|
|
map f [] = []
|
|
|
map f (x: map f -> xs) = x:xs
|
|
|
|
|
|
foldr f z [] = z
|
|
|
foldr f z (x: foldr f z -> xs) = x `f` xs
|
|
|
fib (np 2 => n) = fib (n + 1) + fib n
|
|
|
```
|
|
|
|
|
|
### Transparent ordinary Patterns
|
|
|
|
|
|
|
|
|
The lightweight view proposal has different syntax for view functions and ordinary pattern matches, they are not interchangeable. To use the abstraction view functions offer, you have to anticipate whether you can stick to ordinary constructors or whether you will switch to abstract constructors at some time. For example, a stack abstraction would have to use view patterns if we want to be able to change the concrete representation of stacks later on.
|
|
|
This syntax works very nicely with partial views:
|
|
|
|
|
|
```wiki
|
|
|
type Stack a = [a]
|
|
|
|
|
|
f :: Stack a
|
|
|
f (null?) = ...
|
|
|
f (pop? x xs) = ...
|
|
|
size (outUnit => _) = 1
|
|
|
size (outArrow => (t1, t2)) = size t1 + size t2
|
|
|
```
|
|
|
|
|
|
#### Implicit Tupling
|
|
|
|
|
|
This certainly discourages ordinary pattern matching. In other words,
|
|
|
implementing the proposal has considerable impact on ordinary pattern
|
|
|
matching (not in semantics but in use).
|
|
|
|
|
|
A further syntactic extension would be to have implcit Maybes with implicit tupling: multiple patterns after the `=>` are implicitly tupled. Then you could write:
|
|
|
|
|
|
The problem that needs to be solved is to introduce abstraction "after the fact".
|
|
|
```wiki
|
|
|
size (outArrow => t1 t2) = size t1 + size t2
|
|
|
```
|
|
|
|
|
|
### Implicit View Functions
|
|
|
|
|
|
On the other hand, 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.
|
|
|
|
|
|
### Nesting
|
|
|
Total views have one syntactic disadvantage relative to the iterated-case style definition that we started with: you have to repeat the name of the view function in each clause! We now describe a method for eliding the name of the view function.
|
|
|
|
|
|
|
|
|
In the lightweight proposal, view patterns are just an extra syntactic form of pattern, and they nest inside other patterns, and other patterns nest inside them. So one can write
|
|
|
The idea is that we distinguish a particular type class as a hook into the pattern compiler. The class has the following interface:
|
|
|
|
|
|
```wiki
|
|
|
f (sing -> x, True) = ...
|
|
|
g (Just (sing -> x)) = ...
|
|
|
h (Just (sing -> Just x)) = ...
|
|
|
class View a b where
|
|
|
view :: a -> b
|
|
|
```
|
|
|
|
|
|
|
|
|
And by the same token, view patterns nest inside each other:
|
|
|
Then, you can leave off the expresion in a view pattern, writing (`->`*pat*), to mean `view -> `*pat*. For example:
|
|
|
|
|
|
```wiki
|
|
|
k :: [[a]] -> a
|
|
|
k (sing -> sing -> x) = x
|
|
|
size (-> Unit) = 1
|
|
|
size (-> Arrow t1 t2) = size t1 + size t2
|
|
|
```
|
|
|
|
|
|
|
|
|
This convenient nesting is perhaps the biggest practical
|
|
|
difference between view patterns and pattern guards.
|
|
|
|
|
|
|
|
|
The majority of the proposals allow nesting.
|
|
|
|
|
|
### Integration with type classes
|
|
|
|
|
|
|
|
|
A view mechanism that integrates nicely with type classes would allow
|
|
|
a single "view" to decompose multiple different data types. For
|
|
|
example, a view might work on any type in class Num, or in class Sequence.
|
|
|
|
|
|
|
|
|
A good example is Haskell's existing (n+k) patterns. Here is how they
|
|
|
can be expressed using the view pattern proposed in this page (with different
|
|
|
syntax, of course):
|
|
|
means
|
|
|
|
|
|
```wiki
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
np k n | k <= n = Just (n-k)
|
|
|
| otherwise = Nothing
|
|
|
|
|
|
g :: Int -> Int
|
|
|
g (np 3 -> n) = n*2
|
|
|
|
|
|
h :: Integer -> Integer
|
|
|
h (np 9 -> n) = n*2
|
|
|
|
|
|
f :: Num a => a -> Int
|
|
|
f (np 10 -> n) = n -- Matches values >= 10, f a = (a - 10)
|
|
|
f (np 4 -> n) = 1 -- Matches values >= 4
|
|
|
f other = 2
|
|
|
size (view -> Unit) = 1
|
|
|
size (view -> Arrow t1 t2) = size t1 + size t2
|
|
|
```
|
|
|
|
|
|
|
|
|
Here a single, overloaded view, `np`, can be used
|
|
|
in `g`, and `h` to match against values of different types and,
|
|
|
in `f`'s case, any type in class Num. (Notice too the use of the value
|
|
|
input feature.)
|
|
|
|
|
|
|
|
|
This feature falls out very nicely from view patterns, but
|
|
|
not from all other proposals.
|
|
|
|
|
|
---
|
|
|
for the overloaded `view`.
|
|
|
|
|
|
## Efficiency of Views
|
|
|
|
|
|
|
|
|
View patterns can do arbitrary computation, perhaps expensive.
|
|
|
|
|
|
|
|
|
It's reasonable to expect the compiler to avoid repeated computation when
|
|
|
pattern line up in a column:
|
|
|
To use this mechanism, you add instances to `view`, as in:
|
|
|
|
|
|
```wiki
|
|
|
f (snoc -> x xs) True = ...
|
|
|
f (snoc -> x xs) False = ...
|
|
|
instance View Typ TypView where
|
|
|
view = (the view function from above)
|
|
|
```
|
|
|
|
|
|
|
|
|
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.
|
|
|
This way, you don't have to write the name of the view function in each case. However, there is a still a syntactic marker saying that the case isn't an ordinary pattern match, which may be useful in understanding the performance of the code.
|
|
|
|
|
|
---
|
|
|
|
|
|
## Use cases and examples
|
|
|
Of course, you can only use one view function for each hidden-type/view-type pair this way, since you can only have one instance of the class.
|
|
|
|
|
|
#### Functional dependencies
|
|
|
|
|
|
Whether views are really worth it can only be decide on the base of examples. Some are situations where you programmed and thought "I wish I had a view for that". Some are those snippets of code that unexpectedly use views to good effect.
|
|
|
|
|
|
### Sequences
|
|
|
|
|
|
|
|
|
Lists, queues, ByteStrings and 2-3-finger trees are all implementations of sequences, but only ordinary lists can be deconstructed using pattern matching. The need for list patterns on arbitrary sequence data structures is desperate. As if to ease the pain, Data.Sequence even defines the views from the left and from the right
|
|
|
The above implementation of `size` is given the following type:
|
|
|
|
|
|
```wiki
|
|
|
data ViewL a
|
|
|
= EmptyL
|
|
|
| (:<) a (Seq a)
|
|
|
|
|
|
viewl :: Seq a -> ViewL a
|
|
|
|
|
|
data ViewR a
|
|
|
= EmptyR
|
|
|
| (:>) (Seq a) a
|
|
|
|
|
|
viewr :: Seq a -> ViewR a
|
|
|
size :: View a TypView -> a -> Int
|
|
|
```
|
|
|
|
|
|
|
|
|
Thus, the presence of views has a direct impact on existing Haskell libraries. Arguably, a view proposal that wants to be effective for abstract data types likely has to have the transparent ordinary patterns feature.
|
|
|
|
|
|
|
|
|
The observations from [ Okasaki: Breadth-First Numbering - Lessons ... ](http://citeseer.ist.psu.edu/356396.html) suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of.
|
|
|
|
|
|
### Designing data structures
|
|
|
|
|
|
|
|
|
The abstractional power views offer can also be put to good use when designing data structures, as the following papers show
|
|
|
|
|
|
- [ R.Hinze: A fresh look on binary search trees](http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz).
|
|
|
- [ R.Hinze: A Simple Implementation Technique for Priority Search Queues](http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf)
|
|
|
|
|
|
### Sets and Inductive Graphs
|
|
|
|
|
|
|
|
|
Having the value input feature, even set like data structures come in reach for pattern matching. In fact, the key idea of [ M.Erwig: Inductive Graphs and Functional Graph Algorithms](http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz) is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch.
|
|
|
which may or may not be what you want. (For example, with nested view patterns, you can get into situations where the middle type connecting two view patterns is not determined.)
|
|
|
|
|
|
|
|
|
Here is a small module that allows to decompose sets with repsect to a given element, deleting it hereby.
|
|
|
Thus, it may be better to make one parameter of the type class determine the other (using associated type synonyms):
|
|
|
|
|
|
```wiki
|
|
|
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)
|
|
|
class View a where
|
|
|
type View a
|
|
|
view :: a -> View a
|
|
|
```
|
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
### 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](http://user.it.uu.se/~kostis/Papers/index.html#Conference)). Suppose we had a parsing function thus:
|
|
|
or
|
|
|
|
|
|
```wiki
|
|
|
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
|
|
|
class View b where
|
|
|
type Hidden b
|
|
|
view :: Hidden b -> a
|
|
|
```
|
|
|
|
|
|
|
|
|
Then we could write patterns like this:
|
|
|
Of course, a programmer can always use all three type classes explicitly; it's just a question of which one should be the default. We plan to try them out before deciding.
|
|
|
The downside of these versions is that you can only have one view for a type (when `a` determines `View a`) or you can only use a type as a view of one type (when `b` determines `Hidden b`) with the implicit syntax.
|
|
|
|
|
|
```wiki
|
|
|
parsePacket :: ByteString -> ...
|
|
|
parsePacket (bits 3 -> n (bits n -> val bs)) = ...
|
|
|
```
|
|
|
## Compilation
|
|
|
|
|
|
**Efficiency** View patterns can do arbitrary computation, perhaps expensive. It's reasonable to expect the compiler to avoid repeated computation when pattern line up in a column, as in `size` at the top of the page. 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.
|
|
|
|
|
|
This parses 3 bits to get the value of `n`, and then parses `n` bits to get
|
|
|
the value of `val`.
|
|
|
**Exhaustiveness/Redundancy.** 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 tricky too. So matters are not much worse than before.
|
|
|
|
|
|
### N+k patterns
|
|
|
## Features views can have
|
|
|
|
|
|
|
|
|
You can test for values. For example here's a view function that tests for values
|
|
|
greater than or equal to n:
|
|
|
In comparing the different views proposals below, it will be useful to have terminology for some features of views.
|
|
|
|
|
|
```wiki
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
np k n | k <= n = Just (n-k)
|
|
|
| otherwise = Nothing
|
|
|
#### Value input feature
|
|
|
|
|
|
f :: Num a => a -> a
|
|
|
f (np 10 -> n) = 0 -- Matches values >= 10
|
|
|
f (np 4 -> n) = 1 -- Matches values >= 4
|
|
|
f other = 2
|
|
|
```
|
|
|
|
|
|
Our proposal has the *value input* feature: the view function can be passed parameters; and those those parameters can mention variables bound by patterns to the left. For example, this permits a view function itself to be passed as an argument, so patterns, in a sense, become first class.
|
|
|
|
|
|
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).
|
|
|
#### Implicit `Maybe` feature
|
|
|
|
|
|
### Naming constants in one place
|
|
|
|
|
|
Our proposal has the *implicit `Maybe`* feature: the syntax *expr*`=>`*pat* permits the programmer to elide the `Just`, for example when using partial views.
|
|
|
|
|
|
We are always taught to write magic numbers, or constants, in one place only.
|
|
|
In C you can write
|
|
|
#### Transparent ordinary Patterns
|
|
|
|
|
|
```wiki
|
|
|
#define ERRVAL 4
|
|
|
```
|
|
|
|
|
|
Our proposal does not have the *transparent ordinary patterns* feature: view patterns are written differently than ordinary patterns.
|
|
|
There are pros and cons both ways:
|
|
|
The advantage of having transparent ordinary patterns is that you can replace a concrete datatype with an abstract type and a view without changing client code. A disadvantage is that view patterns can do arbitrary computation, perhaps expensive, so it's good to have a syntactic marker that some computation beyond ordinary pattern matching may be going on. Another disadvantage is that transparent ordinary patterns require a larger language extension than just a new form of pattern, so that certain names may be declared to be view constructors for a type. We consider our proposal's implicit-view-function syntax `(->`*pat*`)` to be a nice compromise between the two alternatives.
|
|
|
|
|
|
and then use `ERRVAL` in `switch` labels. You can't do that in Haskell, which is tiresome.
|
|
|
But with view pattern you can:
|
|
|
#### Nesting
|
|
|
|
|
|
```wiki
|
|
|
errVal :: Int -> Bool
|
|
|
errVal = (== 4)
|
|
|
|
|
|
f (errVal ->) = ...
|
|
|
```
|
|
|
Our proposal has the *nesting* feature: view patterns nest inside other patterns, and other patterns nest inside them. Nesting is perhaps the biggest practical difference between view patterns and pattern guards.
|
|
|
|
|
|
#### Integration with type classes
|
|
|
|
|
|
|
|
|
---
|
|
|
Our proposal *integrates with type classes*: an single view function can decompose multiple different data types, and the type class constraints are propagated to the user of the view.
|
|
|
|
|
|
## Related work
|
|
|
|
|
|
### Wadler's original paper (POPL 1987)
|
|
|
#### [ Wadler's original paper (POPL 1987)](http://homepages.inf.ed.ac.uk/wadler/papers/view/view.ps)
|
|
|
|
|
|
|
|
|
Wadler's paper was the first concrete proposal. It proposed a top-level view
|
... | ... | @@ -720,7 +491,7 @@ 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)](http://haskell.org/development/views.html)
|
|
|
#### [ Burton et al views (1996)](http://haskell.org/development/views.html)
|
|
|
|
|
|
|
|
|
This proposal is substantially more complicated than the one above; in particular it
|
... | ... | @@ -743,13 +514,13 @@ 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](http://citeseer.ist.psu.edu/okasaki98view.html)
|
|
|
#### [ Okasaki: views in Standard ML](http://citeseer.ist.psu.edu/okasaki98view.html)
|
|
|
|
|
|
|
|
|
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](http://citeseer.ist.psu.edu/erwig96active.html)
|
|
|
#### [ Erwig: active patterns](http://citeseer.ist.psu.edu/erwig96active.html)
|
|
|
|
|
|
|
|
|
Erwig's proposal for active patterns renders the Set example like this:
|
... | ... | @@ -775,11 +546,21 @@ follows from the `pat` declaration. |
|
|
|
|
|
Still the proposal does support the value input feature.
|
|
|
|
|
|
### [ Palao et al: active destructors (ICFP'96)](http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM)
|
|
|
#### [ Palao et al: active destructors (ICFP'96)](http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM)
|
|
|
|
|
|
|
|
|
Active Desctructors (ADs) are defined by a new form of top-level declaration. Our
|
|
|
singleton example would look like this:
|
|
|
Active Destructors (ADs) are defined by a new form of top-level declaration.
|
|
|
|
|
|
|
|
|
Where we'd write
|
|
|
|
|
|
```wiki
|
|
|
sing :: [a] -> a option
|
|
|
sing [x] = x
|
|
|
```
|
|
|
|
|
|
|
|
|
The equivalent active destructor would be
|
|
|
|
|
|
```wiki
|
|
|
Sing x match [x]
|
... | ... | @@ -792,8 +573,7 @@ Haskell functions, and need their own form of top-level declaration. They even |
|
|
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.
|
|
|
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
|
... | ... | @@ -808,9 +588,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,
|
|
|
only a bit more clumsily:
|
|
|
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
|
|
|
headV (x:xs) = Just x
|
... | ... | @@ -819,6 +597,13 @@ only a bit more clumsily: |
|
|
tailV (x:xs) = Just xs
|
|
|
tailV [] = Nothing
|
|
|
|
|
|
f (both -> (headV => x, tailV => ys)) = x:x:ys
|
|
|
```
|
|
|
|
|
|
|
|
|
An alternative to duplicating the value is to compose the functions:
|
|
|
|
|
|
```wiki
|
|
|
(@) :: (a -> Maybe b) -> (a -> Maybe c) -> a -> Maybe (b,c)
|
|
|
(f @ g) x = do { b <- f x; c <- g x; return (b,c) }
|
|
|
|
... | ... | @@ -827,15 +612,9 @@ only a bit more clumsily: |
|
|
```
|
|
|
|
|
|
|
|
|
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`.
|
|
|
This is a little clumsier: 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](http://citeseer.ist.psu.edu/erwig00pattern.html)
|
|
|
#### [ Erwig/Peyton Jones: transformational patterns](http://citeseer.ist.psu.edu/erwig00pattern.html)
|
|
|
|
|
|
|
|
|
This paper describes pattern guards, but it also introduces **transformational patterns**. (Although
|
... | ... | @@ -844,12 +623,12 @@ are very close to what we propose here. In particular, view functions are ordin |
|
|
so that the only changes are to patterns themselves.
|
|
|
|
|
|
|
|
|
There are two main differences (apart from syntax).
|
|
|
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).
|
|
|
|
|
|
### [ F\# Active Patterns](http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx)
|
|
|
#### [ F\# Active Patterns](http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx)
|
|
|
|
|
|
|
|
|
Simon started this design discussion after talking to Don Syme about F\#'s **active patterns**, which serve a very similar purpose. These combine both “total” discrimination (views) and “partial” discrimination (implicit maybe) into one mechanism. It does this by embedding the names of discriminators in the names of matching functions, via “values with structured names”. Sample uses include matching on .NET objects and XML.
|
... | ... | @@ -903,7 +682,7 @@ And for views: |
|
|
| Param(pos,cxs) -> Array.fold_right freeVarsAcc cxs (typ :: acc)
|
|
|
```
|
|
|
|
|
|
### [ Emir, Odersky, Williams: Matching objects with patterns](http://lambda-the-ultimate.org/node/1960)
|
|
|
#### [ Emir, Odersky, Williams: Matching objects with patterns](http://lambda-the-ultimate.org/node/1960)
|
|
|
|
|
|
|
|
|
Scala is an OO language with lots of functional features. It has algebraic data types and
|
... | ... | @@ -916,7 +695,7 @@ implicitly meaning "use the constructor in expressions, and use the extractor in |
|
|
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
|
|
|
|
|
|
[ Pattern synonyms](http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms)
|
|
|
are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see
|
... | ... | @@ -924,8 +703,7 @@ are a requested Haskell Prime feature. John Reppy had the same idea years ago fo |
|
|
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
|
|
|
The one way in which pattern synonyms are better than view patterns is thatn they define by-construction bi-directional maps. Example
|
|
|
|
|
|
```wiki
|
|
|
data Term = Var String | Term String [Term]
|
... | ... | @@ -954,10 +732,9 @@ With pattern views, we'd have to write two functions for the "plus" view: |
|
|
```
|
|
|
|
|
|
|
|
|
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).
|
|
|
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).
|
|
|
|
|
|
### [ Tullsen: First Class Patterns](http://citeseer.ist.psu.edu/tullsen00first.html)
|
|
|
#### [ Tullsen: First Class Patterns](http://citeseer.ist.psu.edu/tullsen00first.html)
|
|
|
|
|
|
|
|
|
First Class Patterns is an approach that attempts to
|
... | ... | @@ -978,7 +755,7 @@ The disadvantages are as follows: 1) An extra syntactic construct that binds var |
|
|
4) No attempt is made to integrate with Haskell's patterns, the idea is a proposal for an alternative when one needs more than simple patterns.
|
|
|
|
|
|
|
|
|
The examples at the top of this page would look like this with first class patterns:
|
|
|
The singleton example above would like this:
|
|
|
|
|
|
```wiki
|
|
|
f = {%sing n} .-> n+1
|
... | ... | @@ -989,7 +766,7 @@ The examples at the top of this page would look like this with first class patte |
|
|
|>> 2
|
|
|
```
|
|
|
|
|
|
### First class abstractions
|
|
|
#### First class abstractions
|
|
|
|
|
|
|
|
|
Several proposals suggest first class *abstractions* rather that first-class *patterns*. By a "first class abstraction" I mean a value of type
|
... | ... | @@ -1022,7 +799,19 @@ None of these proposals say |
|
|
anything about the patterns themselves, which in turn is all this
|
|
|
proposal deals with. Hence orthgonal.
|
|
|
|
|
|
### Barry Jay: First class patterns
|
|
|
#### Barry Jay: First class patterns
|
|
|
|
|
|
|
|
|
A yet more ambitious scheme is to treat patterns themselves as first class, even though they have free (binding) variables. This is the approach that Barry Jay has taken in his very interesting project on the *pattern calculus*. His [ home page](http://www-staff.it.uts.edu.au/~cbj) has more info.
|
|
|
|
|
|
#### Uses of Views
|
|
|
|
|
|
|
|
|
The observations from [ Okasaki: Breadth-First Numbering - Lessons ... ](http://citeseer.ist.psu.edu/356396.html) suggest that not having abstract pattern matching (for sequences) can indeed have great impact on the abstractions functional programmers can think of.
|
|
|
|
|
|
|
|
|
The abstractional power views offer can also be put to good use when designing data structures, as the following papers show
|
|
|
|
|
|
- [ R.Hinze: A fresh look on binary search trees](http://www.informatik.uni-bonn.de/~ralf/publications/SearchTree.ps.gz).
|
|
|
- [ R.Hinze: A Simple Implementation Technique for Priority Search Queues](http://www.informatik.uni-bonn.de/~ralf/publications/ICFP01.pdf)
|
|
|
- The the key idea of [ M.Erwig: Inductive Graphs and Functional Graph Algorithms](http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.ps.gz) is to introduce a suitable view of graphs. This way, graphs can be liberated from their notoriously imperative touch. |