|
CONVERSION ERROR
|
|
# View patterns: lightweight views for Haskell
|
|
|
|
|
|
Error: HttpError (HttpExceptionRequest Request {
|
|
|
|
host = "ghc.haskell.org"
|
|
This page describes a rather lightweight proposal for adding views to
|
|
port = 443
|
|
Haskell Prime. I'm thinking of prototyping the idea in GHC, so I'm looking
|
|
secure = True
|
|
for feedback.
|
|
requestHeaders = []
|
|
|
|
path = "/trac/ghc/wiki/ViewPatterns"
|
|
|
|
queryString = "?version=16"
|
|
This page is open to editing by anyone. (Chase the "Wiki notes" link in the sidebar to find out how.)
|
|
method = "GET"
|
|
|
|
proxy = Nothing
|
|
## The problem
|
|
rawBody = False
|
|
|
|
redirectCount = 10
|
|
|
|
responseTimeout = ResponseTimeoutDefault
|
|
We are keen on abstraction, but pattern matching is so convenient that
|
|
requestVersion = HTTP/1.1
|
|
we break abstractions all the time. It's our dirty little secret.
|
|
}
|
|
Looked at this way, object-oriented folk are much more obsessive
|
|
(StatusCodeException (Response {responseStatus = Status {statusCode = 403, statusMessage = "Forbidden"}, responseVersion = HTTP/1.1, responseHeaders = [("Date","Sun, 10 Mar 2019 07:01:02 GMT"),("Server","Apache/2.2.22 (Debian)"),("Strict-Transport-Security","max-age=63072000; includeSubDomains"),("Vary","Accept-Encoding"),("Content-Encoding","gzip"),("Content-Length","252"),("Content-Type","text/html; charset=iso-8859-1")], responseBody = (), responseCookieJar = CJ {expose = []}, responseClose' = ResponseClose}) "<!DOCTYPE HTML PUBLIC \"-//IETF//DTD HTML 2.0//EN\">\n<html><head>\n<title>403 Forbidden</title>\n</head><body>\n<h1>Forbidden</h1>\n<p>You don't have permission to access /trac/ghc/wiki/ViewPatterns\non this server.</p>\n<hr>\n<address>Apache/2.2.22 (Debian) Server at ghc.haskell.org Port 443</address>\n</body></html>\n"))
|
|
about abstraction than we are: everything (including field access
|
|
|
|
these days) is a method.
|
|
Original source:
|
|
|
|
|
|
|
|
```trac
|
|
Views have, in one form or another, repeatedly been proposed as a
|
|
[[PageOutline]]
|
|
solution for this problem. (See the end for a comparison with related work.)
|
|
= View patterns: lightweight views for Haskell =
|
|
|
|
|
|
## The proposal informally
|
|
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.
|
|
The proposal introduces a new form of pattern, called a **view pattern**
|
|
|
|
Here are some function definitions using view patterns.
|
|
This page is open to editing by anyone. (Chase the "Wiki notes" link in the sidebar to find out how.)
|
|
To read these definitions, imagine that `sing` is
|
|
|
|
a sort of constructor that matches singleton lists.
|
|
== The problem ==
|
|
|
|
|
|
```wiki
|
|
We are keen on abstraction, but pattern matching is so convenient that
|
|
f :: [Int] -> Int
|
|
we break abstractions all the time. It's our dirty little secret.
|
|
f (sing -> n) = n+1 -- Equiv to: f [n] = ...
|
|
Looked at this way, object-oriented folk are much more obsessive
|
|
f other = 0
|
|
about abstraction than we are: everything (including field access
|
|
|
|
these days) is a method.
|
|
g :: [Bool] -> Int
|
|
|
|
g (sing -> True) = 0 -- Equiv to: g [True] = ...
|
|
Views have, in one form or another, repeatedly been proposed as a
|
|
g (sing -> False) = 1 -- Equiv to: g [False] = ...
|
|
solution for this problem. (See the end for a comparison with related work.)
|
|
g other = 2
|
|
|
|
|
|
== The proposal informally ==
|
|
h :: [[Int]] -> Int
|
|
|
|
h (sing -> x : sing -> y : _) = x+y
|
|
The proposal introduces a new form of pattern, called a '''view pattern'''
|
|
-- Equiv to: h ([x]:[y]:_) = ...
|
|
Here are some function definitions using view patterns.
|
|
h other = 0
|
|
To read these definitions, imagine that `sing` is
|
|
```
|
|
a sort of constructor that matches singleton lists.
|
|
|
|
{{{
|
|
|
|
f :: [Int] -> Int
|
|
So what is `sing`? It is just an ordinary Haskell function that
|
|
f (sing -> n) = n+1 -- Equiv to: f [n] = ...
|
|
returns a `Maybe` type:
|
|
f other = 0
|
|
|
|
|
|
```wiki
|
|
g :: [Bool] -> Int
|
|
sing :: [a] -> Maybe a
|
|
g (sing -> True) = 0 -- Equiv to: g [True] = ...
|
|
sing [x] = Just x
|
|
g (sing -> False) = 1 -- Equiv to: g [False] = ...
|
|
sing other = Nothing
|
|
g other = 2
|
|
```
|
|
|
|
|
|
h :: [[Int]] -> Int
|
|
|
|
h (sing -> x : sing -> y : _) = x+y
|
|
So `sing` simply identifies singleton lists, and returns the payload (that is,
|
|
-- Equiv to: h ([x]:[y]:_) = ...
|
|
the singleton element; otherwise it returns `Nothing`.
|
|
h other = 0
|
|
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
|
|
So what is `sing`? It is just an ordinary Haskell function that
|
|
of `sing` might not have intended it to be used in pattern matching.
|
|
returns a `Maybe` type:
|
|
|
|
{{{
|
|
---
|
|
sing :: [a] -> Maybe a
|
|
|
|
sing [x] = Just x
|
|
## The proposal more formally
|
|
sing other = Nothing
|
|
|
|
}}}
|
|
|
|
So `sing` simply identifies singleton lists, and returns the payload (that is,
|
|
The only special stuff is in the pattern.
|
|
the singleton element; otherwise it returns `Nothing`.
|
|
The sole change is this: add a single new sort of pattern, of the
|
|
It is very important that '''there is nothing special about `sing`'''. It is
|
|
form
|
|
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.
|
|
>
|
|
|
|
> (*expr*`->`*pat*)
|
|
---------------------------
|
|
|
|
== The proposal more formally ==
|
|
|
|
|
|
where *expr* is an arbitrary Haskell expression. I'll call a pattern
|
|
The only special stuff is in the pattern.
|
|
of this form a **view pattern**.
|
|
The sole change is this: add a single new sort of pattern, of the
|
|
|
|
form
|
|
|
|
(''expr'' `->` ''pat'')
|
|
From a **scoping** point of view, the variables bound by the pattern (*expr*`->`*pat*)
|
|
|
|
are simply the variables bound by ``pat``.
|
|
where ''expr'' is an arbitrary Haskell expression. I'll call a pattern
|
|
Any variables in ``expr`` are bound occurrences.
|
|
of this form a '''view pattern'''.
|
|
|
|
|
|
|
|
From a '''scoping''' point of view, the variables bound by the pattern (''expr'' `->` ''pat'')
|
|
The rule for **pattern-matching** is this:
|
|
are simply the variables bound by ``pat``.
|
|
To match a value *v* against a pattern *(expr -\> p)*,
|
|
Any variables in ``expr`` are bound occurrences.
|
|
|
|
|
|
- Evaluate *(expr v)*
|
|
The rule for '''pattern-matching''' is this:
|
|
- If the result is *(`Just` w)*, match *w* against *p*
|
|
To match a value ''v'' against a pattern ''(expr -> p)'',
|
|
- If the result is `Nothing`, the match fails.
|
|
* 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
|
|
The '''typing rule''' is similarly simple.
|
|
*t1 `-> Maybe` t2*. Then the pattern *pat* must have type *t2*, and the
|
|
The expression ''expr'' must have type
|
|
whole pattern (*expr*`->`*pat*) has type *t1*.
|
|
''t1 `-> Maybe` t2''. Then the pattern ''pat'' must have type ''t2'', and the
|
|
|
|
whole pattern (''expr'' `->` ''pat'') has type ''t1''.
|
|
### Nesting
|
|
|
|
|
|
=== Nesting ===
|
|
|
|
|
|
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
|
|
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
|
|
|
|
{{{
|
|
```wiki
|
|
f (sing -> x, True) = ...
|
|
f (sing -> x, True) = ...
|
|
g (Just (sing -> x)) = ...
|
|
g (Just (sing -> x)) = ...
|
|
h (Just (sing -> Just x)) = ...
|
|
h (Just (sing -> Just x)) = ...
|
|
}}}
|
|
```
|
|
And by the same token, view patterns nest inside each other:
|
|
|
|
{{{
|
|
|
|
k :: [[a]] -> a
|
|
And by the same token, view patterns nest inside each other:
|
|
k (sing -> sing -> x) = x
|
|
|
|
}}}
|
|
```wiki
|
|
This convenient nesting is perhaps the biggest practical
|
|
k :: [[a]] -> a
|
|
difference between view patterns and pattern guards.
|
|
k (sing -> sing -> x) = x
|
|
|
|
```
|
|
|
|
|
|
=== The value input feature ===
|
|
|
|
|
|
This convenient nesting is perhaps the biggest practical
|
|
Note that the ''expr'' is an arbitrary Haskell expression. For example, suppose you wrote
|
|
difference between view patterns and pattern guards.
|
|
a regular expression matching function:
|
|
|
|
{{{
|
|
### The value input feature
|
|
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
|
|
Note that the *expr* is an arbitrary Haskell expression. For example, suppose you wrote
|
|
}}}
|
|
a regular expression matching function:
|
|
then you could use it in patterns thus:
|
|
|
|
{{{
|
|
```wiki
|
|
f :: String -> String
|
|
regexp :: String -> String -> Maybe (String, String)
|
|
f (regexp "[a-z]*" -> (name, rest)) = ...
|
|
-- (regexp r s) parses a string matching regular expression r
|
|
}}}
|
|
-- the front of s, returning the matched string and remainder of s
|
|
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
|
|
then you could use it in patterns thus:
|
|
all view proposals. I'll call it the '''value input feature'''.
|
|
|
|
|
|
```wiki
|
|
Indeed, in a sense, patterns become first class. For example, one could pass a pattern
|
|
f :: String -> String
|
|
as an argument to a function thus:
|
|
f (regexp "[a-z]*" -> (name, rest)) = ...
|
|
{{{
|
|
```
|
|
g :: (Int -> Maybe Int) -> Int -> ...
|
|
|
|
g p (p -> x) = ...
|
|
|
|
}}}
|
|
Of course, the argument does not need to be a constant as it is here.
|
|
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`.
|
|
**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
|
|
Here is another rather cute example:
|
|
all view proposals. I'll call it the **value input feature**.
|
|
{{{
|
|
|
|
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
|
|
|
|
unfoldr f (f -> (a, b)) = a : unfoldr f b
|
|
Indeed, in a sense, patterns become first class. For example, one could pass a pattern
|
|
unfoldr f other = []
|
|
as an argument to a function thus:
|
|
}}}
|
|
|
|
|
|
```wiki
|
|
=== Possible extension 1: multi-argument view patterns ===
|
|
g :: (Int -> Maybe Int) -> Int -> ...
|
|
|
|
g p (p -> x) = ...
|
|
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:
|
|
|
|
{{{
|
|
Here the first argument `p` can be thought of as a pattern passed to `g`, which
|
|
data Maybe2 a b = Nothing2 | Just2 a b
|
|
is used to match the second argument of `g`.
|
|
data Maybe3 a b c = Nothing3 | Just3 a b c
|
|
|
|
-- ..etc..., up to 8 perhaps (sigh)
|
|
|
|
}}}
|
|
Here is another rather cute example:
|
|
With this in hand we can extend the views story to have multiple sub-patterns.
|
|
|
|
Example:
|
|
```wiki
|
|
{{{
|
|
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
|
|
snoc :: [a] -> Maybe2 [a] a
|
|
unfoldr f (f -> (a, b)) = a : unfoldr f b
|
|
snoc [] = Nothing2
|
|
unfoldr f other = []
|
|
snoc (x:xs) = case snoc xs of
|
|
```
|
|
Nothing2 -> Just2 [] x
|
|
|
|
Just2 ys y -> Just2 (x:ys) y
|
|
### Possible extension 1: multi-argument view patterns
|
|
|
|
|
|
last :: [Int] -> Int
|
|
|
|
last (snoc -> xs x) = x
|
|
It would be quite useful to allow more than one sub-pattern in a view
|
|
last other = error "empty list"
|
|
pattern. To do this we'd need a `Maybe` data type that returns more than
|
|
}}}
|
|
one result, thus:
|
|
It is tiresome that we need types `Maybe2`, `Maybe3` etc, but we already have
|
|
|
|
that in Haskell; consider `zip3`, `zip4` and so on.
|
|
```wiki
|
|
We could always get away without it, by sticking to unary view patterns and
|
|
data Maybe2 a b = Nothing2 | Just2 a b
|
|
using tuples, thus:
|
|
data Maybe3 a b c = Nothing3 | Just3 a b c
|
|
{{{
|
|
-- ..etc..., up to 8 perhaps (sigh)
|
|
snoc :: [a] -> Maybe ([a], a)
|
|
```
|
|
snoc [] = Nothing
|
|
|
|
snoc (x:xs) = case snoc xs of
|
|
|
|
Nothing -> Just ([], x)
|
|
With this in hand we can extend the views story to have multiple sub-patterns.
|
|
Just (ys,y) -> Just (x:ys, y)
|
|
Example:
|
|
|
|
|
|
last :: [Int] -> Int
|
|
```wiki
|
|
last (snoc -> (xs, x)) = x
|
|
snoc :: [a] -> Maybe2 [a] a
|
|
last other = error "empty list"
|
|
snoc [] = Nothing2
|
|
}}}
|
|
snoc (x:xs) = case snoc xs of
|
|
But the tuple looks a bit clumsy.
|
|
Nothing2 -> Just2 [] x
|
|
|
|
Just2 ys y -> Just2 (x:ys) y
|
|
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)',
|
|
last :: [Int] -> Int
|
|
'e' should return a `Maybe3`.
|
|
last (snoc -> xs x) = x
|
|
|
|
last other = error "empty list"
|
|
If n=0, then we want `Maybe0`, which is called `Bool`. Thus
|
|
```
|
|
{{{
|
|
|
|
even :: Int -> Bool
|
|
|
|
even n = n `div` 2 == 0
|
|
It is tiresome that we need types `Maybe2`, `Maybe3` etc, but we already have
|
|
|
|
that in Haskell; consider `zip3`, `zip4` and so on.
|
|
f (even ->) = ... -- Matches even numbers
|
|
We could always get away without it, by sticking to unary view patterns and
|
|
f other = ...
|
|
using tuples, thus:
|
|
}}}
|
|
|
|
Here `even` is used as a nullary view pattern, with no sub-patterns
|
|
```wiki
|
|
following the `->`.
|
|
snoc :: [a] -> Maybe ([a], a)
|
|
|
|
snoc [] = Nothing
|
|
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.
|
|
snoc (x:xs) = case snoc xs of
|
|
|
|
Nothing -> Just ([], x)
|
|
=== Possible extension 2: the implicit `Maybe` ===
|
|
Just (ys,y) -> Just (x:ys, y)
|
|
|
|
|
|
Thus far, the view function is required to return a `Maybe` type, with `Nothing` to indicate match
|
|
last :: [Int] -> Int
|
|
failure. An alternative, presented in the Erwig paper on transformational patterns (see Related work below),
|
|
last (snoc -> (xs, x)) = x
|
|
this implicit matching is not performed; instead, the sub-pattern is matched against
|
|
last other = error "empty list"
|
|
whatever the view function returns. So you'd have to write:
|
|
```
|
|
{{{
|
|
|
|
f (snoc -> Just2 xs x) = ...
|
|
|
|
}}}
|
|
But the tuple looks a bit clumsy.
|
|
(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:
|
|
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)',
|
|
data Product = ....some big data type...
|
|
'e' should return a `Maybe3`.
|
|
|
|
|
|
data Size = Small | Medium | Big -- View type
|
|
|
|
prodSize :: Product -> Size
|
|
If n=0, then we want `Maybe0`, which is called `Bool`. Thus
|
|
prodSize = ....
|
|
|
|
|
|
```wiki
|
|
f :: Product -> ...
|
|
even :: Int -> Bool
|
|
f (prodSize -> Small) = ...
|
|
even n = n `div` 2 == 0
|
|
f (prodSize -> Medium) = ...
|
|
|
|
f (prodSize -> Big) = ...
|
|
f (even ->) = ... -- Matches even numbers
|
|
}}}
|
|
f other = ...
|
|
With the built-in `Maybe` proposal, you'd instead write something like this:
|
|
```
|
|
{{{
|
|
|
|
smallProd, medProd, bigProd :: Product -> Bool
|
|
|
|
smallProd p = ...
|
|
Here `even` is used as a nullary view pattern, with no sub-patterns
|
|
medProd p = ...
|
|
following the `->`.
|
|
bigProd p = ...
|
|
|
|
|
|
|
|
f :: Product -> ...
|
|
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.
|
|
f (smallProd ->) = ...
|
|
|
|
f (medProd ->) = ...
|
|
### Possible extension 2: the implicit `Maybe`
|
|
f (bigProd ->) = ...
|
|
|
|
}}}
|
|
|
|
This is not obviously worse, except that the first version is more
|
|
Thus far, the view function is required to return a `Maybe` type, with `Nothing` to indicate match
|
|
obviously exhaustive. Incidentally, both should generate the same
|
|
failure. An alternative, presented in the Erwig paper on transformational patterns (see Related work below),
|
|
code.
|
|
this implicit matching is not performed; instead, the sub-pattern is matched against
|
|
|
|
whatever the view function returns. So you'd have to write:
|
|
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.
|
|
```wiki
|
|
* No built-in `Maybe` stuff. Arguably this is more consistent with pattern-guards.
|
|
f (snoc -> Just2 xs x) = ...
|
|
* Both are available, with different syntax. For example
|
|
```
|
|
* ''(expr `->` pat)'' for the built-in `Maybe` story
|
|
|
|
* ''(expr `=>` pat)'' with no bulit-in `Maybe`
|
|
|
|
|
|
(Note the tiresome `Just2`.)
|
|
== Efficiency ==
|
|
The benefit of not having the implicit matching is that you can write functions that are, perhaps,
|
|
|
|
more view-like. Example:
|
|
View patterns can do arbitrary computation, perhaps expensive. So
|
|
|
|
it's good to have a syntactically-distinct notation that reminds the
|
|
```wiki
|
|
programmer that some computation beyond ordinary pattern matching may
|
|
data Product = ....some big data type...
|
|
be going on.
|
|
|
|
|
|
data Size = Small | Medium | Big -- View type
|
|
It's reasonable to expect the compiler to avoid repeated computation when
|
|
prodSize :: Product -> Size
|
|
pattern line up in a column:
|
|
prodSize = ....
|
|
{{{
|
|
|
|
f (snoc -> x xs) True = ...
|
|
f :: Product -> ...
|
|
f (snoc -> x xs) False = ...
|
|
f (prodSize -> Small) = ...
|
|
}}}
|
|
f (prodSize -> Medium) = ...
|
|
In pattern-guard form, common sub-expression should achieve the same
|
|
f (prodSize -> Big) = ...
|
|
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.
|
|
|
|
|
|
With the built-in `Maybe` proposal, you'd instead write something like this:
|
|
---------------------------
|
|
|
|
== Features views can have ==
|
|
```wiki
|
|
|
|
smallProd, medProd, bigProd :: Product -> Bool
|
|
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
|
|
smallProd p = ...
|
|
|
|
medProd p = ...
|
|
=== Value input feature ===
|
|
bigProd p = ...
|
|
|
|
|
|
This features allows to introduce additional parameters into the computation. Perhaps the most basic example are (n+k) patterns
|
|
f :: Product -> ...
|
|
{{{
|
|
f (smallProd ->) = ...
|
|
fib :: Int -> Int
|
|
f (medProd ->) = ...
|
|
fib 0 = 1
|
|
f (bigProd ->) = ...
|
|
fib 1 = 1
|
|
```
|
|
fib (n + 2) = fib (n + 1) + fib n
|
|
|
|
}}}
|
|
|
|
Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc.
|
|
This is not obviously worse, except that the first version is more
|
|
|
|
obviously exhaustive. Incidentally, both should generate the same
|
|
Of course, the real power unfolds when the extra parameter can be given at runtime
|
|
code.
|
|
{{{
|
|
|
|
f :: Int -> Int -> ...
|
|
|
|
f n (n + m) = m -- f a b = (b - a)
|
|
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.
|
|
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:
|
|
- No built-in `Maybe` stuff. Arguably this is more consistent with pattern-guards.
|
|
{{{
|
|
- Both are available, with different syntax. For example
|
|
regexp :: String -> String -> Maybe (String, String)
|
|
|
|
-- (regexp r s) parses a string matching regular expression r
|
|
- *(expr `->` pat)* for the built-in `Maybe` story
|
|
-- the front of s, returning the matched string and remainder of s
|
|
- *(expr `=>` pat)* with no bulit-in `Maybe`
|
|
}}}
|
|
|
|
then you could use it in patterns thus:
|
|
## Efficiency
|
|
{{{
|
|
|
|
f :: String -> String
|
|
|
|
f (regexp "[a-z]*" -> (name, rest)) = ...
|
|
View patterns can do arbitrary computation, perhaps expensive. So
|
|
}}}
|
|
it's good to have a syntactically-distinct notation that reminds the
|
|
Of course, the argument does not need to be a constant as it is here.
|
|
programmer that some computation beyond ordinary pattern matching may
|
|
|
|
be going on.
|
|
The (n+k) patterns can be implemented (with different syntax, of course) with a view function that tests for values greater than or equal to n:
|
|
|
|
{{{
|
|
|
|
np :: Num a => a -> a -> Maybe a
|
|
It's reasonable to expect the compiler to avoid repeated computation when
|
|
np k n | k <= n = Just (n-k)
|
|
pattern line up in a column:
|
|
| otherwise = Nothing
|
|
|
|
|
|
```wiki
|
|
f :: Num a => a -> Int
|
|
f (snoc -> x xs) True = ...
|
|
f (np 10 -> n) = n -- Matches values >= 10, f a = (a - 10)
|
|
f (snoc -> x xs) False = ...
|
|
f (np 4 -> n) = 1 -- Matches values >= 4
|
|
```
|
|
f other = 2
|
|
|
|
}}}
|
|
|
|
|
|
In pattern-guard form, common sub-expression should achieve the same
|
|
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:
|
|
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
|
|
g :: (Int -> Maybe Int) -> Int -> ...
|
|
guaranteed.
|
|
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`.
|
|
## Features views can have
|
|
|
|
|
|
=== Implicit `Maybe` feature ===
|
|
|
|
|
|
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
|
|
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`):
|
|
|
|
{{{
|
|
### Value input feature
|
|
maybeLeft :: Either a b -> Maybe a
|
|
|
|
maybeRight :: Either a b -> Maybe b
|
|
|
|
}}}
|
|
This features allows to introduce additional parameters into the computation. Perhaps the most basic example are (n+k) patterns
|
|
|
|
|
|
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.
|
|
```wiki
|
|
|
|
fib :: Int -> Int
|
|
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:
|
|
fib 0 = 1
|
|
{{{
|
|
fib 1 = 1
|
|
data Product = ....some big data type...
|
|
fib (n + 2) = fib (n + 1) + fib n
|
|
type Size = Int
|
|
```
|
|
|
|
|
|
smallProd, medProd, bigProd :: Product -> Maybe Size
|
|
|
|
smallProd p = ...
|
|
Here, the number 2 can be arbitrary, we are not fixed to a "finite" set of "constructors" (+1), (+2) etc.
|
|
medProd p = ...
|
|
|
|
bigProd p = ...
|
|
|
|
|
|
Of course, the real power unfolds when the extra parameter can be given at runtime
|
|
f :: Product -> ...
|
|
|
|
f (smallProd -> s) = ...
|
|
```wiki
|
|
f (medProd -> s) = ...
|
|
f :: Int -> Int -> ...
|
|
f (bigProd -> s) = ...
|
|
f n (n + m) = m -- f a b = (b - a)
|
|
}}}
|
|
```
|
|
|
|
|
|
Projection to multiple alternatives requires a new data type for every group of alternatives introduced.
|
|
|
|
{{{
|
|
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:
|
|
data Dimensions = Small | Medium | Big -- View type
|
|
|
|
prodSize :: Product -> Dimensions
|
|
```wiki
|
|
prodSize = ...
|
|
regexp :: String -> String -> Maybe (String, String)
|
|
|
|
-- (regexp r s) parses a string matching regular expression r
|
|
f :: Product -> ...
|
|
-- the front of s, returning the matched string and remainder of s
|
|
f (prodSize -> Small) = ...
|
|
```
|
|
f (prodSize -> Medium) = ...
|
|
|
|
f (prodSize -> Big) = ...
|
|
|
|
}}}
|
|
then you could use it in patterns thus:
|
|
|
|
|
|
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
|
|
```wiki
|
|
|
|
f :: String -> String
|
|
{{{
|
|
f (regexp "[a-z]*" -> (name, rest)) = ...
|
|
data Graph
|
|
```
|
|
}}}
|
|
|
|
represents a graph and that we want a function
|
|
|
|
{{{
|
|
Of course, the argument does not need to be a constant as it is here.
|
|
g :: Graph -> [...]
|
|
|
|
g (forest -> xs) = concatMap g xs
|
|
|
|
g (tree ->) = ...
|
|
The (n+k) patterns can be implemented (with different syntax, of course) with a view function that tests for values greater than or equal to n:
|
|
g (dag ->) = ...
|
|
|
|
}}}
|
|
```wiki
|
|
These three properties are expensive to calculate but all three only
|
|
np :: Num a => a -> a -> Maybe a
|
|
depend on the result of a single depth first search. By projecting the
|
|
np k n | k <= n = Just (n-k)
|
|
disjoint sum to several `Maybe`s, the depth first search has to be
|
|
| otherwise = Nothing
|
|
repeated every time. More importantly, there is *no way* for the compiler to optimize this because that would mean common subexpression elimination across
|
|
|
|
functions.
|
|
f :: Num a => a -> Int
|
|
|
|
f (np 10 -> n) = n -- Matches values >= 10, f a = (a - 10)
|
|
=== Transparent ordinary Patterns ===
|
|
f (np 4 -> n) = 1 -- Matches values >= 4
|
|
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.
|
|
f other = 2
|
|
{{{
|
|
```
|
|
type Stack a = [a]
|
|
|
|
|
|
|
|
f :: Stack a
|
|
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:
|
|
f (null?) = ...
|
|
|
|
f (pop? x xs) = ...
|
|
```wiki
|
|
}}}
|
|
g :: (Int -> Maybe Int) -> Int -> ...
|
|
This certainly discourages ordinary pattern matching. In other words,
|
|
g p (p -> x) = ...
|
|
implementing the proposal has considerable impact on ordinary pattern
|
|
```
|
|
matching (not in semantics but in use).
|
|
|
|
|
|
|
|
The problem that needs to be solved is to introduce abstraction "after the fact".
|
|
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`.
|
|
---------------------------
|
|
|
|
== More examples ==
|
|
### Implicit `Maybe` feature
|
|
|
|
|
|
=== Erlang-style parsing ===
|
|
|
|
|
|
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`):
|
|
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 ([http://user.it.uu.se/~kostis/Papers/index.html#Conference "Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07]). Suppose we had a parsing function thus:
|
|
```wiki
|
|
{{{
|
|
maybeLeft :: Either a b -> Maybe a
|
|
bits :: Int -> ByteString -> Maybe2 Word ByteString
|
|
maybeRight :: Either a b -> Maybe b
|
|
-- (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:
|
|
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.
|
|
{{{
|
|
|
|
parsePacket :: ByteString -> ...
|
|
|
|
parsePacket (bits 3 -> n (bits n -> val bs)) = ...
|
|
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:
|
|
}}}
|
|
|
|
This parses 3 bits to get the value of `n`, and then parses `n` bits to get
|
|
```wiki
|
|
the value of `val`.
|
|
data Product = ....some big data type...
|
|
|
|
type Size = Int
|
|
=== Sets as lists ===
|
|
|
|
|
|
smallProd, medProd, bigProd :: Product -> Maybe Size
|
|
Here is a module implementing sets as lists:
|
|
smallProd p = ...
|
|
{{{
|
|
medProd p = ...
|
|
module Set( Set, empty, insert, delete, has) where
|
|
bigProd p = ...
|
|
|
|
|
|
newtype Set a = S [a]
|
|
f :: Product -> ...
|
|
|
|
f (smallProd -> s) = ...
|
|
has :: Eq a => a -> Set a -> Maybe (Set a)
|
|
f (medProd -> s) = ...
|
|
has x (S xs) | x `elem` xs = Just (xs \\ x)
|
|
f (bigProd -> s) = ...
|
|
| otherwise = Nothing
|
|
```
|
|
|
|
|
|
delete :: a -> Set a -> Set a
|
|
|
|
delete x (has x -> s) = s
|
|
Projection to multiple alternatives requires a new data type for every group of alternatives introduced.
|
|
delete x s = s
|
|
|
|
|
|
```wiki
|
|
insert :: a -> Set a -> Set a
|
|
data Dimensions = Small | Medium | Big -- View type
|
|
insert x s@(has x -> _) = s
|
|
prodSize :: Product -> Dimensions
|
|
insert x (S xs) = S (x:xs)
|
|
prodSize = ...
|
|
}}}
|
|
|
|
Notice that in the left-hand side `delete x (has x -> s)`, the first `x` is a binding occurrence,
|
|
f :: Product -> ...
|
|
but the second is merely an argument to `has` and is a bound occurrence.
|
|
f (prodSize -> Small) = ...
|
|
|
|
f (prodSize -> Medium) = ...
|
|
=== N+k patterns ===
|
|
f (prodSize -> Big) = ...
|
|
|
|
```
|
|
You can test for values. For example here's a view function that tests for values
|
|
|
|
greater than or equal to n:
|
|
|
|
{{{
|
|
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
|
|
np :: Num a => a -> a -> Maybe a
|
|
|
|
np k n | k <= n = Just (n-k)
|
|
```wiki
|
|
| otherwise = Nothing
|
|
data Graph
|
|
|
|
```
|
|
f :: Num a => a -> Int
|
|
|
|
f (np 10 -> n) = 0 -- Matches values >= 10
|
|
|
|
f (np 4 -> n) = 1 -- Matches values >= 4
|
|
represents a graph and that we want a function
|
|
f other = 2
|
|
|
|
}}}
|
|
```wiki
|
|
You will recognise these as (n+k) patterns, albeit with slightly different syntax.
|
|
g :: Graph -> [...]
|
|
(Incidentally, this example shows that the view function can be overloaded, and
|
|
g (forest -> xs) = concatMap g xs
|
|
that its use in a view pattern gives rise to a type-class constraint (in this case,
|
|
g (tree ->) = ...
|
|
that in turn makes `f` overloaded).
|
|
g (dag ->) = ...
|
|
|
|
```
|
|
=== Naming constants in one place ===
|
|
|
|
|
|
|
|
We are always taught to write magic numbers, or constants, in one place only.
|
|
These three properties are expensive to calculate but all three only
|
|
In C you can write
|
|
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
|
|
#define ERRVAL 4
|
|
repeated every time. More importantly, there is \*no way\* for the compiler to optimize this because that would mean common subexpression elimination across
|
|
}}}
|
|
functions.
|
|
and then use `ERRVAL` in `switch` labels. You can't do that in Haskell, which is tiresome.
|
|
|
|
But with view pattern you can:
|
|
### Transparent ordinary Patterns
|
|
{{{
|
|
|
|
errVal :: Int -> Bool
|
|
|
|
errVal = (== 4)
|
|
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.
|
|
|
|
|
|
f (errVal ->) = ...
|
|
```wiki
|
|
}}}
|
|
type Stack a = [a]
|
|
|
|
|
|
== Concrete syntax ==
|
|
f :: Stack a
|
|
A disadvantage of the arrow syntax is that it looks a bit confusing
|
|
f (null?) = ...
|
|
when it appears in a case expression:
|
|
f (pop? x xs) = ...
|
|
{{{
|
|
```
|
|
last xs = case xs of
|
|
|
|
(snoc -> x xs) -> x
|
|
|
|
}}}
|
|
This certainly discourages ordinary pattern matching. In other words,
|
|
(Also that "x xs" looks a bit like `x` applied to `xs`.)
|
|
implementing the proposal has considerable impact on ordinary pattern
|
|
|
|
matching (not in semantics but in use).
|
|
Here are some other possible syntax choices I've considered:
|
|
|
|
{{{
|
|
|
|
f ($snoc x xs) = ... -- Use prefix "$"
|
|
The problem that needs to be solved is to introduce abstraction "after the fact".
|
|
g ($(bits 3) x bs) = ... -- Extra parens for the value input feature
|
|
|
|
|
|
### Nesting
|
|
f (%snoc x xs) = ... -- Or use prefix "%" instead
|
|
|
|
|
|
|
|
f (.snoc x xs) = ... -- Or use prefix "." instead
|
|
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
|
|
|
|
|
|
f (snoc | x xs) = .. -- Use "|" instead of "->"
|
|
```wiki
|
|
g (bits 3 | b bs) = ...
|
|
f (sing -> x, True) = ...
|
|
}}}
|
|
g (Just (sing -> x)) = ...
|
|
Another possibility is to use a backward arrow, more like pattern guards:
|
|
h (Just (sing -> Just x)) = ...
|
|
{{{
|
|
```
|
|
f ((x,xs) <- snoc) = ... -- More like pattern guards
|
|
|
|
}}}
|
|
|
|
But that messes up the left-to-right flow that is useful in some cases.
|
|
And by the same token, view patterns nest inside each other:
|
|
For example, compare these:
|
|
|
|
{{{
|
|
```wiki
|
|
parsePacket1 (bits 3 -> n (bits n -> val bs)) = ...
|
|
k :: [[a]] -> a
|
|
|
|
k (sing -> sing -> x) = x
|
|
parsePacket2 (n (val bs <- bits n) <- bits 3) = ...
|
|
```
|
|
}}}
|
|
|
|
|
|
|
|
I also thought about infix view patterns, where the view function
|
|
This convenient nesting is perhaps the biggest practical
|
|
appears between its (pattern) arguments, but I could not think of a
|
|
difference between view patterns and pattern guards.
|
|
nice syntax for it, so it is not provided by this proposal.
|
|
|
|
|
|
|
|
== Remarks ==
|
|
The majority of the proposals allow nesting.
|
|
|
|
|
|
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.
|
|
## More examples
|
|
* 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.
|
|
### Erlang-style parsing
|
|
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 expression to the left of the `->` can mention variables bound in earlier patterns.
|
|
the data representation and exporting view functions instead, which might
|
|
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:
|
|
be an excellent thing.
|
|
|
|
|
|
```wiki
|
|
All this could be done with pattern guards. For example `parsePacket` could be written
|
|
bits :: Int -> ByteString -> Maybe2 Word ByteString
|
|
{{{
|
|
-- (bits n bs) parses n bits from the front of bs, returning
|
|
parsePacket bs | Just (n, bs') <- bits 3 bs
|
|
-- the n-bit Word, and the remainder of bs
|
|
| Just (val, bs'') <- bits n bs'
|
|
```
|
|
= ...
|
|
|
|
}}}
|
|
|
|
Indeed, one might ask whether the extra syntax for view patterns is worth
|
|
Then we could write patterns like this:
|
|
it when they are so close to pattern guards.
|
|
|
|
That's a good question. I'm hoping that support for view patterns
|
|
```wiki
|
|
might encourage people to export view functions (ones with `Maybe`
|
|
parsePacket :: ByteString -> ...
|
|
return types, and encouage their use in patten matching). That is,
|
|
parsePacket (bits 3 -> n (bits n -> val bs)) = ...
|
|
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.
|
|
This parses 3 bits to get the value of `n`, and then parses `n` bits to get
|
|
So matters are not much worse than before.
|
|
the value of `val`.
|
|
|
|
|
|
|
|
### Sets as lists
|
|
-------------------------
|
|
|
|
== Related work ==
|
|
|
|
|
|
Here is a module implementing sets as lists:
|
|
=== Wadler's original paper (POPL 1987) ===
|
|
|
|
|
|
```wiki
|
|
Wadler's paper was the first concrete proposal. It proposed a top-level view
|
|
module Set( Set, empty, insert, delete, has) where
|
|
declaration, together with functions ''in both directions'' between the view type
|
|
|
|
and the original type, which are required to be mutually inverse.
|
|
newtype Set a = S [a]
|
|
This allows view constructors to be used in expressions
|
|
|
|
as well as patterns, which seems cool. Unfortunately this dual role proved
|
|
has :: Eq a => a -> Set a -> Maybe (Set a)
|
|
problematic for equational reasoning, and every subsequent proposal restricted
|
|
has x (S xs) | x `elem` xs = Just (xs \\ x)
|
|
view constructors to appear in patterns only.
|
|
| otherwise = Nothing
|
|
|
|
|
|
=== [http://haskell.org/development/views.html Burton et al views (1996)] ===
|
|
delete :: a -> Set a -> Set a
|
|
|
|
delete x (has x -> s) = s
|
|
This proposal is substantially more complicated than the one above; in particular it
|
|
delete x s = s
|
|
rquires new form of top-level declaration for a view type. For example:
|
|
|
|
{{{
|
|
insert :: a -> Set a -> Set a
|
|
view Backwards a of [a] = [a] `Snoc` a | Nil
|
|
insert x s@(has x -> _) = s
|
|
where
|
|
insert x (S xs) = S (x:xs)
|
|
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.
|
|
|
|
|
|
|
|
=== [http://citeseer.ist.psu.edu/okasaki98view.html 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.
|
|
|
|
|
|
|
|
=== [http://citeseer.ist.psu.edu/erwig96active.html 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.
|
|
|
|
|
|
|
|
=== [http://portal.acm.org/citation.cfm?id=232641&coll=portal&dl=ACM 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.
|
|
|
|
|
|
|
|
=== [http://citeseer.ist.psu.edu/erwig00pattern.html 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).
|
|
|
|
|
|
|
|
=== [http://lambda-the-ultimate.org/node/1960 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 ===
|
|
|
|
|
|
|
|
[http://hackage.haskell.org/trac/haskell-prime/wiki/PatternSynonyms Pattern synonyms]
|
|
|
|
are a requested Haskell Prime feature. John Reppy had the same idea years ago for Standard ML; see
|
|
|
|
[http://people.cs.uchicago.edu/~jhr/papers/1992/tr-sml-const.pdf 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).
|
|
|
|
|
|
|
|
=== [http://citeseer.ist.psu.edu/tullsen00first.html Tullsen: First Class Patterns] ===
|
|
|
|
|
|
|
|
First Class Patterns is an approach that attempts to
|
|
|
|
add the minimum of syntax to the language which---in combination with
|
|
|
|
pattern combinators written within the language---can achieve everything
|
|
|
|
and more that Haskell patterns can do. They have the value-input feature.
|
|
|
|
|
|
|
|
The advantages are 1) They are simpler than Haskell's patterns; 2) Patterns are first class.
|
|
|
|
3) The binding mechanism (the pattern binder) is orthogonal to the the pattern combinators:
|
|
|
|
the hope is that one can stop changing the syntax/semantics of patterns and concentrate on writing the
|
|
|
|
combinators (as Haskell functions).
|
|
|
|
|
|
|
|
The disadvantages are as follows: 1) An extra syntactic construct that binds variables, the pattern binder, is required.
|
|
|
|
2) Even with pattern binders, simple patterns look clunkier than Haskell's patterns.
|
|
|
|
3) No attempt is made to check for exhaustiveness of patterns.
|
|
|
|
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:
|
|
|
|
{{{
|
|
|
|
f = {%sing n} .-> n+1
|
|
|
|
|>> 0
|
|
|
|
|
|
|
|
g = {%sing True} .-> 0
|
|
|
|
.| {%sing False} .-> 1
|
|
|
|
|>> 2
|
|
|
|
}}}
|
|
|
|
=== 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
|
|
|
|
(''something'' `->` ''something'')
|
|
|
|
with a syntax something like
|
|
|
|
(`\` ''pattern'' `->` ''result'').
|
|
|
|
The abstraction includes both the pattern and the result. In contrast, view patterns tackle only the syntax of patterns; the pattern of a first-class abstraction.
|
|
|
|
|
|
|
|
Here are the ones I know of
|
|
|
|
|
|
|
|
* [http://hackage.haskell.org/trac/haskell-prime/ticket/114 Claus Reinke's lambda-match proposal]
|
|
|
|
* [http://ttic.uchicago.edu/~blume/pub-cat.html Matthias Blume: Extensible programming with first-class cases] (ICFP06)
|
|
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
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 ===
|
|
|
|
|
|
|
|
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 [http://www-staff.it.uts.edu.au/~cbj home page] has more info.
|
|
|
|
```
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
#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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
errVal :: Int -> Bool
|
|
|
|
errVal = (== 4)
|
|
|
|
|
|
|
|
f (errVal ->) = ...
|
|
|
|
```
|
|
|
|
|
|
|
|
## Concrete syntax
|
|
|
|
|
|
|
|
|
|
|
|
A disadvantage of the arrow syntax is that it looks a bit confusing
|
|
|
|
when it appears in a case expression:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
last xs = case xs of
|
|
|
|
(snoc -> x xs) -> x
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
(Also that "x xs" looks a bit like `x` applied to `xs`.)
|
|
|
|
|
|
|
|
|
|
|
|
Here are some other possible syntax choices I've considered:
|
|
|
|
|
|
|
|
```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) = .. -- Use "|" instead of "->"
|
|
|
|
g (bits 3 | b bs) = ...
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
Another possibility is to use a backward arrow, more like pattern guards:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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)](http://haskell.org/development/views.html)
|
|
|
|
|
|
|
|
|
|
|
|
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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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](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's proposal for active patterns renders the Set example like this:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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)](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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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](http://citeseer.ist.psu.edu/erwig00pattern.html)
|
|
|
|
|
|
|
|
|
|
|
|
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](http://lambda-the-ultimate.org/node/1960)
|
|
|
|
|
|
|
|
|
|
|
|
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](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
|
|
|
|
[ Abstract value constructors](http://people.cs.uchicago.edu/~jhr/papers/1992/tr-sml-const.pdf),
|
|
|
|
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
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
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).
|
|
|
|
|
|
|
|
### [ Tullsen: First Class Patterns](http://citeseer.ist.psu.edu/tullsen00first.html)
|
|
|
|
|
|
|
|
|
|
|
|
First Class Patterns is an approach that attempts to
|
|
|
|
add the minimum of syntax to the language which---in combination with
|
|
|
|
pattern combinators written within the language---can achieve everything
|
|
|
|
and more that Haskell patterns can do. They have the value-input feature.
|
|
|
|
|
|
|
|
|
|
|
|
The advantages are 1) They are simpler than Haskell's patterns; 2) Patterns are first class.
|
|
|
|
3) The binding mechanism (the pattern binder) is orthogonal to the the pattern combinators:
|
|
|
|
the hope is that one can stop changing the syntax/semantics of patterns and concentrate on writing the
|
|
|
|
combinators (as Haskell functions).
|
|
|
|
|
|
|
|
|
|
|
|
The disadvantages are as follows: 1) An extra syntactic construct that binds variables, the pattern binder, is required.
|
|
|
|
2) Even with pattern binders, simple patterns look clunkier than Haskell's patterns.
|
|
|
|
3) No attempt is made to check for exhaustiveness of patterns.
|
|
|
|
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:
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
f = {%sing n} .-> n+1
|
|
|
|
|>> 0
|
|
|
|
|
|
|
|
g = {%sing True} .-> 0
|
|
|
|
.| {%sing False} .-> 1
|
|
|
|
|>> 2
|
|
|
|
```
|
|
|
|
|
|
|
|
### 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
|
|
|
|
(*something*`->`*something*)
|
|
|
|
with a syntax something like
|
|
|
|
(`\`*pattern*`->`*result*).
|
|
|
|
The abstraction includes both the pattern and the result. In contrast, view patterns tackle only the syntax of patterns; the pattern of a first-class abstraction.
|
|
|
|
|
|
|
|
|
|
|
|
Here are the ones I know of
|
|
|
|
|
|
|
|
- [ Claus Reinke's lambda-match proposal](http://hackage.haskell.org/trac/haskell-prime/ticket/114)
|
|
|
|
- [ Matthias Blume: Extensible programming with first-class cases](http://ttic.uchicago.edu/~blume/pub-cat.html) (ICFP06)
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
```wiki
|
|
|
|
(| Just x -> x+1 ) +++ (| Nothing -> 0 )
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
combines two abstractions, with failure from the first falling through to the seoond.
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
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. |