%**<title>A Gentle Introduction to Haskell: Patterns</title>
%**~header

\section{Case Expressions and Pattern Matching}
\label{tut-pattern-matching}

Earlier we gave several examples of pattern matching in defining
functions---for example \mbox{\tt length} and \mbox{\tt fringe}.  In this section we
will look at the pattern-matching process in greater detail
(\see{pattern-matching}).\footnote{Pattern matching in Haskell is 
different from that found in logic programming languages such as
Prolog; in particular, it can be viewed as ``one-way'' matching,
whereas Prolog allows ``two-way'' matching (via unification), along
with implicit backtracking in its evaluation mechanism.}

Patterns are not ``first-class;'' there is only a fixed set of
different kinds of patterns.  We have already seen several examples of
{\em data constructor} patterns; both \mbox{\tt length} and \mbox{\tt fringe} defined
earlier use such patterns, the former on the constructors of a
``built-in'' type (lists), the latter on a user-defined type (\mbox{\tt Tree}).
Indeed, matching is permitted using the constructors of any type,
user-defined or not.  This includes tuples, strings, numbers,
characters, etc.  For example, here's a contrived function that
matches against a tuple of ``constants:''
\bprog
\mbox{\tt contrived\ ::\ ([a],\ Char,\ (Int,\ Float),\ String,\ Bool)\ ->\ Bool}\\
\mbox{\tt contrived\ \ \ \ ([],\ \ 'b',\ \ (1,\ \ \ 2.0),\ \ \ "hi",\ \ \ True)\ =\ False}
\eprog 
This example also demonstrates that {\em nesting} of patterns is
permitted (to arbitrary depth).

Technically speaking, {\em formal parameters}\footnote{The Report
calls these {\em variables}.} are also patterns---it's just that they
{\em never fail to match a value}.  As a ``side effect'' of the
successful match, the formal parameter is bound to the value it is
being matched against.  For this reason patterns in any one equation
are not allowed to have more than one occurrence of the same formal
parameter (a property called {\em linearity} \see{pattern-matching},
\see{lambda-abstractions}, \see{function-bindings}).

Patterns such as formal parameters that never fail to match are said
to be {\em irrefutable}, in contrast to {\em refutable} patterns which
may fail to match.  The pattern used
in the \mbox{\tt contrived} example above is refutable.  There are three
other kinds of irrefutable patterns, two of which we will introduce
now (the other we will delay until Section \ref{tut-lazy-patterns}).

\paragraph*{As-patterns.} Sometimes it is convenient to name a
pattern for use on the right-hand side of an equation.  For example, a
function that duplicates the first element in a list might be written
as: 
\bprog
\mbox{\tt f\ (x:xs)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ x:x:xs}
\eprog 
(Recall that ``\mbox{\tt :}'' associates to the right.)  Note that \mbox{\tt x:xs} appears
both as a pattern on the left-hand side, and an expression on the
right-hand side.  To improve readability, we might prefer to write
\mbox{\tt x:xs} just once, which we can achieve using an {\em as-pattern} as
follows:\footnote{Another advantage to doing this is that a naive
implementation might completely reconstruct \mbox{\tt x:xs} rather than
re-use the value being matched against.}
\bprog
\mbox{\tt f\ s@(x:xs)\ \ \ \ \ \ \ \ \ \ \ \ \ =\ x:s}
\eprog 
Technically speaking, as-patterns always result in a successful match,
although the sub-pattern (in this case \mbox{\tt x:xs}) could, of course, fail.

