%
-% $Id: glasgow_exts.vsgml,v 1.6 1999/03/16 17:07:21 simonm Exp $
+% $Id: glasgow_exts.vsgml,v 1.20 1999/11/25 10:28:41 simonpj Exp $
%
% GHC Language Extensions.
%
<tag>Local universal quantification:</tag>
-GHC's type system supports explicit unversal quantification in
+GHC's type system supports explicit universal quantification in
constructor fields and function arguments. This is useful for things
like defining @runST@ from the state-thread world. See Section <ref
name="Local universal quantification" id="universal-quantification">.
file. The pragmas GHC supports are described in Section <ref
name="Pragmas" id="pragmas">.
+<tag>Rewrite rules:</tag>
+
+The programmer can specify rewrite rules as part of the source program
+(in a pragma). GHC applies these rewrite rules wherever it can.
+Details in Section <ref name="Rewrite Rules"
+id="rewrite-rules">.
+
+<tag>Pattern guards</tag>
+
+add a more flexible syntax and semantics for guards in function definitions.
+This gives expressiveness somewhat comparable to that of ``views''.
</descrip>
Before you get too carried away working at the lowest level (e.g.,
through a native-code generator):
<tscreen><verb>
+import Addr
+import CString
+
oldGetEnv name
- = _casm_ ``%r = getenv((char *) %0);'' name >>= \ litstring@(A# str#) ->
+ = _casm_ ``%r = getenv((char *) %0);'' name >>= \ litstring ->
return (
- if (litstring == ``NULL'') then
+ if (litstring == nullAddr) then
Left ("Fail:oldGetEnv:"++name)
else
- Right (unpackCString# str#)
+ Right (unpackCString litstring)
)
</verb></tscreen>
%************************************************************************
%* *
+<sect2>Literal-literals
+<label id="glasgow-literal-literals">
+<p>
+<nidx>Literal-literals</nidx>
+%* *
+%************************************************************************
+
+The literal-literal argument to @_casm_@ can be made use of separately
+from the @_casm_@ construct itself. Indeed, we've already used it:
+
+<tscreen><verb>
+fooH :: Char -> Int -> Double -> Word -> IO Double
+fooH c i d w = _ccall_ fooC (``stdin''::Addr) c i d w
+</verb></tscreen>
+
+The first argument that's passed to @fooC@ is given as a literal-literal,
+that is, a literal chunk of C code that will be inserted into the generated
+@.hc@ code at the right place.
+
+A literal-literal is restricted to having a type that's an instance of
+the @CCallable@ class, see <ref name="CCallable" id="ccall-gotchas">
+for more information.
+
+Notice that literal-literals are by their very nature unfriendly to
+native code generators, so exercise judgement about whether or not to
+make use of them in your code.
+
+%************************************************************************
+%* *
<sect2>Using function headers
<label id="glasgow-foreign-headers">
<p>
<label id="ccall-gotchas">
<p>
<nidx>C call dangers</nidx>
+<nidx>CCallable</nidx>
+<nidx>CReturnable</nidx>
%* *
%************************************************************************
from the <tt>MonadT</tt> data structure, rather than using pattern
matching.
+You cannot pattern-match against an argument that is polymorphic.
+For example:
+<tscreen><verb>
+ newtype TIM s a = TIM (ST s (Maybe a))
+
+ runTIM :: (forall s. TIM s a) -> Maybe a
+ runTIM (TIM m) = runST m
+</verb></tscreen>
+
+Here the pattern-match fails, because you can't pattern-match against
+an argument of type <tt>(forall s. TIM s a)</tt>. Instead you
+must bind the variable and pattern match in the right hand side:
+<tscreen><verb>
+ runTIM :: (forall s. TIM s a) -> Maybe a
+ runTIM tm = case tm of { TIM m -> runST m }
+</verb></tscreen>
+The <tt>tm</tt> on the right hand side is (invisibly) instantiated, like
+any polymorphic value at its occurrence site, and now you can pattern-match
+against it.
+
<sect2>The partial-application restriction
<p>
but single-field existentially quantified constructors aren't much
use. So the simple restriction (no existential stuff on <tt>newtype</tt>)
stands, unless there are convincing reasons to change it.
+
+
+<item> You can't use <tt>deriving</tt> to define instances of a
+data type with existentially quantified data constructors.
+
+Reason: in most cases it would not make sense. For example:#
+<tscreen><verb>
+ data T = forall a. MkT [a] deriving( Eq )
+</verb></tscreen>
+To derive <tt>Eq</tt> in the standard way we would need to have equality
+between the single component of two <tt>MkT</tt> constructors:
+<tscreen><verb>
+ instance Eq T where
+ (MkT a) == (MkT b) = ???
+</verb></tscreen>
+But <tt>a</tt> and <tt>b</tt> have distinct types, and so can't be compared.
+It's just about possible to imagine examples in which the derived instance
+would make sense, but it seems altogether simpler simply to prohibit such
+declarations. Define your own instances!
</itemize>
+
+<sect1> <idx/Assertions/
+<label id="sec:assertions">
+<p>
+
+If you want to make use of assertions in your standard Haskell code, you
+could define a function like the following:
+
+<tscreen><verb>
+assert :: Bool -> a -> a
+assert False x = error "assertion failed!"
+assert _ x = x
+</verb></tscreen>
+
+which works, but gives you back a less than useful error message --
+an assertion failed, but which and where?
+
+One way out is to define an extended <tt/assert/ function which also
+takes a descriptive string to include in the error message and
+perhaps combine this with the use of a pre-processor which inserts
+the source location where <tt/assert/ was used.
+
+Ghc offers a helping hand here, doing all of this for you. For every
+use of <tt/assert/ in the user's source:
+
+<tscreen><verb>
+kelvinToC :: Double -> Double
+kelvinToC k = assert (k >= 0.0) (k+273.15)
+</verb></tscreen>
+
+Ghc will rewrite this to also include the source location where the
+assertion was made,
+
+<tscreen><verb>
+assert pred val ==> assertError "Main.hs|15" pred val
+</verb></tscreen>
+
+The rewrite is only performed by the compiler when it spots
+applications of <tt>Exception.assert</tt>, so you can still define and
+use your own versions of <tt/assert/, should you so wish. If not,
+import <tt/Exception/ to make use <tt/assert/ in your code.
+
+To have the compiler ignore uses of assert, use the compiler option
+@-fignore-asserts@. <nidx>-fignore-asserts option</nidx> That is,
+expressions of the form @assert pred e@ will be rewritten to @e@.
+
+Assertion failures can be caught, see the documentation for the
+Hugs/GHC Exception library for information of how.
+
% -----------------------------------------------------------------------------
<sect1>Scoped Type Variables
<label id="scoped-type-variables">
and this line corresponds to line 42 in the original. GHC will adjust
its error messages to refer to the line/file named in the @LINE@
pragma.
+
+<sect2>RULES pragma
+<p>
+The RULES pragma lets you specify rewrite rules. It is described in
+Section <ref name="Rewrite Rules"
+id="rewrite-rules">.
+
+%-----------------------------------------------------------------------------
+<sect1>Rewrite rules
+<label id="rewrite-rules">
+<nidx>RULES pagma</nidx>
+<nidx>pragma, RULES</nidx>
+<nidx>rewrite rules</nidx>
+<p>
+
+The programmer can specify rewrite rules as part of the source program
+(in a pragma). GHC applies these rewrite rules wherever it can.
+
+Here is an example:
+<tscreen><verb>
+ {-# RULES
+ "map/map" forall f g xs. map f (map g xs) = map (f.g) xs
+ #-}
+</verb></tscreen>
+
+<sect2>Syntax
+<p>
+
+From a syntactic point of view:
+<itemize>
+<item> Each rule has a name, enclosed in double quotes. The name itself has
+no significance at all. It is only used when reporting how many times the rule fired.
+<item> There may be zero or more rules in a @RULES@ pragma.
+<item> Layout applies in a @RULES@ pragma. Currently no new indentation level
+is set, so you must lay out your rules starting in the same column as the
+enclosing definitions.
+<item> Each variable mentioned in a rule must either be in scope (e.g. @map@),
+or bound by the @forall@ (e.g. @f@, @g@, @xs@). The variables bound by
+the @forall@ are called the <em>pattern</em> variables. They are separated
+by spaces, just like in a type @forall@.
+<item> A pattern variable may optionally have a type signature.
+If the type of the pattern variable is polymorphic, it <em>must</em> have a type signature.
+For example, here is the @foldr/build@ rule:
+<tscreen><verb>
+ "fold/build" forall k z (g::forall b. (a->b->b) -> b -> b) .
+ foldr k z (build g) = g k z
+</verb></tscreen>
+Since @g@ has a polymorphic type, it must have a type signature.
+
+<item> The left hand side of a rule must consist of a top-level variable applied
+to arbitrary expressions. For example, this is <em>not</em> OK:
+<tscreen><verb>
+ "wrong1" forall e1 e2. case True of { True -> e1; False -> e2 } = e1
+ "wrong2" forall f. f True = True
+</verb></tscreen>
+In @"wrong1"@, the LHS is not an application; in @"wrong1"@, the LHS has a pattern variable
+in the head.
+<item> A rule does not need to be in the same module as (any of) the
+variables it mentions, though of course they need to be in scope.
+<item> Rules are automatically exported from a module, just as instance declarations are.
+</itemize>
+
+<sect2>Semantics
+<p>
+
+From a semantic point of view:
+<itemize>
+<item> Rules are only applied if you use the @-O@ flag.
+
+<item> Rules are regarded as left-to-right rewrite rules.
+When GHC finds an expression that is a substitution instance of the LHS
+of a rule, it replaces the expression by the (appropriately-substituted) RHS.
+By "a substitution instance" we mean that the LHS can be made equal to the
+expression by substituting for the pattern variables.
+
+<item> The LHS and RHS of a rule are typechecked, and must have the
+same type.
+
+<item> GHC makes absolutely no attempt to verify that the LHS and RHS
+of a rule have the same meaning. That is undecideable in general, and
+infeasible in most interesting cases. The responsibility is entirely the programmer's!
+
+<item> GHC makes no attempt to make sure that the rules are confluent or
+terminating. For example:
+<tscreen><verb>
+ "loop" forall x,y. f x y = f y x
+</verb></tscreen>
+This rule will cause the compiler to go into an infinite loop.
+
+<item> If more than one rule matches a call, GHC will choose one arbitrarily to apply.
+
+<item> GHC currently uses a very simple, syntactic, matching algorithm
+for matching a rule LHS with an expression. It seeks a substitution
+which makes the LHS and expression syntactically equal modulo alpha
+conversion. The pattern (rule), but not the expression, is eta-expanded if
+necessary. (Eta-expanding the epression can lead to laziness bugs.)
+But not beta conversion (that's called higher-order matching).
+<p>
+Matching is carried out on GHC's intermediate language, which includes
+type abstractions and applications. So a rule only matches if the
+types match too. See Section <ref name="Specialisation" id="rule-spec"> below.
+
+<item> GHC keeps trying to apply the rules as it optimises the program.
+For example, consider:
+<tscreen><verb>
+ let s = map f
+ t = map g
+ in
+ s (t xs)
+</verb></tscreen>
+The expression @s (t xs)@ does not match the rule @"map/map"@, but GHC
+will substitute for @s@ and @t@, giving an expression which does match.
+If @s@ or @t@ was (a) used more than once, and (b) large or a redex, then it would
+not be substituted, and the rule would not fire.
+
+<item> In the earlier phases of compilation, GHC inlines <em>nothing
+that appears on the LHS of a rule</em>, because once you have substituted
+for something you can't match against it (given the simple minded
+matching). So if you write the rule
+<tscreen><verb>
+ "map/map" forall f,g. map f . map g = map (f.g)
+</verb></tscreen>
+this <em>won't</em> match the expression @map f (map g xs)@.
+It will only match something written with explicit use of ".".
+Well, not quite. It <em>will</em> match the expression
+<tscreen><verb>
+ wibble f g xs
+</verb></tscreen>
+where @wibble@ is defined:
+<tscreen><verb>
+ wibble f g = map f . map g
+</verb></tscreen>
+because @wibble@ will be inlined (it's small).
+
+Later on in compilation, GHC starts inlining even things on the
+LHS of rules, but still leaves the rules enabled. This inlining
+policy is controlled by the per-simplification-pass flag @-finline-phase@n.
+
+<item> All rules are implicitly exported from the module, and are therefore
+in force in any module that imports the module that defined the rule, directly
+or indirectly. (That is, if A imports B, which imports C, then C's rules are
+in force when compiling A.) The situation is very similar to that for instance
+declarations.
+</itemize>
+
+<sect2>List fusion
+<p>
+
+The RULES mechanism is used to implement fusion (deforestation) of common list functions.
+If a "good consumer" consumes an intermediate list constructed by a "good producer", the
+intermediate list should be eliminated entirely.
+<p>
+The following are good producers:
+<itemize>
+<item> List comprehensions
+<item> Enumerations of @Int@ and @Char@ (e.g. @['a'..'z']@).
+<item> Explicit lists (e.g. @[True, False]@)
+<item> The cons constructor (e.g @3:4:[]@)
+<item> @++@
+<item> @map@
+<item> @filter@
+<item> @iterate@, @repeat@
+<item> @zip@, @zipWith@
+</itemize>
+
+The following are good consumers:
+<itemize>
+<item> List comprehensions
+<item> @array@ (on its second argument)
+<item> @length@
+<item> @++@ (on its first argument)
+<item> @map@
+<item> @filter@
+<item> @concat@
+<item> @unzip@, @unzip2@, @unzip3@, @unzip4@
+<item> @zip@, @zipWith@ (but on one argument only; if both are good producers, @zip@
+will fuse with one but not the other)
+<item> @partition@
+<item> @head@
+<item> @and@, @or@, @any@, @all@
+<item> @sequence_@
+<item> @msum@
+<item> @sortBy@
+</itemize>
+
+So, for example, the following should generate no intermediate lists:
+<tscreen><verb>
+ array (1,10) [(i,i*i) | i <- map (+ 1) [0..9]]
+</verb></tscreen>
+
+This list could readily be extended; if there are Prelude functions that you use
+a lot which are not included, please tell us.
+<p>
+If you want to write your own good consumers or producers, look at the
+Prelude definitions of the above functions to see how to do so.
+
+<sect2>Specialisation
+<label id="rule-spec">
+<p>
+
+Rewrite rules can be used to get the same effect as a feature
+present in earlier version of GHC:
+<tscreen><verb>
+ {-# SPECIALIZE fromIntegral :: Int8 -> Int16 = int8ToInt16 #-}
+</verb></tscreen>
+This told GHC to use @int8ToInt16@ instead of @fromIntegral@ whenever
+the latter was called with type @Int8 -> Int16@. That is, rather than
+specialising the original definition of @fromIntegral@ the programmer is
+promising that it is safe to use @int8ToInt16@ instead.
+
+This feature is no longer in GHC. But rewrite rules let you do the
+same thing:
+<tscreen><verb>
+ {-# RULES
+ "fromIntegral/Int8/Int16" fromIntegral = int8ToInt16
+ #-}
+</verb></tscreen>
+This slightly odd-looking rule instructs GHC to replace @fromIntegral@
+by @int8ToInt16@ <em>whenever the types match</em>. Speaking more operationally,
+GHC adds the type and dictionary applications to get the typed rule
+<tscreen><verb>
+ forall (d1::Integral Int8) (d2::Num Int16) .
+ fromIntegral Int8 Int16 d1 d2 = int8ToInt16
+</verb></tscreen>
+What is more,
+this rule does not need to be in the same file as fromIntegral,
+unlike the @SPECIALISE@ pragmas which currently do (so that they
+have an original definition available to specialise).
+
+<sect2>Controlling what's going on
+<p>
+
+<itemize>
+<item> Use @-ddump-rules@ to see what transformation rules GHC is using.
+<item> Use @-ddump-simpl-stats@ to see what rules are being fired.
+If you add @-dppr-debug@ you get a more detailed listing.
+<item> The defintion of (say) @build@ in @PrelBase.lhs@ looks llike this:
+<tscreen><verb>
+ build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
+ {-# INLINE build #-}
+ build g = g (:) []
+</verb></tscreen>
+Notice the @INLINE@! That prevents @(:)@ from being inlined when compiling
+@PrelBase@, so that an importing module will ``see'' the @(:)@, and can
+match it on the LHS of a rule. @INLINE@ prevents any inlining happening
+in the RHS of the @INLINE@ thing. I regret the delicacy of this.
+
+<item> In @ghc/lib/std/PrelBase.lhs@ look at the rules for @map@ to
+see how to write rules that will do fusion and yet give an efficient
+program even if fusion doesn't happen. More rules in @PrelList.lhs@.
+</itemize>
+
+
+%-----------------------------------------------------------------------------
+<sect1>Pattern guards
+<label id="pattern-guards">
+<p>
+GHC supports the ``pattern-guards'' extension to
+the guards that form part of Haskell function
+definitions. 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.
+
+<sect2>What's the problem?
+<p>
+Consider the following Haskell function definition
+<tscreen><verb>
+ filter p [] = []
+ filter p (y:ys) | p y = y : filter p ys
+ | otherwise = filter p ys
+</verb></tscreen>
+
+<p>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.
+
+<p>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:
+<tscreen><verb>
+ lookup :: FinteMap -> Int -> Maybe Int
+</verb></tscreen>
+
+<p>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:
+<tscreen><verb>
+ 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
+</verb></tscreen>
+The auxiliary functions are
+<tscreen><verb>
+ maybeToBool :: Maybe a -> Bool
+ maybeToBool (Just x) = True
+ maybeToBool Nothing = False
+
+ expectJust :: Maybe a -> a
+ expectJust (Just x) = x
+ expectJust Nothing = error "Unexpected Nothing"
+</verb></tscreen>
+<p>What is <tt>clunky</tt> doing? The guard <tt>ok1 && ok2</tt> checks that both
+lookups succeed, using <tt>maybeToBool</tt> to convert the maybe types to
+booleans. The (lazily evaluated) <tt>expectJust</tt> calls extract the values
+from the results of the lookups, and binds the returned values to
+<tt>val1</tt> and <tt>val2</tt> respectively. If either lookup fails, then <tt>clunky</tt>
+takes the <tt>otherwise</tt> case and returns the sum of its arguments.
+
+<p>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 <tt>clunky</tt> would be to use case expressions:
+<tscreen><verb>
+ 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
+</verb></tscreen>
+<p>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 (<tt>fail</tt>),
+and the whole expression tends to become more and more indented.
+
+<p>Worse, if this was just one equation of <tt>clunky</tt>, with others that
+follow, then the thing wouldn't work at all. That is, suppose we have
+<tscreen><verb>
+ 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...
+</verb></tscreen>
+Now, if either the lookups fail we want to fall through to the second
+and third equations for <tt>clunky'</tt>. If we write the definition in the
+form of a case expression we are forced to make the latter two
+equations for <tt>clunky'</tt> into a separate definition and call it in
+the right hand side of <tt>fail</tt>. 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.
+
+
+<p>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:
+<tscreen><verb>
+ 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...
+</verb></tscreen>
+<p>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 <tt>Just</tt> pattern corresponds to. Worse, we can't
+use one lookup in the next. For example, suppose our function was
+like this:
+<tscreen><verb>
+ 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
+</verb></tscreen>
+<p>Notice that the second lookup uses val1, the result of the first lookup.
+To express this with a <tt>clunky_help</tt> function requires a second helper
+function nested inside the first. Dire stuff.
+
+<p>So the original definition, using <tt>maybeToBool</tt> and <tt>expectJust</tt> has the
+merit that it scales nicely, to accommodate both multiple equations
+and successive lookups. Yet it stinks.
+
+
+<sect2>The pattern guards extension
+<p>
+The extension that GHC implements is simple:
+<em>instead of being a boolean expression,
+a guard is a list of qualifiers,
+exactly as in a list comprehension</em>.
+
+<p>That is, the only syntax change is to replace
+<em>exp</em> by <em>quals</em> in the syntax of guarded equations.
+
+<p>Here is how you can now write <tt>clunky</tt>:
+<tscreen><verb>
+ clunky env var1 var1
+ | Just val1 <- lookup env var1
+ , Just val2 <- lookup env var2
+ = val1 + val2
+ ...other equations for clunky...
+</verb></tscreen>
+<p>The semantics should be clear enough. The qualifers are matched in
+order. For a <tt><-</tt> qualifier, which I call a <em>pattern guard</em>, 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 <tt><-</tt> 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.
+
+<p>Just as with list comprehensions, boolean expressions can be freely mixed
+with among the pattern guards. For example:
+<tscreen><verb>
+ f x | [y] <- x
+ , y > 3
+ , Just z <- h y
+ = ...
+</verb></tscreen>
+<p>Haskell's current guards therefore emerge as a special case, in which the
+qualifier list has just one element, a boolean expression.
+
+<p>Just as with list comprehensions, a <tt>let</tt> qualifier can introduce a binding.
+It is also possible to do this with pattern guard with a simple
+variable pattern <tt>a <- e</tt>
+However a <tt>let</tt> 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.
+
+<p>One could argue that the notation <tt><-</tt> is misleading, suggesting
+the idea of <em>drawn from</em> as in a list comprehension. But it's very
+nice to reuse precisely the list-comprehension syntax. Furthermore,
+the only viable alternative is <tt>=</tt>, and that would lead to parsing
+difficulties, because we rely on the <tt>=</tt> to herald the arrival of
+the right-hand side of the equation. Consider <tt>f x | y = h x = 3</tt>.
+
+<sect2>Views
+
+<p>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:
+<tscreen><verb>
+ addressMaybe :: Person -> Maybe String
+</verb></tscreen>
+<p>The function <tt>addressMaybe</tt> extracts a string from the abstract data type
+<tt>Person</tt>, but returns <tt>Nothing</tt> if the person has no address. Inside
+GHC we have lots of functions like:
+<tscreen><verb>
+ getFunTyMaybe :: Type -> Maybe (Type,Type)
+</verb></tscreen>
+<p>This returns <tt>Nothing</tt> if the argument is not a function type, and
+<tt>(Just arg_ty res_ty)</tt> if the argument is a function type. The data
+type <tt>Type</tt> is abstract.
+
+<p>Since <tt>Type</tt> and <tt>Person</tt> are abstract we can't pattern-match on them,
+but it's really nice to be able to say:
+<tscreen><verb>
+ f person | Just address <- addressMaybe person
+ = ...
+ | otherwise
+ = ...
+</verb></tscreen>
+<p>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].
+
+<p>It is natural to ask whether views subsume pattern guards or vice versa.
+The answer is "neither".
+
+<sect3>Do views subsume pattern guards?
+
+<p>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.
+
+<p>However, views give a view on a <em>single</em> value, whereas guards allow
+arbitrary function calls to combine in-scope values. For example,
+<tt>clunky</tt> matches <tt>(Just val1)</tt> against <tt>(lookup env var1)</tt>. We do not want a
+view of <tt>env</tt> nor of <tt>var1</tt> but rather of their combination by
+<tt>lookup</tt>. Views simply do not help with <tt>clunky</tt>.
+
+<p>Views are capable of dealing with the data abstraction issue of
+course. However, each conditional selector (such as <tt>getFunTyMaybe</tt>)
+would require its own view, complete with its own viewtype:
+<tscreen><verb>
+ view FunType of Type = FunType Type Type
+ | NotFunType
+ where
+ funType (Fun arg res) = FunType arg res
+ funType other_type = NotFunType
+</verb></tscreen>
+This seems a bit heavyweight (three new names instead of one)
+compared with
+<tscreen><verb>
+ getFunTypeMaybe (Fun arg res) = Just (arg,res)
+ getFunTypeMaybe other_type = Nothing
+</verb></tscreen>
+<p>Here we can re-use the existing <tt>Maybe</tt> type. Not only does this
+save defining new types, but it allows the existing library of
+functions on <tt>Maybe</tt> types to be applied directly to the result
+of <tt>getFunTypeMaybe</tt>.
+
+<p>Just to put this point another way, suppose we had a function
+<tscreen><verb>
+ tyvarsOf :: Type -> [TyVar]
+</verb></tscreen>
+that returns the free type variables of a type.
+Would anyone suggest that we make this into a view of <tt>Type</tt>?
+<tscreen><verb>
+ view TyVarsOf of Type = TyVarsOf [TyVar]
+ where
+ tyVarsOf ty = ...
+</verb></tscreen>
+Now we could write
+<tscreen><verb>
+ f :: Type -> Int
+ f (TyVarsOf tyvars) = length tyvars
+</verb></tscreen>
+instead of
+<tscreen><verb>
+ f :: Type -> Int
+ f ty = length (tyvarsOf ty)
+</verb></tscreen>
+Surely not! So why do so just because the value returned is a <tt>Maybe</tt> type?
+
+<sect3>Do pattern guards subsume views?
+
+<p>There are two ways in which views might be desired even if you
+had pattern guards:<p>
+<itemize>
+<item>
+We might prefer to write (using views)
+<tscreen><verb>
+ addCpx (Rect r1 i1) (Rect r1 i2) = rect (r1+r2) (c1+c2)
+</verb></tscreen>
+rather than (using pattern guards)
+<tscreen><verb>
+ addCpx c1 c2
+ | Rect r1 i1 <- getRect c1
+ , Rect r1 i2 <- getRect c2
+ = mkRect (r1+r2) (c1+c2)
+</verb></tscreen>(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.)
+</item>
+<item>
+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:
+<tscreen><verb>
+ view AbsInt of Int = Pos Int | Neg Int
+ where
+ absInt n = if n>=0 then Pos n else Neg (-n)
+</verb></tscreen>
+Here the view returns a Pos or Neg constructor, each of which contains the absolute value of the original Int. Now we can say
+<tscreen><verb>
+ f (Pos n) = n+1
+ f (Neg n) = n-1
+</verb></tscreen>
+Then <tt>f 4 = 5</tt>, <tt>f (-3) = -4</tt>.
+
+Without views, but with pattern guards, we could write this:
+<tscreen><verb>
+ 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
+</verb></tscreen>
+<p>Here we've used a where clause to ensure that <tt>absInt</tt> is only called once (though we could instead duplicate the call to <tt>absInt</tt> and hope the compile spots the common subexpression).
+
+<p>The view version is undoubtedly more compact. (Again, one might wonder, though, whether it perhaps conceals too much.)
+</item>
+<item>
+When nested pattern guards are used, though, the use of a where clause fails. For example, consider the following silly function using the <tt>AbsInt</tt> view
+<tscreen><verb>
+ g (Pos (Pos n)) = n+1
+ g (Pos (Neg n)) = n-1 -- A bit silly
+</verb></tscreen>
+Without views we have to write
+<tscreen><verb>
+ 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
+</verb></tscreen>
+<p>We can share the first call to <tt>absInt</tt> 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 <tt>abs_n by (absInt n)</tt>, so we might hope that it would optimise the second.
+The views optimisation seems more simple to spot, somehow.
+</item>
+</itemize>
+
+<sect3>Views --- summary
+<p>
+My gut feel at the moment is that the pattern-guard proposal
+<itemize>
+<item>is much simpler to specify and implement than views
+<item> gets some expressiveness that is simply inaccessible to views.
+<item>successfully reconciles pattern matching with data abstraction,
+albeit with a slightly less compact notation than views --
+but the extra notation carries useful clues
+<item>is less heavyweight to use when defining many information
+extraction functions over an ADT
+</itemize>
+So I think the case for pattern guards is stronger than that for views,
+and (if implemented) reduces, without eliminating, the need for views.
+
+<sect2>Argument evaluation order
+
+<p>Haskell specifies that patterns are evaluated left to right. Thus
+<tscreen><verb>
+ f (x:xs) (y:ys) = ...
+ f xs ys = ...
+</verb></tscreen>
+Here, the first argument is evaluated and matched against <tt>(x:xs)</tt> and
+then the second argument is evaluated and matched against <tt>(y:ys)</tt>.
+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.
+
+<p>With pattern guards you can say what you want, without changing the
+argument order:
+<tscreen><verb>
+ f xs ys | (y:ys) <- ys
+ (x:xs) <- xs
+ = ...
+ f xs ys = ...
+</verb></tscreen>
+(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.)
+
+<p>I can't say that this is a very important feature in practice, but
+it's worth noting.
+
+<sect2>References
+
+<p>[1] P Wadler, "Views: a way for pattern matching to cohabit with
+data abstraction", POPL 14 (1987), 307-313
+
+<p>[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
projects / ghc-hetmet.git / blobdiff