A new view of guards
                ~~~~~~~~~~~~~~~~~~~~
                Simon Peyton Jones, April 1997

This note proposes an extension to the guards that form part of function
definitions in Haskell.  The increased expressive power is known (by me
anyway!) to be useful.  The general aim is similar to that of views [1,2],
but the expressive power of this proposal is a little different, in places
more expressive than views, and in places less so.  The proposal can be
implemented with very modest syntactic and implementation cost.  It is
upward compatible with Haskell; all existing programs will continue to work.

I'd welcome feedback and improvements to this proposal.


What's the problem?
~~~~~~~~~~~~~~~~~~~
Consider the following Haskell function definition

        filter p []                 = []
        filter p (y:ys) | p y       = y : filter p ys
                        | otherwise = filter p ys

The decision of which right-hand side to choose is made in
two stages: first, pattern matching selects a guarded group,
and second, the boolean-valued guards select among the right-hand
sides of the group.  In these two stages, only the pattern-matching
stage can bind variables.  A guard is simply a boolean valued expression.

So pattern-matching combines selection with binding, whereas guards simply
perform selection.  Sometimes this is a tremendous nuisance.  For example,
suppose we have an abstract data type of finite maps, with a lookup
operation:

        lookup :: FinteMap -> Int -> Maybe Int

The lookup returns Nothing if the supplied key is not in the
domain of the mapping, and (Just v) otherwise, where v is
the value that the key maps to.  Now consider the following
definition:

   clunky env var1 var2 | ok1 && ok2 = val1 + val2
                        | otherwise  = var1 + var2
                        where
                          m1 = lookup env var1
                          m2 = lookup env var2
                          ok1 = maybeToBool m1
                          ok2 = maybeToBool m2
                          val1 = expectJust m1
                          val2 = expectJust m2

The auxiliary functions are
        maybeToBool :: Maybe a -> Bool  
        maybeToBool (Just x) = True
        maybeToBool Nothing  = False

        expectJust :: Maybe a -> a
        expectJust (Just x) = x
        expectJust Nothing  = error "Unexpected Nothing"

What is "clunky" doing?  The guard "ok1 && ok2" checks that both
lookups succeed, using maybeToBool to convert the maybe types to
booleans.  The (lazily evaluated) expectJust calls extract the values
from the results of the lookups, and binds the returned values to
val1 and val2 respectively.  If either lookup fails, then clunky
takes the "otherwise" case and returns the sum of its arguments.

This is certainly legal Haskell, but it is a tremendously verbose
and un-obvious way to achieve the desired effect.  Arguably, a more
direct way to write "clunky" would be to use case expressions:

  clunky env var1 var1 = case lookup env var1 of
                           Nothing -> fail
                           Just val1 -> case lookup env var2 of
                                          Nothing -> fail
                                          Just val2 -> val1 + val2
                         where
                          fail = val1 + val2

This is a bit shorter, but hardly better.  Of course, we can rewrite
any set of pattern-matching, guarded equations as case expressions;
that is precisely what the compiler does when compiling equations!
The reason that Haskell provides guarded equations is because they
allow us to write down the cases we want to consider, one at a time,
independently of each other.  This structure is hidden in the case 
version.  Two of the right-hand sides are really the same ("fail"),
and the whole expression tends to become more and more indented.  

Worse, if this was just one equation of "clunky", with others that
follow, then the thing wouldn't work at all.  That is, suppose we have

  clunky' env (var1:var2:vars) | ok1 && ok2 = val1 + val2
                               where
                                m1 = lookup env var1
                                ...as before...

  clunky' env [var1]           = ...some stuff...
  clunky' env []               = ...more stuff...

Now, if either the lookups fail we want to fall through to the second
and third equations for clunky'.  If we write the definition in the 
form of a case expression we are forced to make the latter two
equations for clunky' into a separate definition and call it in
the right hand side of "fail".  Ugh.  Ugh.  Ugh.  This is precisely
why Haskell provides guards at all, rather than relying on if-then-else
expressions: if the guard fails we fall through to the next equation,
whereas we can't do that with a conditional.