\paragraph*{Wild-cards.} Another common situation is matching against
a value we really care nothing about.  For example, the functions
\mbox{\tt head} and \mbox{\tt tail} defined in Section \ref{tut-polymorphism}
can be rewritten as:
\bprog
\mbox{\tt head\ (x:{\char'137})\ \ \ \ \ \ \ \ \ \ \ \ \ =\ x}\\
\mbox{\tt tail\ ({\char'137}:xs)\ \ \ \ \ \ \ \ \ \ \ \ =\ xs}
\eprog 
in which we have ``advertised'' the fact that we don't care what a
certain part of the input is.  Each wild-card independently matches
anything, but in contrast to a formal parameter, each binds
nothing; for this reason more than one is allowed in an equation.



\subsection{Pattern-Matching Semantics}
\label{tut-matching-semantics}

So far we have discussed how individual patterns are matched, how some
are refutable, some are irrefutable, etc.  But what drives the overall
process?  In what order are the matches attempted?  What if none
succeeds?  This section addresses these questions.

Pattern matching can either {\em fail}, {\em succeed}  or {\em
diverge}.  A successful match binds the formal parameters in the
pattern.  Divergence occurs when a value needed by the pattern
contains an error ($\bot$).  The matching process itself occurs ``top-down,
left-to-right.''  Failure of a pattern anywhere in one equation
results in failure of the whole equation, and the next equation is
then tried.  If all equations fail, the value of the function
application is $\bot$, and results in a run-time error.

For example, if \mbox{\tt [1,2]} is matched against \mbox{\tt [0,bot]}, then \mbox{\tt 1} fails
to match \mbox{\tt 0}, so the result is a failed match.  (Recall that \mbox{\tt bot},
defined earlier, is a variable bound to $\bot$.)  But if \mbox{\tt [1,2]} is
matched against \mbox{\tt [bot,0]}, then matching \mbox{\tt 1} against \mbox{\tt bot} causes
divergence (i.e.~$\bot$).

The other twist to this set of rules is that top-level patterns
may also have a boolean {\em guard}, as in this definition of a
function that forms an abstract version of a number's sign:
\bprog
\mbox{\tt sign\ x\ |\ \ x\ >\ \ 0\ \ \ \ \ \ \ \ =\ \ \ 1}\\
\mbox{\tt \ \ \ \ \ \ \ |\ \ x\ ==\ 0\ \ \ \ \ \ \ \ =\ \ \ 0}\\
\mbox{\tt \ \ \ \ \ \ \ |\ \ x\ <\ \ 0\ \ \ \ \ \ \ \ =\ \ -1}
\eprog 
Note that a sequence of guards may be provided for the same pattern;
as with patterns, they are evaluated top-down, and the first that
evaluates to \mbox{\tt True} results in a successful match.

\subsection{An Example}

The pattern-matching rules can have subtle effects on the meaning of
functions.  For example, consider this definition of \mbox{\tt take}:
\bprog
\mbox{\tt take\ \ 0\ \ \ \ \ {\char'137}\ \ \ \ \ \ \ \ \ \ \ =\ \ []}\\
\mbox{\tt take\ \ {\char'137}\ \ \ \ \ []\ \ \ \ \ \ \ \ \ \ =\ \ []}\\
\mbox{\tt take\ \ n\ \ \ \ \ (x:xs)\ \ \ \ \ \ =\ \ x\ :\ take\ (n-1)\ xs}
\eprog 
and this slightly different version (the first 2 equations have been
reversed):
\bprog
\mbox{\tt take1\ \ {\char'137}\ \ \ \ \ []\ \ \ \ \ \ \ \ \ =\ \ []}\\
\mbox{\tt take1\ \ 0\ \ \ \ \ {\char'137}\ \ \ \ \ \ \ \ \ \ =\ \ []}\\
\mbox{\tt take1\ \ n\ \ \ \ (x:xs)\ \ \ \ \ \ =\ \ x\ :\ take1\ (n-1)\ xs}
\eprog 
Now note the following:
\[\ba{lcl}
  \mbox{\tt take\ \ 0\ bot}  &\ \ \ \red\ \ \ & \mbox{\tt []} \\
  \mbox{\tt take1\ 0\ bot}  &\ \ \ \red\ \ \ & \bot \\[.1in]
  \mbox{\tt take\ \ bot\ []} &\ \ \ \red\ \ \ & \bot \\
  \mbox{\tt take1\ bot\ []} &\ \ \ \red\ \ \ & \mbox{\tt []}
\ea\]
We see that \mbox{\tt take} is ``more defined'' with respect to its second
argument, whereas \mbox{\tt take1} is more defined with respect to its first.
It is difficult to say in this case which definition is better.  Just
remember that in certain applications, it may make a difference.  (The
Standard Prelude includes a definition corresponding to \mbox{\tt take}.)

\subsection{Case Expressions}
\label{tut-case}

Pattern matching provides a way to ``dispatch control'' based on
structural properties of a value.  In many circumstances we
don't wish to define a {\em function} every time we need to do this,
but so far we have only shown how to do pattern matching in function
definitions.  Haskell's {\em case expression} provides a way to solve
this problem.  Indeed, the meaning of pattern matching in function
definitions is specified in the Report in terms of case expressions,
which are considered more primitive.  In particular, a function
definition of the form:
\[\ba{l}
\mbox{$\it \makebox{\tt f}\ p_{11}\ \ldots \ p_{1k}\ \makebox{\tt =}\ e_{1}$} \\
\mbox{$\it \ldots $} \\
\mbox{$\it \makebox{\tt f}\ p_{n1}\ \ldots \ p_{nk}\ \makebox{\tt =}\ e_{n}$}
\ea\]
where each \mbox{$\it p_{ij}$} is a pattern, is semantically equivalent to:
\[ \mbox{$\it \makebox{\tt f\ x1\ x2}\ \ldots \ \makebox{\tt xk\ =\ case\ (x1,\ }\ldots \makebox{\tt ,\ xk)\ of}$}
   \ba[t]{l}
   \mbox{$\it \makebox{\tt (}p_{11},\ \ldots ,\ p_{1k}\makebox{\tt )\ ->}\ e_{1}$} \\
   \mbox{$\it \ldots $} \\
   \mbox{$\it \makebox{\tt (}p_{n1},\ \ldots ,\ p_{nk}\makebox{\tt )\ ->}\ e_{n}$}
   \ea
\]
where the \mbox{\tt xi} are new identifiers.  (For a more general translation
that includes guards, see \see{function-bindings}.)  For example, the
definition of \mbox{\tt take} given earlier is equivalent to:
\bprog
\mbox{\tt take\ m\ ys\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ case\ (m,ys)\ of}\\
\mbox{\tt \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (0,{\char'137})\ \ \ \ \ \ \ ->\ \ []}\\
\mbox{\tt \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ({\char'137},[])\ \ \ \ \ \ ->\ \ []}\\
\mbox{\tt \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (n,x:xs)\ \ \ \ ->\ \ x\ :\ take\ (n-1)\ xs}
\eprog 

A point not made earlier is that, for type correctness, the types of
the right-hand sides of a case expression or set of equations
comprising a function definition must all be the same; more precisely,
they must all share a common principal type.

The pattern-matching rules for case expressions are the same as we
have given for function definitions, so there is really nothing new to
learn here, other than to note the convenience that case expressions
offer.  Indeed, there's one use of a case expression that is so common
that it has special syntax: the {\em conditional expression}.  In
Haskell, conditional expressions have the familiar form:
\[ \mbox{\tt if}\ e_1\ \mbox{\tt then}\ e_2\ \mbox{\tt else}\ e_3 \]
which is really short-hand for:
\[\ba{ll}
\mbox{\tt case}\ e_1\ \mbox{\tt of} & \mbox{\tt True\ \ ->}\ e_2\\
                  & \mbox{\tt False\ ->}\ e_3
\ea\]
{}From this expansion it should be clear that $e_1$ must have type
\mbox{\tt Bool}, and $e_2$ and $e_3$ must have the same (but otherwise
arbitrary) type.  In other words, \mbox{\tt if}-\mbox{\tt then}-\mbox{\tt else} when viewed
as a function has type \mbox{\tt Bool->a->a->a}.

\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 \mbox{\tt {\char'176}}$pat$.  Lazy patterns are
{\em irrefutable}: matching a value $v$ against \mbox{\tt {\char'176}}$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 data structures 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 \mbox{\tt server}
and a client process \mbox{\tt client}, where \mbox{\tt client} sends a sequence of {\em
requests} to \mbox{\tt server}, and \mbox{\tt server} replies to each request with some
kind of {\em response}.  This situation is shown pictorially in Figure
\ref{tut-client-fig}.  (Note that \mbox{\tt client} also takes an initial message as
argument.)
%**<div align=center><img src=\mbox{$\it fig2.gif$} alt=\mbox{$\it Client\ Server\ Example$}> 
%**<h4>Figure 2</h4> </div>
Using
streams to simulate the message sequences, the Haskell code
corresponding to this diagram is:
\bprog
\mbox{\tt reqs\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ client\ init\ resps}\\
\mbox{\tt resps\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ server\ reqs}
\eprog 
These recursive equations are a direct lexical transliteration of the
diagram.

%*ignore
\begin{figure}
\begin{center}
\mbox{
\epsfbox{fig2.eps}}
\end{center}
\caption{Client-Server Simulation}
\label{tut-client-fig}
\end{figure}
%*endignore
Let us further assume that the structure of the server and client look
something like this:
\bprog
\mbox{\tt client\ init\ (resp:resps)\ =\ init\ :\ client\ (next\ resp)\ resps}\\
\mbox{\tt server\ \ \ \ \ \ (req:reqs)\ \ \ =\ process\ req\ :\ server\ reqs}
\eprog 
where we assume that \mbox{\tt next} is a function that, given a response from
the server, determines the next request, and \mbox{\tt 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 \mbox{\tt client}, as used in the recursive
setting of \mbox{\tt reqs} and \mbox{\tt 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 \mbox{\tt client} as follows:
\bprog
\mbox{\tt 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
\mbox{\tt client\ init\ {\char'176}(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
\mbox{\tt init\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ 0}\\
\mbox{\tt next\ resp\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\ resp}\\
\mbox{\tt process\ req\ \ \ \ \ \ \ \ \ \ \ \ \ =\ req+1}
\eprog 
then we see that:
\[ \mbox{\tt take\ 10\ reqs}\ \ \ \ \red\ \ \ \ \mbox{\tt [0,1,2,3,4,5,6,7,8,9]} \]

As another example of the use of lazy patterns, consider the
definition of Fibonacci given earlier:
\bprog
\mbox{\tt fib\ \ \ \ \ \ \ \ \ \ \ \ \ =\ 1\ :\ 1\ :\ [\ a+b\ |\ (a,b)\ <-\ zip\ fib\ (tail\ fib)\ ]}
\eprog 
We might try rewriting this using an as-pattern:
\bprog
\mbox{\tt fib@(1:tfib)\ \ \ \ =\ 1\ :\ 1\ :\ [\ a+b\ |\ (a,b)\ <-\ zip\ fib\ tfib\ ]}
\eprog 
This version of \mbox{\tt fib} has the (small) advantage of not using \mbox{\tt tail} on
the right-hand side, since it is available in ``destructured'' form on
the left-hand side as \mbox{\tt 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 \mbox{\tt fib} and \mbox{\tt tfib} become bound within the scope of
the declaration.}

Now, using the same reasoning as 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 \mbox{\tt {\char'176}} 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.

\subsection{Lexical Scoping and Nested Forms}
\label{tut-nesting}

It is often desirable to create a nested scope within an expression,
for the purpose of creating local bindings not seen elsewhere---i.e.
some kind of ``block-structuring'' form.  In Haskell there are two ways
to achieve this:

\paragraph*{Let Expressions.} Haskell's {\em let expressions} are
useful whenever a nested set of bindings is required.  As a simple
example, consider:
\bprog
\mbox{\tt let\ y\ \ \ =\ a*b}\\
\mbox{\tt \ \ \ \ f\ x\ =\ (x+y)/y}\\
\mbox{\tt in\ f\ c\ +\ f\ d}
\eprog 
The set of bindings created by a \mbox{\tt let} expression is {\em mutually
recursive}, and pattern bindings are treated as lazy patterns (i.e.
they carry an implicit \mbox{\tt {\char'176}}).  The only kind of declarations permitted
are {\em type signatures}, {\em function bindings}, and {\em pattern
bindings}.

\paragraph*{Where Clauses.} Sometimes it is convenient to scope
bindings over several guarded equations, which requires a {\em where
clause}:
\bprog
\mbox{\tt f\ x\ y\ \ |\ \ y>z\ \ \ \ \ \ \ \ \ \ \ =\ \ ...}\\
\mbox{\tt \ \ \ \ \ \ \ |\ \ y==z\ \ \ \ \ \ \ \ \ \ =\ \ ...}\\
\mbox{\tt \ \ \ \ \ \ \ |\ \ y<z\ \ \ \ \ \ \ \ \ \ \ =\ \ ...}\\
\mbox{\tt \ \ \ \ \ where\ z\ =\ x*x}
\eprog 
Note that this cannot be done with a \mbox{\tt let} expression, which only
scopes over the expression which it encloses.  A \mbox{\tt where} clause is
only allowed at the top level of a set of equations or case
expression.  The same properties and constraints on bindings in \mbox{\tt let}
expressions apply to those in \mbox{\tt where} clauses.

These two forms of nested scope seem very similar, but remember that a
\mbox{\tt let} expression is an {\em expression}, whereas a \mbox{\tt where} clause is
not---it is part of the syntax of function declarations and case
expressions.

\subsection{Layout}
\label{tut-layout}

The reader may have been wondering how it is that Haskell programs
avoid the use of semicolons, or some other kind of terminator, to
mark the end of equations, declarations, etc.  For example, consider
this \mbox{\tt let} expression from the last section:
\bprog
\mbox{\tt let\ y\ \ \ =\ a*b}\\
\mbox{\tt \ \ \ \ f\ x\ =\ (x+y)/y}\\
\mbox{\tt in\ f\ c\ +\ f\ d}
\eprog
How does the parser know not to parse this as:
\bprog
\mbox{\tt let\ y\ \ \ =\ a*b\ f}\\
\mbox{\tt \ \ \ \ x\ \ \ =\ (x+y)/y}\\
\mbox{\tt in\ f\ c\ +\ f\ d}
\eprog
?

The answer is that Haskell uses a two-dimensional syntax called {\em
layout} that essentially relies on declarations being ``lined up in
columns.''  In the above example, note that \mbox{\tt y} and \mbox{\tt f} begin in the
same column.  The rules for layout are spelled out in detail in the
Report (\see{lexemes-layout}, \see{layout}), but in practice, use of
layout is rather intuitive.  Just remember two things:

First, the next character following any of the keywords \mbox{\tt where},
\mbox{\tt let}, or \mbox{\tt of} is what determines the starting column for the
declarations in the where, let, or case expression being written (the
rule also applies to \mbox{\tt where} used in the class and instance
declarations to be introduced in Section \ref{tut-type-classes}).  Thus
we can begin the declarations on the same line as the keyword, the
next line, etc.  (The \mbox{\tt do} keyword, to be discussed later, also uses layout).

Second, just be sure that the starting column is further to the right
than the starting column associated with the immediately surrounding
clause (otherwise it would be ambiguous).  The ``termination'' of a
declaration happens when something appears at or to the left of the
starting column associated with that binding form.\footnote{Haskell
observes the convention that tabs count as 8 blanks; thus care must be
taken when using an editor which may observe some other convention.}

Layout is actually shorthand for an {\em explicit} grouping mechanism,
which deserves mention because it can be useful under certain
circumstances.  The \mbox{\tt let} example above is equivalent to:
\bprog
\mbox{\tt let\ {\char'173}\ y\ \ \ =\ a*b}\\
\mbox{\tt \ \ \ \ ;\ f\ x\ =\ (x+y)/y}\\
\mbox{\tt \ \ \ \ {\char'175}}\\
\mbox{\tt in\ f\ c\ +\ f\ d}
\eprog
Note the explicit curly braces and semicolons.  One way in which this
explicit notation is useful is when more than one declaration is
desired on a line; for example, this is a valid expression:
\bprog
\mbox{\tt let\ y\ \ \ =\ a*b;\ \ z\ =\ a/b}\\
\mbox{\tt \ \ \ \ f\ x\ =\ (x+y)/z}\\
\mbox{\tt in\ f\ c\ +\ f\ d}
\eprog 
For another example of the expansion of layout into explicit
delimiters, see \see{lexemes-layout}.

The use of layout greatly reduces the syntactic clutter associated
with declaration lists, thus enhancing readability.  It is easy to
learn, and its use is encouraged.

%**~footer