GHC supports an extension of pattern matching called bang
patterns, written !
.
Bang patterns are under consideration for Haskell Prime.
The Haskell
prime feature description contains more discussion and examples
than the material below.
pat
The key change is the addition of a new rule to the
semantics of pattern matching in the Haskell 98 report.
Add new bullet 10, saying: Matching the pattern !
pat
against a value v
behaves as follows:
if v
is bottom, the match diverges
otherwise, pat
is matched against v
Bang patterns are enabled by the flag -XBangPatterns
.
The main idea is to add a single new production to the syntax of patterns:
pat ::= !pat
Matching an expression e
against a pattern !p
is done by first
evaluating e
(to WHNF) and then matching the result against p
.
Example:
f1 !x = True
This definition makes f1
is strict in x
,
whereas without the bang it would be lazy.
Bang patterns can be nested of course:
f2 (!x, y) = [x,y]
Here, f2
is strict in x
but not in
y
.
A bang only really has an effect if it precedes a variable or wild-card pattern:
f3 !(x,y) = [x,y] f4 (x,y) = [x,y]
Here, f3
and f4
are identical;
putting a bang before a pattern that
forces evaluation anyway does nothing.
There is one (apparent) exception to this general rule that a bang only
makes a difference when it precedes a variable or wild-card: a bang at the
top level of a let
or where
binding makes the binding strict, regardless of the pattern.
(We say "apparent" exception because the Right Way to think of it is that the bang
at the top of a binding is not part of the pattern; rather it
is part of the syntax of the binding,
creating a "bang-pattern binding".)
For example:
let ![x,y] = e in b
is a bang-pattern binding. Operationally, it behaves just like a case expression:
case e of [x,y] -> b
Like a case expression, a bang-pattern binding must be non-recursive, and is monomorphic. However, nested bangs in a pattern binding behave uniformly with all other forms of pattern matching. For example
let (!x,[y]) = e in b
is equivalent to this:
let { t = case e of (x,[y]) -> x `seq` (x,y) x = fst t y = snd t } in b
The binding is lazy, but when either x
or y
is
evaluated by b
the entire pattern is matched, including forcing the
evaluation of x
.
Bang patterns work in case
expressions too, of course:
g5 x = let y = f x in body g6 x = case f x of { y -> body } g7 x = case f x of { !y -> body }
The functions g5
and g6
mean exactly the same thing.
But g7
evaluates (f x)
, binds y
to the
result, and then evaluates body
.
We add a single new production to the syntax of patterns:
pat ::= !pat
There is one problem with syntactic ambiguity. Consider:
f !x = 3
Is this a definition of the infix function "(!)
",
or of the "f
" with a bang pattern? GHC resolves this
ambiguity in favour of the latter. If you want to define
(!)
with bang-patterns enabled, you have to do so using
prefix notation:
(!) f x = 3
The semantics of Haskell pattern matching is described in Section 3.17.2 of the Haskell Report. To this description add one extra item 10, saying:
Matching
the pattern !pat
against a value v
behaves as follows:
if v
is bottom, the match diverges
otherwise, pat
is matched against
v
Similarly, in Figure 4 of Section 3.17.3, add a new case (t):
case v of { !pat -> e; _ -> e' } = v `seq` case v of { pat -> e; _ -> e' }
That leaves let expressions, whose translation is given in
Section
3.12
of the Haskell Report.
In the translation box, first apply
the following transformation: for each pattern pi
that is of
form !qi = ei
, transform it to (xi,!qi) = ((),ei)
, and and replace e0
by (xi `seq` e0)
. Then, when none of the left-hand-side patterns
have a bang at the top, apply the rules in the existing box.
The effect of the let rule is to force complete matching of the pattern
qi
before evaluation of the body is begun. The bang is
retained in the translated form in case qi
is a variable,
thus:
let !y = f x in b
The let-binding can be recursive. However, it is much more common for
the let-binding to be non-recursive, in which case the following law holds:
(let !p = rhs in body)
is equivalent to
(case rhs of !p -> body)
A pattern with a bang at the outermost level is not allowed at the top level of a module.