There have been several questions about lazy patterns recently.
The most recent is this one from Namrata:
Can anyone explain me the need of having irrefutable pattern
matching (the HASKELL style).
Haskell 1.0 on pg. 17 states that
"Operationally, this means that no matching is done on an
irrefutable pattern until one of the variables in the pattern
is used. At that point the entire pattern is matched against
the value, and if the match fails or diverges, so does the
overall computation."
What does the phrase "one of the var. in the pattern is used"
mean ?
The above quoted passage from the Report was intended to give an
operational feel for what's going on, but the problem is that it is
too "temporal". It's probably better to think more declaratively.
Joe Fasel and I recently finished a tutorial on Haskell (whose
availability will be announced shortly). In it I use the following
operational description:
Lazy patterns are {\em irrefutable}: matching a value "v" against
"^pat" always succeeds, regardless of "pat". Operationally speaking,
if an identifier in "pat" is later ``used'' on the right-hand-side, it
will be bound to that portion of the value that would result if "v"
were to successfully match "pat", and _|_ otherwise.
Hopefully this is clearer; see the example below.
Consider for eg,
g x = x + 1
f ^(x,1) = g x
f (2,1)
Here var. x is within an irrefutable pattern (x,1) .
Do I do pattern matching of (2,1) with (x,1) before the call to g is
made (i.e calling g as g 2)
or
do pattern matching of (x,1) with (2,1) when I evaluate the
body of g (i.e, evaluate x+1).
Using the descrition I gave above, here's how I would explain this
example:
1) Because lazy patterns are irrefutable, the call "f (2,1)" matches
the left-hand side "f ^(x,1)", and thus the result is "g x".
2) To determine the value of "g x", first consider the match of (2,1)
with (x,1); this succeeds, binding x to 2. Since "g 2" is 3, this
is the overall result.
In contrast, if the above call were "f (2,2)", here's what would happen:
1) Because lazy patterns are irrefutable, the call "f (2,2)" matches
the LHS "f ^(x,1)", and thus the result is "g x".
2) To determine the value of "g x", first consider the match of (2,2)
with (x,1); this fails, thus binding x to _|_. Since "g _|_" is
also _|_, this is the overall result.
I hope i will get an answer to this question from the gurus of
the field.
I hope this helps.
In another message, Rob Turner writes:
Having just learnt about the use of irrefutable patterns for I/O, I
wish my suspicions about them being a bolted on addition to the
language for pragmatic reasons to be dispelled. Do irrefutable
patterns cause any problems mathematically? Does the ability to reason
(relatively) easily about functional programs disappear when they are
used?
Two important points need to be made here: (1) lazy patterns were
definitely NOT added to Haskell because of I/O, and (2) the original
motivation in fact stemmed from mathematical considerations, and NOT
pragmatic or even stylistic reasons.
Scott King later writes:
Another question: are irrefutable patterns really necessary/good?
IMHO, I can more clearly write my I/O functions without them:
withTildes ^((Str userInput) : ^(Success : _)) =
[ ReadChan stdin,
AppendChan stdout output ]
where
output = someFunction userInput
or, more clearly:
withoutTildes responses =
[ ReadChan stdin,
AppendChan stdout output ]
where
((Str userInput) : resps2) = responses
(Success : _) = resps2
output = someFunction userInput
This is certainly true. Scott goes on to give mostly stylistic
reasons for why the latter might in fact be preferred, but this is of
course subjective. In any case, a couple of points need to be made
here as well:
(1) What do you do about the user who writes the first program above,
but WITHOUT tildes? How do you explain why it doesn't work, and must
be written as in the second program above?
(2) Indeed, how do you explain that the second program works but the
first doesn't? More specifically, why do "pattern bindings" match
lazily, but those in functional argument position don't? In fact,
please note in the Report that pattern bindings are explained IN TERMS
OF lazy patterns! (See Section 3.11 on let expressions.)
Scott goes on to say:
Using ^-patterns for I/O makes it seem as if I/O is special. In fact,
the following two definitions would suffice quite nicely to describe
how the request- and response-lists are related:
requests = mainUserFunction responses
responses = haskellKernel requests
This is nothing but a lexical transliteration of the diagram in the
Report, and doesn't address the issue of lazy patterns.
I wonder if interaction with the system would be easier if a program
could directly use a `haskellKernel' identifier rather than being
restricted to the above relationship.
This would be disastrous, since "haskellKernel" essentially
corresponds to the operating system. Having a "handle" on it means I
could store it in data structures, duplicate it, perhaps even write it
to a file! For a discussion of some of these issues, see reference
[8] in the Report.
Having said all this, I won't say definitively that I am a fan of lazy
patterns. But if we were to get rid of them, we would at a minimum
need a different way to explain pattern bindings, probably not by
direct translation, but rather by a denotational semantics. For a
more detailed discussion of lazy patterns, including some motivating
examples, I've attached below an extract from the tutorial that Joe
and I wrote; I hope this helps.
Cheers,
-Paul
-----------------------------------------------------------------------
\subsection{Lazy Patterns}
\label{tut-lazy-patterns}
There is one other kind of pattern allowed in Haskell. It is called a
{\em lazy pattern}, and has the form \verb|^|$pat$. Lazy patterns are
{\em irrefutable}: matching a value $v$ against \verb|^|$pat$ always
succeeds, regardless of $pat$. Operationally speaking, if an
identifier in $pat$ is later ``used'' on the right-hand-side, it will
be bound to that portion of the value that would result if $v$ were to
successfully match $pat$, and $\bot$ otherwise.
Lazy patterns are useful in contexts where infinite lists are being
defined recursively. For example, infinite lists are an excellent
vehicle for writing {\em simulation} programs, and in this context the
infinite lists are often called {\em streams}. Consider the simple
case of simulating the interactions between a server process @server@
and a client process @client@, where @client@ sends a sequence of {\em
requests} to @server@, and @server@ replies to each request with some
kind of {\em response}. This situation is shown pictorially in Figure
\ref{tut-fib-fig}b, just as we did with the Fibonacci example. (Note
that @client@ also takes an initial message as argument.) Using
streams to simulate the message sequences, the Haskell code
corresponding to this diagram is:
\bprog@
reqs = client init resps
resps = server reqs
@\eprog
These recursive equations are a direct lexical transliteration of the
diagram.
Let us further assume that the structure of the server and client look
something like this:
\bprog@
client init (resp:resps) = init : client (next resp) resps
server (req:reqs) = process req : server reqs
@\eprog
where we assume that @next@ is a function that, given a response from
the server, determines the next request, and @process@ is a function
that processes a request from the client, returning an appropriate
response.
Unfortunately, this program has a serious problem: it will not produce
any output! The problem is that @client@, as used in the recursive
setting of @reqs@ and @resps@, attempts a match on the response list
before it has submitted its first request! In other words, the
pattern matching is being done ``too early.'' One way to fix this is
to redefine @client@ as follows:
\bprog@
client init resps = init : client (next (head resps)) (tail resps)
@\eprog
Although workable, this solution does not read as well as that given
earlier. A better solution is to use a lazy pattern:
\bprog@
client init ^(resp:resps) = init : client (next resp) resps
@\eprog
Because lazy patterns are irrefutable, the match will immediately
succeed, allowing the initial request to be ``submitted,'' in turn
allowing the first response to be generated; the engine is now
``primed,'' and the recursion takes care of the rest.
As an example of this program in action, if we define:
\bprog@
init = 0
next resp = resp
process req = req+1
@\eprog
then we see that:
\[ @take 10 reqs@\ \ \ \ \red\ \ \ \ @[0,1,2,3,4,5,6,7,8,9]@ \]
The server/client example was deliberately chosen to demonstrate a
typical use of lazy patterns and streams, and also to aid the user
interested in using Haskell's {\em stream-based I/O}, in which a
Haskell program is essentially the client, with the operating system
acting as server (\see{io}). Although in this tutorial we will only
discuss {\em continuation-based I/O} (see Section
\ref{tut-io}), the stream-based alternative is an excellent example of
the use of lazy patterns and streams. Indeed, the stream-based I/O
example in the Report uses lazy patterns.
As another example of the use of lazy patterns, consider the
definition of Fibonacci given earlier:
\bprog@
fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]
@\eprog
We might try rewriting this using an as-pattern:
\bprog@
fib@@(1:tfib) = 1 : 1 : [ a+b | (a,b) <- zip fib tfib ]
@\eprog
This version of @fib@ has the (small advantage) of not using @tail@ on
the right-hand side, since it is available in ``destructured'' form on
the left-hand side as @tfib@.
\syn{This kind of equation is called a {\em pattern binding} because
it is a top-level equation in which the entire left-hand side is a
pattern; i.e.\ both @fib@ and @tfib@ become bound within the scope of
the declaration.}
Now, using the same reasoning we did earlier, we should be led to
believe that this program will not generate any output. Curiously,
however, it {\em does}, and the reason is simple: in Haskell,
pattern bindings are assumed to have an implicit @^@ in front of them,
reflecting the most common behavior expected of pattern bindings, and
avoiding some anomalous situations which are beyond the scope of this
tutorial. Thus we see that lazy patterns play an important role in
Haskell, if only implicitly.
