Alternative view patterns: lightweight views for Haskell
This is a copy of the ViewPatterns page, but with a different syntax.
Basic view patterns
View patterns are a convenient way of pattern-matching against values of abstract types. For example, in a programming language implementation, we might represent the syntax of the types of the language as follows:
type Typ
data TypView = Unit
| Arrow Typ Typ
view :: Typ -> TypView
-- additional operations for constructing Typ's ...
The representation of Typ
is held abstract, permitting implementations to use a fancy representation (e.g., hash-consing to manage sharing).
In current Haskell, using this signature is a little inconvenient:
size :: Typ -> Integer
size t = case view t of
Unit -> 1
Arrow t1 t2 -> size t1 + size t2
It is necessary to iterate the case, rather than using an equational function definition. And the situation is even worse when the matching against t
is buried deep inside another pattern.
In response, programmers sometimes eschew type abstraction in favor of revealing a concrete datatype that is easy to pattern-match against.
View patterns permit calling the view function inside the pattern and matching against the result:
size (x | Unit <- view x) = 1
size (x | Arrow t1 t2 <- view x) = size t1 + size t2
That is, we add a new form of pattern, written
pattern | qual1 , ..., qualn
This has the same meaning as pattern guard at the top level, but here they are allowed to be part of a pattern, and thus nested inside other patterns.
So first the pattern is matched, then the qualifiers are matched in order. An expression qualifier has to evaluate to True
, and for a pat <-
exp the pattern must match the expression.
The key feature of this proposal is its modesty, rather than its ambition:
- There is no new form of declaration (e.g. 'view' or 'pattern synonym').
- No new syntax, the existing pattern guard syntax is simply generalized to be allowed inside patterns.
- No changes are needed to import or export mechanisms.
- Both static and dynamic semantics are extremely simple.
It is essentially some simple syntactic sugar for patterns. However, sometimes modest syntactic sugar can have profound consequences. In this case, it's possible that people would start routinely hiding the data representation and exporting view functions instead, which would be an excellent thing.
Semantics
Scoping for pat |
quals:
-
The variables bound by the view pattern are the variables bound by pat and quals.
-
Variables bound by patterns to the left of a view pattern expression are in scope. For example:
-
In function definitions, variables bound by matching earlier curried arguments may be used in view pattern expressions in later arguments.
example :: (String -> Integer) -> String -> Bool example f (x | f x == 4) = True
-
Variables can be bound to the left in tuples and data constructors:
example :: ((String -> Integer,Integer), String) -> Bool example ((f,_), x | f x == 4) = True
-
There is no way to localise how many variables are brought into scope. For example, consider
f (x | x>=k, let y = x-k) = rhs
Here, both x
and y
are in scope in rhs
; and there is no way to say "only bind y
in this pattern".
Typing
If pat |
quals has same type as pat, and the "quals" must be well typed in the same way as for pattern guards.
Evaluation
To match a value v against a pattern (pat |
quals), match "v" against pat and then match the quals.
Examples
We discuss some examples of pattern-matching abstract types and of other uses of view patterns here.
Join lists
The requisite join-list example:
data JList a = Empty
| Single a
| Join (JList a) (JList a)
data JListView a = Nil
| Cons a (JList a)
Here we've chosen that the view type only exposes the cons/nil structure one level at a time: the second argument to Cons
is a join-list, not a view of it---but that's of course up to the programmer.
The implementation of the view:
view :: JList a -> JListView a
view Empty = Nil
view (Single a) = Cons a Empty
view (Join (l | Cons xh xt <- view l) y) = Cons xh $ Join xt y
view (Join (l | Nil <- view l) y) = view y
Note the recursive uses of the view function in view patterns within its own definition.
An example of using it:
length :: JList a -> Integer
length (l | Nil <- view l) = 0
length (l | Cons x xs <- view l) = 1 + length xs
For more general sequences, Data.Sequence
already defines the views from the left and from the right
data ViewL a
= EmptyL
| (:<) a (Seq a)
viewl :: Seq a -> ViewL a
data ViewR a
= EmptyR
| (:>) (Seq a) a
viewr :: Seq a -> ViewR a
that now may be used in view patterns.
Partial views
Here's an alternate style of view definition: rather than mapping the abstract type to a single sum type, you provide outjections optionally inverting each constructor:
type Typ
outUnit : Typ -> Maybe ()
outArrow : Typ -> Maybe (Typ, Typ)
-- additional operations for constructing Typ's ...
This view is used as follows:
size (t | Just _ <- outUnit t) = 1
size (t | Just (t1, t2) <- outArrow t) = size t1 + size t2
This style should be discouraged when the view is in fact a total operation, as it moves the documentation of this fact out of the type system, making it harder for both people and the compiler to check exhaustiveness. However, it may be a useful idiom for defining a partial matching function with several constructors (e.g., in XML processing).
Sets
Here is a small module that allows to decompose sets with respect to a given element, deleting it hereby.
module Set(Set, empty, insert, delete, has) where
newtype Set a = S [a]
has :: Eq a => a -> Set a -> Maybe (Set a)
has x (S xs) | x `elem` xs = Just (xs \\ x)
| otherwise = Nothing
delete :: a -> Set a -> Set a
delete x (r | Just s <- has x r) = s
delete x s = s
insert :: a -> Set a -> Set a
insert x (s | Just _ <- has x s) = s
insert x (S xs) = S (x:xs)
Note the use of the previous argument x
in later view patterns.
Erlang-style parsing
Sagonas et al describe an extension to Erlang that supports pattern-matching on bit-strings ("Application, implementation and performance evaluation of bit-stream programming in Erlang", PADL'07). Suppose we had a parsing function thus:
bits :: Int -> ByteString -> Maybe (Word, ByteString)
-- (bits n bs) parses n bits from the front of bs, returning
-- the n-bit Word, and the remainder of bs
Then we could write patterns like this:
parsePacket :: ByteString -> ...
parsePacket (p1 | Just (n, (p2 | Just (val, bs) <- bits n p2)) <- bits 3 p1) = ...
This parses 3 bits to get the value of n
, and then parses n
bits to get the value of val
. Note that this example uses the left-to-right scoping in the inner tuple: the first component is used in the view expression in the second.
Note that this example could also be written without nesting as follows (suggested by AntC2):
parsePacket :: ByteString -> ...
parsePacket (p1 | Just (n, p2) <- bits 3 p1, Just (val, bs) <- bits n p2) = ...
N+k patterns
(n+k)
patterns use the following view function:
np :: Num a => a -> a -> Maybe a
np k n | k <= n = Just (n-k)
| otherwise = Nothing
They are used as follows:
fib :: Num a -> a -> a
fib 0 = 1
fib 1 = 1
fib (n2 | Just n <- np 2 n2) = fib (n + 1) + fib n
Note the integration with type classes: the view function can be overloaded, and its use in a view pattern gives rise to a type-class constraint (in this case, that in turn makes fib
overloaded).
Alternatively it can be written without an auxiliary function
fib :: Num a -> a -> a
fib 0 = 1
fib 1 = 1
fib (n2 | let n = n2-2, n >= 0) = fib (n + 1) + fib n
n+k
patterns are another a good opportunity for passing view data at run-time, as in:
example k (m | m > k) = ...
Named constants
View patterns can be used to pattern match against named constants:
errorVal :: Int -> Bool
errorVal = (== 4)
f (x | errorVal x) = ...
Both patterns
A "both pattern" pat1 & pat2
matches a value against both pat1
and pat2
and succeeds only when they both succeed. A special case is as-patterns, x@p
, where the first pattern is a variable. Both patterns can be programmed using view patterns:
And used as follows:
f (x | xs <- x, h : t <- x) = h : (xs ++ t)
Comparison with existing view patterns
There are straightforward translations between old and new style view patterns:
pat <-
exp
translates to
x |
pat <-
exp x
where x is a fresh variable.
And in the other direction
pat |
quals
translates to
Just
vs <- let
f pat |
quals = Just
vs;
f _ = Nothing in
f
where vs are all the variables bound in pat and quals and f is fresh.
Notable differences:
- The new style is a straightforward extension of existing syntax (pattern guards).
- The new style allows more powerful matching without introducing an auxiliary type (typically a
Maybe
). This leads to a more straightforward translation of pattern matching and better efficiency without sophisticated transformations. - The new style often has to introduce an extra variable to match the entire expression; a variable that is not needed on the right hand side. This small pollution of the namespace can be avoided if the PatternSynonyms proposal is also implemented.