What is frustrating about this is that the solution is so tantalisingly
near at hand!  What we want to do is to pattern-match on the result of 
the lookup.  We can do it like this:

  clunky' env vars@(var1:var2:vars) 
    = clunky_help (lookup env var1) (lookup env var2) vars
    where
      clunky_help (Just val1) (Just val2) vars = val1 + val2
      clunky_help _           _           [var1] = ...some stuff...
      clunky_help _           _           []     = ...more stuff...

Now we do get three equations, one for each right-hand side, but
it is still clunky.  In a big set of equations it becomes hard to
remember what each "Just" pattern corresponds to.  Worse, we can't
use one lookup in the next.  For example, suppose our function was 
like this:

  clunky'' env var1 var2 | ok1 && ok2 = val2
                         | otherwise  = var1 + var2
                         where
                          m1 = lookup env var1
                          m2 = lookup env (var2 + val1)
                          ok1 = maybeToBool m1
                          ok2 = maybeToBool m2
                          val1 = expectJust m1
                          val2 = expectJust m2

Notice that the second lookup uses val1, the result of the first lookup.
To express this with a clunky_help function requires a second helper
function nested inside the first.  Dire stuff.

So the original definition, using maybeToBool and expectJust has the
merit that it scales nicely, to accommodate both multiple equations
and successive lookups.  Yet it stinks.


A proposal
~~~~~~~~~~~
The proposal I want to make is simple:

        Instead of being a boolean expression,
        a guard is a list of qualifiers,
        exactly as in a list comprehension.

        That is, the only syntax change is to replace 
        "exp" by "quals" in the syntax of guarded equations. 

Here is how I would write clunky:

  clunky env var1 var1 | Just val1 <- lookup env var1,
                         Just val2 <- lookup env var2
                       = val1 + val2
  ...other equations for clunky...

The semantics should be clear enough.  The qualifers are matched in
order.  For a "<-" qualifier, which I call a "pattern guard", the
right hand side is evaluated and matched against the pattern on the
left.  If the match fails then the whole guard fails and the next
equation is tried.  If it succeeds, then the appropriate binding takes
place, and the next qualifier is matched, in the augmented
environment.  Unlike list comprehensions, however, the type of the
expression to the right of the "<-" is the same as the type of the
pattern to its left.  The bindings introduced by pattern guards scope
over all the remaining guard qualifiers, and over the right hand side
of the equation.

Just as with list comprehensions, boolean expressions can be freely mixed
with among the pattern guards.  For example:

        f x | [y] <- x,
              y > 3,
              Just z <- h y
            = ...

Haskell's current guards therefore emerge as a special case, in which the
qualifier list has just one element, a boolean expression.

Just as with list comprehensions, a "let" qualifier can introduce a binding.
It is also possible to do this with pattern guard with a simple
variable pattern
                        a <- <expression>
However a "let" qualifier is a little more powerful, because it can 
introduce a recursive or mutually-recursive binding.  It is not clear
whether this power is particularly useful, but it seems more uniform to
have exactly the same syntax as list comprehensions.

One could argue that the notation "<-" is misleading, suggesting
the idea of "drawn from" as in a list comprehension.  But it's very
nice to reuse precisely the list-comprehension syntax.  Furthermore,
the only viable alternative is "=", and that would lead to parsing
difficulties, because we rely on the "=" to herald the arrival of
the right-hand side of the equation.  Consider
        f x | y = h x = 3


An alternative version
~~~~~~~~~~~~~~~~~~~~~~~
Erik Meijer has suggested [personal communication] that patterns on the
left hand side of a where clause should be matched strictly, with failure
leading to the next equation being tried.  So clunky would be written like
this:

  clunky env var1 var1 = val1 + val2
                       where
                         Just val1 = lookup env var1,
                         Just val2 = lookup env var2
  ...other equations for clunky...

