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

- Re: A new view of guards Simon L Peyton Jones
- Re: A new view of guards Lennart Augustsson
- Re: A new view of guards Manuel Chakravarty
- Re: A new view of guards Johannes Waldmann
- Re: A new view of guards Heribert Schuetz
- Re: A new view of guards Simon L Peyton Jones
- Re: A new view of guards Alex Ferguson
- Re: A new view of guards John Launchbury
- Re: A new view of guards Brian Boutel
- Re: A new view of guards Frank Christoph
- Re: A new view of guards Tony Davie