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

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:

  1. 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.)
  2. 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.)

  3. 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 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, "Views: an extension to Haskell pattern matching", sent to the Haskell mailing list 23 Oct 1996