This seems attractive, because it requires no syntactic changes at all.
However, it suffers from the following disadvantages

  * Haskell carefully places guards before the "=" sign so that all the
    things that have to be satisfied before committing to a particular
    right-hand side are together.  The "where" can be a long way down, and
    patterns hiding there could be easily missed.

  * The compiler has to figure out which order to match the pattern 
    bindings in.  It can usually do a dependency analysis, but
        a) The dependency graph may not fully specify the evaluation 
           order.  Alas the choice affects the
           termination semantics.  It is not clear how to specify this.
        b) The dependency graph may be cyclic if there are mutually
           recursive pattern bindings.  Perhaps they become illegal?

  * More seriously, pattern guards allow inter-mingling of pattern 
    bindings and boolean expressions, which must be matched and evaluated
    (respectively) in a particular order. With the where-clause technique
    the boolean conditions presumably appear in the guard (connected by &&)
    while the patterns appear in the where clause.  So how should they be 
    intermingled?

  * The change is not upward compatible.  Existing programs will break.

  * It is often useful for where clause to span several guarded right-hand
    sides. If the where clause fails, then presumably all the guarded rhss
    are abandoned.
    


Views
~~~~~~
One very useful application of pattern guards is to abstract data types.
Given an abstract data type it's quite common to have conditional 
selectors.  For example:

        addressMaybe :: Person -> Maybe String

The function "addressMaybe" extracts a string from the abstract data type
"Person", but returns Nothing if the person has no address.  Inside
GHC we have lots of functions like:

        getFunTyMaybe :: Type -> Maybe (Type,Type)

This returns Nothing if the argument is not a function type, and
(Just arg_ty res_ty) if the argument is a function type.  The data
type "Type" is abstract.

Since "Type" and "Person" are abstract we can't pattern-match on them,
but it's really nice to be able to say:

        f person | Just address <- addressMaybe person
                  = ...
                  | otherwise
                  = ...

Thus, pattern guards can be seen as addressing a similar goal to 
that of views, namely reconciling pattern matching with data abstraction.
Views were proposed by Wadler ages ago [1], and are the subject of a
recent concrete proposal for a Haskell language extension [2].

It is natural to ask whether views subsume pattern guards or vice versa.
The answer is "neither".

Do views subsume pattern guards?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The views proposal [2] points out that you can use views to simulate
(some) guards and, as we saw above, views have similar purpose and
functionality to at least some applications of pattern guards.

However, views give a view on a *single* value, whereas guards allow
arbitrary function calls to combine in-scope values.  For example,
clunky matches (Just val1) against (lookup env var1). We do not want a
view of "env" nor of "var1" but rather of their combination by
"lookup".  Views simply do not help with clunky.

Views are capable of dealing with the data abstraction issue of
course.  However, each conditional selector (such as getFunTyMaybe)
would require its own view, complete with its own viewtype:

        view FunType of Type = FunType Type Type
                             | NotFunType
          where
            funType (Fun arg res) = FunType arg res
            funType other_type    = NotFunType

This seems a bit heavyweight (three new names instead of one)
compared with

        getFunTypeMaybe (Fun arg res) = Just (arg,res)
        getFunTypeMaybe other_type    = Nothing

Here we can re-use the existing Maybe type.  Not only does this
save defining new types, but it allows the existing library of
functions on Maybe types to be applied directly to the result
of getFunTypeMaybe.

Just to put this point another way, suppose we had a function

        tyvarsOf :: Type -> [TyVar]

that returns the free type variables of a type.  
Would anyone suggest that we make this into a view of Type?

        view TyVarsOf of Type = TyVarsOf [TyVar]
          where
            tyVarsOf ty = ...

Now we could write

        f :: Type -> Int
        f (TyVarsOf tyvars) = length tyvars

instead of

        f :: Type -> Int
        f ty = length (tyvarsOf ty)

Surely not!  So why do so just because the value returned is a Maybe type?


Do pattern guards subsume views?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
There are two ways in which views might be desired even if you
had pattern guards:

  * We might prefer to write (using views)

        addCpx (Rect r1 i1) (Rect r1 i2) = rect (r1+r2) (c1+c2)

    rather than (using pattern guards)

        addCpx c1 c2 | Rect r1 i1 <- getRect c1, 
                        Rect r1 i2 <- getRect c2
                     = mkRect (r1+r2) (c1+c2)

    (One might argue, though, that the latter accurately indicates
    that there may be some work involved in matching against a view,
    compared to ordinary pattern matching.)

  * The pattern-guard notation gets a bit more clunky if we want a view
    that has more than one information-carrying constructor.
    For example, consider the following view:

        view AbsInt of Int = Pos Int | Neg Int
          where
            absInt n = if n>=0 then Pos n else Neg (-n)

    Here the view returns a Pos or Neg constructor, each of which
    contains the absolute value of the original Int.  Now we can say

        f (Pos n) = n+1
        f (Neg n) = n-1

    Then f 4 = 5, f (-3) = -4.

    Without views, but with pattern guards, we could write this:

        data AbsInt = Pos Int | Neg Int
        absInt n = if n>=0 then Pos n else Neg n

        f n | Pos n' <- abs_n = n'+1
            | Neg n' <- abs_n = n'-1
            where
              abs_n = absInt n

    Here we've used a where clause to ensure that absInt is only called
    once (though we could instead duplicate the call to absInt and hope
    the compile spots the common subexpression).  

    The view version is undoubtedly more compact. (Again, one might
    wonder, though, whether it perhaps conceals too much.)

  * When nested pattern guards are used, though, the use of a where
    clause fails.  For example, consider the following silly function using
    the AbsInt view

        g (Pos (Pos n)) = n+1
        g (Pos (Neg n)) = n-1   -- A bit silly

    Without views we have to write

        g n | n1 <- abs_n,
              Pos n2 <- absInt n1
            = n2+1
            | Pos n1 <- abs_n
              Neg n2 <- absInt n1
            = n2-1
            where
              abs_n = absInt n

    We can share the first call to absInt, but not the second.  This is
    a compilation issue.  Just as we might hope that the compiler would spot
    the common sub-expression if we replaced abs_n by (absInt n), so we
    might hope that it would optimise the second...  The views optimisation
    seems more simple to spot, somehow.

Views --- summary
~~~~~~~~~~~~~~~~~~
My gut feel at the moment is that the pattern-guard proposal

        - is much simpler to specify and implement than views

        - gets some expressiveness that is simply inaccessible to views

        - successfully reconciles pattern matching with data abstraction, 
                albeit with a slightly less compact notation than views -- 
                but the extra notation carries useful clues

        - is less heavyweight to use when defining many information
                extraction functions over an ADT

So I think the case for pattern guards is stronger than that for views,
and (if implemented) reduces, without eliminating, the need for views.
        
    

Argument evaluation order
~~~~~~~~~~~~~~~~~~~~~~~~~~
Haskell specifies that patterns are evaluated left to right.  Thus

        f (x:xs) (y:ys) = ...
        f xs     ys     = ...

Here, the first argument is evaluated and matched against (x:xs) and
then the second argument is evaluated and matched against (y:ys).
If you want to match the second argument first --- a significant change
since it changes the semantics of the function --- you are out of luck.
You must either change the order of the arguments, or use case expressions
instead.

With pattern guards you can say what you want, without changing the
argument order:

        f xs ys | (y:ys) <- ys
                   (x:xs) <- xs
                 = ...
        f xs ys = ...

(Since a pattern guard is a non recursive binding I have shadowed 
xs and ys, just to remind us that it's OK to do so.)

I can't say that this is a very important feature in practice, but
it's worth noting.

Implementation
~~~~~~~~~~~~~~~
I claim that the implementation of this new form of guards is
very simple.  My claim will carry more weight when I've implemented it,
but I thought I'd float the idea first to see if any improvements emerge
from the discussion.


Summary
~~~~~~~~
Is this a storm in a teacup? Much huff and puff for a seldom-occurring
situation?  No!  It happens to me ALL THE TIME.  The Glasgow Haskell Compiler
is absolutely littered with definitions like clunky.  

For the price of a one-symbol change in the language syntax we get an
upward-compatible change to Haskell that provides a smooth extension
of the binding power of pattern matching to guards.  This extension
allows a useful class of programs to be written much more elegantly.
Furthermore, its semantics and implementation are both easy.

I would really welcome feedback on this proposal.  Have you encountered
situations in which pattern guards would be useful?  Can you think of ways
in which they might be harmful, or in which their semantics is non-obvious?
Are there ways in which the proposal could be improved?  And so on.


References
~~~~~~~~~~~

[1] P Wadler, "Views: a way for pattern matching to cohabit with 
        data abstraction", POPL 14 (1987), 307-313

[2] W Burton, E Meijer, P Sansom, S Thompson, P Wadler, "A (sic) extension
        to Haskell 1.3 for views", sent to the Haskell mailing list
        23 Oct 1996



Reply via email to