vectorise: Put it out of its misery
[ghc.git] / compiler / deSugar / Match.hs
1 {-
2 (c) The University of Glasgow 2006
3 (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
4
5
6 The @match@ function
7 -}
8
9 {-# LANGUAGE CPP #-}
10 {-# LANGUAGE TypeFamilies #-}
11
12 module Match ( match, matchEquations, matchWrapper, matchSimply, matchSinglePat ) where
13
14 #include "HsVersions.h"
15
16 import GhcPrelude
17
18 import {-#SOURCE#-} DsExpr (dsLExpr, dsSyntaxExpr)
19
20 import DynFlags
21 import HsSyn
22 import TcHsSyn
23 import TcEvidence
24 import TcRnMonad
25 import Check
26 import CoreSyn
27 import Literal
28 import CoreUtils
29 import MkCore
30 import DsMonad
31 import DsBinds
32 import DsGRHSs
33 import DsUtils
34 import Id
35 import ConLike
36 import DataCon
37 import PatSyn
38 import MatchCon
39 import MatchLit
40 import Type
41 import Coercion ( eqCoercion )
42 import TyCon( isNewTyCon )
43 import TysWiredIn
44 import SrcLoc
45 import Maybes
46 import Util
47 import Name
48 import Outputable
49 import BasicTypes ( isGenerated, il_value, fl_value )
50 import FastString
51 import Unique
52 import UniqDFM
53
54 import Control.Monad( when, unless )
55 import qualified Data.Map as Map
56 import Data.List (groupBy)
57
58 {-
59 ************************************************************************
60 * *
61 The main matching function
62 * *
63 ************************************************************************
64
65 The function @match@ is basically the same as in the Wadler chapter
66 from "The Implementation of Functional Programming Languages",
67 except it is monadised, to carry around the name supply, info about
68 annotations, etc.
69
70 Notes on @match@'s arguments, assuming $m$ equations and $n$ patterns:
71 \begin{enumerate}
72 \item
73 A list of $n$ variable names, those variables presumably bound to the
74 $n$ expressions being matched against the $n$ patterns. Using the
75 list of $n$ expressions as the first argument showed no benefit and
76 some inelegance.
77
78 \item
79 The second argument, a list giving the ``equation info'' for each of
80 the $m$ equations:
81 \begin{itemize}
82 \item
83 the $n$ patterns for that equation, and
84 \item
85 a list of Core bindings [@(Id, CoreExpr)@ pairs] to be ``stuck on
86 the front'' of the matching code, as in:
87 \begin{verbatim}
88 let <binds>
89 in <matching-code>
90 \end{verbatim}
91 \item
92 and finally: (ToDo: fill in)
93
94 The right way to think about the ``after-match function'' is that it
95 is an embryonic @CoreExpr@ with a ``hole'' at the end for the
96 final ``else expression''.
97 \end{itemize}
98
99 There is a data type, @EquationInfo@, defined in module @DsMonad@.
100
101 An experiment with re-ordering this information about equations (in
102 particular, having the patterns available in column-major order)
103 showed no benefit.
104
105 \item
106 A default expression---what to evaluate if the overall pattern-match
107 fails. This expression will (almost?) always be
108 a measly expression @Var@, unless we know it will only be used once
109 (as we do in @glue_success_exprs@).
110
111 Leaving out this third argument to @match@ (and slamming in lots of
112 @Var "fail"@s) is a positively {\em bad} idea, because it makes it
113 impossible to share the default expressions. (Also, it stands no
114 chance of working in our post-upheaval world of @Locals@.)
115 \end{enumerate}
116
117 Note: @match@ is often called via @matchWrapper@ (end of this module),
118 a function that does much of the house-keeping that goes with a call
119 to @match@.
120
121 It is also worth mentioning the {\em typical} way a block of equations
122 is desugared with @match@. At each stage, it is the first column of
123 patterns that is examined. The steps carried out are roughly:
124 \begin{enumerate}
125 \item
126 Tidy the patterns in column~1 with @tidyEqnInfo@ (this may add
127 bindings to the second component of the equation-info):
128 \item
129 Now {\em unmix} the equations into {\em blocks} [w\/ local function
130 @match_groups@], in which the equations in a block all have the same
131 match group.
132 (see ``the mixture rule'' in SLPJ).
133 \item
134 Call the right match variant on each block of equations; it will do the
135 appropriate thing for each kind of column-1 pattern.
136 \end{enumerate}
137
138 We are a little more paranoid about the ``empty rule'' (SLPJ, p.~87)
139 than the Wadler-chapter code for @match@ (p.~93, first @match@ clause).
140 And gluing the ``success expressions'' together isn't quite so pretty.
141
142 This @match@ uses @tidyEqnInfo@
143 to get `as'- and `twiddle'-patterns out of the way (tidying), before
144 applying ``the mixture rule'' (SLPJ, p.~88) [which really {\em
145 un}mixes the equations], producing a list of equation-info
146 blocks, each block having as its first column patterns compatible with each other.
147
148 Note [Match Ids]
149 ~~~~~~~~~~~~~~~~
150 Most of the matching functions take an Id or [Id] as argument. This Id
151 is the scrutinee(s) of the match. The desugared expression may
152 sometimes use that Id in a local binding or as a case binder. So it
153 should not have an External name; Lint rejects non-top-level binders
154 with External names (Trac #13043).
155 -}
156
157 type MatchId = Id -- See Note [Match Ids]
158
159 match :: [MatchId] -- Variables rep\'ing the exprs we\'re matching with
160 -- See Note [Match Ids]
161 -> Type -- Type of the case expression
162 -> [EquationInfo] -- Info about patterns, etc. (type synonym below)
163 -> DsM MatchResult -- Desugared result!
164
165 match [] ty eqns
166 = ASSERT2( not (null eqns), ppr ty )
167 return (foldr1 combineMatchResults match_results)
168 where
169 match_results = [ ASSERT( null (eqn_pats eqn) )
170 eqn_rhs eqn
171 | eqn <- eqns ]
172
173 match vars@(v:_) ty eqns -- Eqns *can* be empty
174 = ASSERT2( all (isInternalName . idName) vars, ppr vars )
175 do { dflags <- getDynFlags
176 -- Tidy the first pattern, generating
177 -- auxiliary bindings if necessary
178 ; (aux_binds, tidy_eqns) <- mapAndUnzipM (tidyEqnInfo v) eqns
179
180 -- Group the equations and match each group in turn
181 ; let grouped = groupEquations dflags tidy_eqns
182
183 -- print the view patterns that are commoned up to help debug
184 ; whenDOptM Opt_D_dump_view_pattern_commoning (debug grouped)
185
186 ; match_results <- match_groups grouped
187 ; return (adjustMatchResult (foldr (.) id aux_binds) $
188 foldr1 combineMatchResults match_results) }
189 where
190 dropGroup :: [(PatGroup,EquationInfo)] -> [EquationInfo]
191 dropGroup = map snd
192
193 match_groups :: [[(PatGroup,EquationInfo)]] -> DsM [MatchResult]
194 -- Result list of [MatchResult] is always non-empty
195 match_groups [] = matchEmpty v ty
196 match_groups gs = mapM match_group gs
197
198 match_group :: [(PatGroup,EquationInfo)] -> DsM MatchResult
199 match_group [] = panic "match_group"
200 match_group eqns@((group,_) : _)
201 = case group of
202 PgCon {} -> matchConFamily vars ty (subGroupUniq [(c,e) | (PgCon c, e) <- eqns])
203 PgSyn {} -> matchPatSyn vars ty (dropGroup eqns)
204 PgLit {} -> matchLiterals vars ty (subGroupOrd [(l,e) | (PgLit l, e) <- eqns])
205 PgAny -> matchVariables vars ty (dropGroup eqns)
206 PgN {} -> matchNPats vars ty (dropGroup eqns)
207 PgOverS {}-> matchNPats vars ty (dropGroup eqns)
208 PgNpK {} -> matchNPlusKPats vars ty (dropGroup eqns)
209 PgBang -> matchBangs vars ty (dropGroup eqns)
210 PgCo {} -> matchCoercion vars ty (dropGroup eqns)
211 PgView {} -> matchView vars ty (dropGroup eqns)
212 PgOverloadedList -> matchOverloadedList vars ty (dropGroup eqns)
213
214 -- FIXME: we should also warn about view patterns that should be
215 -- commoned up but are not
216
217 -- print some stuff to see what's getting grouped
218 -- use -dppr-debug to see the resolution of overloaded literals
219 debug eqns =
220 let gs = map (\group -> foldr (\ (p,_) -> \acc ->
221 case p of PgView e _ -> e:acc
222 _ -> acc) [] group) eqns
223 maybeWarn [] = return ()
224 maybeWarn l = warnDs NoReason (vcat l)
225 in
226 maybeWarn $ (map (\g -> text "Putting these view expressions into the same case:" <+> (ppr g))
227 (filter (not . null) gs))
228
229 matchEmpty :: MatchId -> Type -> DsM [MatchResult]
230 -- See Note [Empty case expressions]
231 matchEmpty var res_ty
232 = return [MatchResult CanFail mk_seq]
233 where
234 mk_seq fail = return $ mkWildCase (Var var) (idType var) res_ty
235 [(DEFAULT, [], fail)]
236
237 matchVariables :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
238 -- Real true variables, just like in matchVar, SLPJ p 94
239 -- No binding to do: they'll all be wildcards by now (done in tidy)
240 matchVariables (_:vars) ty eqns = match vars ty (shiftEqns eqns)
241 matchVariables [] _ _ = panic "matchVariables"
242
243 matchBangs :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
244 matchBangs (var:vars) ty eqns
245 = do { match_result <- match (var:vars) ty $
246 map (decomposeFirstPat getBangPat) eqns
247 ; return (mkEvalMatchResult var ty match_result) }
248 matchBangs [] _ _ = panic "matchBangs"
249
250 matchCoercion :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
251 -- Apply the coercion to the match variable and then match that
252 matchCoercion (var:vars) ty (eqns@(eqn1:_))
253 = do { let CoPat _ co pat _ = firstPat eqn1
254 ; let pat_ty' = hsPatType pat
255 ; var' <- newUniqueId var pat_ty'
256 ; match_result <- match (var':vars) ty $
257 map (decomposeFirstPat getCoPat) eqns
258 ; core_wrap <- dsHsWrapper co
259 ; let bind = NonRec var' (core_wrap (Var var))
260 ; return (mkCoLetMatchResult bind match_result) }
261 matchCoercion _ _ _ = panic "matchCoercion"
262
263 matchView :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
264 -- Apply the view function to the match variable and then match that
265 matchView (var:vars) ty (eqns@(eqn1:_))
266 = do { -- we could pass in the expr from the PgView,
267 -- but this needs to extract the pat anyway
268 -- to figure out the type of the fresh variable
269 let ViewPat _ viewExpr (L _ pat) = firstPat eqn1
270 -- do the rest of the compilation
271 ; let pat_ty' = hsPatType pat
272 ; var' <- newUniqueId var pat_ty'
273 ; match_result <- match (var':vars) ty $
274 map (decomposeFirstPat getViewPat) eqns
275 -- compile the view expressions
276 ; viewExpr' <- dsLExpr viewExpr
277 ; return (mkViewMatchResult var'
278 (mkCoreAppDs (text "matchView") viewExpr' (Var var))
279 match_result) }
280 matchView _ _ _ = panic "matchView"
281
282 matchOverloadedList :: [MatchId] -> Type -> [EquationInfo] -> DsM MatchResult
283 matchOverloadedList (var:vars) ty (eqns@(eqn1:_))
284 -- Since overloaded list patterns are treated as view patterns,
285 -- the code is roughly the same as for matchView
286 = do { let ListPat (ListPatTc elt_ty (Just (_,e))) _ = firstPat eqn1
287 ; var' <- newUniqueId var (mkListTy elt_ty) -- we construct the overall type by hand
288 ; match_result <- match (var':vars) ty $
289 map (decomposeFirstPat getOLPat) eqns -- getOLPat builds the pattern inside as a non-overloaded version of the overloaded list pattern
290 ; e' <- dsSyntaxExpr e [Var var]
291 ; return (mkViewMatchResult var' e' match_result) }
292 matchOverloadedList _ _ _ = panic "matchOverloadedList"
293
294 -- decompose the first pattern and leave the rest alone
295 decomposeFirstPat :: (Pat GhcTc -> Pat GhcTc) -> EquationInfo -> EquationInfo
296 decomposeFirstPat extractpat (eqn@(EqnInfo { eqn_pats = pat : pats }))
297 = eqn { eqn_pats = extractpat pat : pats}
298 decomposeFirstPat _ _ = panic "decomposeFirstPat"
299
300 getCoPat, getBangPat, getViewPat, getOLPat :: Pat GhcTc -> Pat GhcTc
301 getCoPat (CoPat _ _ pat _) = pat
302 getCoPat _ = panic "getCoPat"
303 getBangPat (BangPat _ pat ) = unLoc pat
304 getBangPat _ = panic "getBangPat"
305 getViewPat (ViewPat _ _ pat) = unLoc pat
306 getViewPat _ = panic "getViewPat"
307 getOLPat (ListPat (ListPatTc ty (Just _)) pats)
308 = ListPat (ListPatTc ty Nothing) pats
309 getOLPat _ = panic "getOLPat"
310
311 {-
312 Note [Empty case alternatives]
313 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
314 The list of EquationInfo can be empty, arising from
315 case x of {} or \case {}
316 In that situation we desugar to
317 case x of { _ -> error "pattern match failure" }
318 The *desugarer* isn't certain whether there really should be no
319 alternatives, so it adds a default case, as it always does. A later
320 pass may remove it if it's inaccessible. (See also Note [Empty case
321 alternatives] in CoreSyn.)
322
323 We do *not* desugar simply to
324 error "empty case"
325 or some such, because 'x' might be bound to (error "hello"), in which
326 case we want to see that "hello" exception, not (error "empty case").
327 See also Note [Case elimination: lifted case] in Simplify.
328
329
330 ************************************************************************
331 * *
332 Tidying patterns
333 * *
334 ************************************************************************
335
336 Tidy up the leftmost pattern in an @EquationInfo@, given the variable @v@
337 which will be scrutinised.
338
339 This makes desugaring the pattern match simpler by transforming some of
340 the patterns to simpler forms. (Tuples to Constructor Patterns)
341
342 Among other things in the resulting Pattern:
343 * Variables and irrefutable(lazy) patterns are replaced by Wildcards
344 * As patterns are replaced by the patterns they wrap.
345
346 The bindings created by the above patterns are put into the returned wrapper
347 instead.
348
349 This means a definition of the form:
350 f x = rhs
351 when called with v get's desugared to the equivalent of:
352 let x = v
353 in
354 f _ = rhs
355
356 The same principle holds for as patterns (@) and
357 irrefutable/lazy patterns (~).
358 In the case of irrefutable patterns the irrefutable pattern is pushed into
359 the binding.
360
361 Pattern Constructors which only represent syntactic sugar are converted into
362 their desugared representation.
363 This usually means converting them to Constructor patterns but for some
364 depends on enabled extensions. (Eg OverloadedLists)
365
366 GHC also tries to convert overloaded Literals into regular ones.
367
368 The result of this tidying is that the column of patterns will include
369 only these which can be assigned a PatternGroup (see patGroup).
370
371 -}
372
373 tidyEqnInfo :: Id -> EquationInfo
374 -> DsM (DsWrapper, EquationInfo)
375 -- DsM'd because of internal call to dsLHsBinds
376 -- and mkSelectorBinds.
377 -- "tidy1" does the interesting stuff, looking at
378 -- one pattern and fiddling the list of bindings.
379 --
380 -- POST CONDITION: head pattern in the EqnInfo is
381 -- one of these for which patGroup is defined.
382
383 tidyEqnInfo _ (EqnInfo { eqn_pats = [] })
384 = panic "tidyEqnInfo"
385
386 tidyEqnInfo v eqn@(EqnInfo { eqn_pats = pat : pats })
387 = do { (wrap, pat') <- tidy1 v pat
388 ; return (wrap, eqn { eqn_pats = do pat' : pats }) }
389
390 tidy1 :: Id -- The Id being scrutinised
391 -> Pat GhcTc -- The pattern against which it is to be matched
392 -> DsM (DsWrapper, -- Extra bindings to do before the match
393 Pat GhcTc) -- Equivalent pattern
394
395 -------------------------------------------------------
396 -- (pat', mr') = tidy1 v pat mr
397 -- tidies the *outer level only* of pat, giving pat'
398 -- It eliminates many pattern forms (as-patterns, variable patterns,
399 -- list patterns, etc) and returns any created bindings in the wrapper.
400
401 tidy1 v (ParPat _ pat) = tidy1 v (unLoc pat)
402 tidy1 v (SigPat _ pat) = tidy1 v (unLoc pat)
403 tidy1 _ (WildPat ty) = return (idDsWrapper, WildPat ty)
404 tidy1 v (BangPat _ (L l p)) = tidy_bang_pat v l p
405
406 -- case v of { x -> mr[] }
407 -- = case v of { _ -> let x=v in mr[] }
408 tidy1 v (VarPat _ (L _ var))
409 = return (wrapBind var v, WildPat (idType var))
410
411 -- case v of { x@p -> mr[] }
412 -- = case v of { p -> let x=v in mr[] }
413 tidy1 v (AsPat _ (L _ var) pat)
414 = do { (wrap, pat') <- tidy1 v (unLoc pat)
415 ; return (wrapBind var v . wrap, pat') }
416
417 {- now, here we handle lazy patterns:
418 tidy1 v ~p bs = (v, v1 = case v of p -> v1 :
419 v2 = case v of p -> v2 : ... : bs )
420
421 where the v_i's are the binders in the pattern.
422
423 ToDo: in "v_i = ... -> v_i", are the v_i's really the same thing?
424
425 The case expr for v_i is just: match [v] [(p, [], \ x -> Var v_i)] any_expr
426 -}
427
428 tidy1 v (LazyPat _ pat)
429 -- This is a convenient place to check for unlifted types under a lazy pattern.
430 -- Doing this check during type-checking is unsatisfactory because we may
431 -- not fully know the zonked types yet. We sure do here.
432 = do { let unlifted_bndrs = filter (isUnliftedType . idType) (collectPatBinders pat)
433 ; unless (null unlifted_bndrs) $
434 putSrcSpanDs (getLoc pat) $
435 errDs (hang (text "A lazy (~) pattern cannot bind variables of unlifted type." $$
436 text "Unlifted variables:")
437 2 (vcat (map (\id -> ppr id <+> dcolon <+> ppr (idType id))
438 unlifted_bndrs)))
439
440 ; (_,sel_prs) <- mkSelectorBinds [] pat (Var v)
441 ; let sel_binds = [NonRec b rhs | (b,rhs) <- sel_prs]
442 ; return (mkCoreLets sel_binds, WildPat (idType v)) }
443
444 tidy1 _ (ListPat (ListPatTc ty Nothing) pats )
445 = return (idDsWrapper, unLoc list_ConPat)
446 where
447 list_ConPat = foldr (\ x y -> mkPrefixConPat consDataCon [x, y] [ty])
448 (mkNilPat ty)
449 pats
450
451 tidy1 _ (TuplePat tys pats boxity)
452 = return (idDsWrapper, unLoc tuple_ConPat)
453 where
454 arity = length pats
455 tuple_ConPat = mkPrefixConPat (tupleDataCon boxity arity) pats tys
456
457 tidy1 _ (SumPat tys pat alt arity)
458 = return (idDsWrapper, unLoc sum_ConPat)
459 where
460 sum_ConPat = mkPrefixConPat (sumDataCon alt arity) [pat] tys
461
462 -- LitPats: we *might* be able to replace these w/ a simpler form
463 tidy1 _ (LitPat _ lit)
464 = return (idDsWrapper, tidyLitPat lit)
465
466 -- NPats: we *might* be able to replace these w/ a simpler form
467 tidy1 _ (NPat ty (L _ lit) mb_neg eq)
468 = return (idDsWrapper, tidyNPat tidyLitPat lit mb_neg eq ty)
469
470 -- Everything else goes through unchanged...
471
472 tidy1 _ non_interesting_pat
473 = return (idDsWrapper, non_interesting_pat)
474
475 --------------------
476 tidy_bang_pat :: Id -> SrcSpan -> Pat GhcTc -> DsM (DsWrapper, Pat GhcTc)
477
478 -- Discard par/sig under a bang
479 tidy_bang_pat v _ (ParPat _ (L l p)) = tidy_bang_pat v l p
480 tidy_bang_pat v _ (SigPat _ (L l p)) = tidy_bang_pat v l p
481
482 -- Push the bang-pattern inwards, in the hope that
483 -- it may disappear next time
484 tidy_bang_pat v l (AsPat x v' p) = tidy1 v (AsPat x v' (L l (BangPat noExt p)))
485 tidy_bang_pat v l (CoPat x w p t)
486 = tidy1 v (CoPat x w (BangPat noExt (L l p)) t)
487
488 -- Discard bang around strict pattern
489 tidy_bang_pat v _ p@(LitPat {}) = tidy1 v p
490 tidy_bang_pat v _ p@(ListPat {}) = tidy1 v p
491 tidy_bang_pat v _ p@(TuplePat {}) = tidy1 v p
492 tidy_bang_pat v _ p@(SumPat {}) = tidy1 v p
493
494 -- Data/newtype constructors
495 tidy_bang_pat v l p@(ConPatOut { pat_con = L _ (RealDataCon dc)
496 , pat_args = args
497 , pat_arg_tys = arg_tys })
498 -- Newtypes: push bang inwards (Trac #9844)
499 =
500 if isNewTyCon (dataConTyCon dc)
501 then tidy1 v (p { pat_args = push_bang_into_newtype_arg l ty args })
502 else tidy1 v p -- Data types: discard the bang
503 where
504 (ty:_) = dataConInstArgTys dc arg_tys
505
506 -------------------
507 -- Default case, leave the bang there:
508 -- VarPat,
509 -- LazyPat,
510 -- WildPat,
511 -- ViewPat,
512 -- pattern synonyms (ConPatOut with PatSynCon)
513 -- NPat,
514 -- NPlusKPat
515 --
516 -- For LazyPat, remember that it's semantically like a VarPat
517 -- i.e. !(~p) is not like ~p, or p! (Trac #8952)
518 --
519 -- NB: SigPatIn, ConPatIn should not happen
520
521 tidy_bang_pat _ l p = return (idDsWrapper, BangPat noExt (L l p))
522
523 -------------------
524 push_bang_into_newtype_arg :: SrcSpan
525 -> Type -- The type of the argument we are pushing
526 -- onto
527 -> HsConPatDetails GhcTc -> HsConPatDetails GhcTc
528 -- See Note [Bang patterns and newtypes]
529 -- We are transforming !(N p) into (N !p)
530 push_bang_into_newtype_arg l _ty (PrefixCon (arg:args))
531 = ASSERT( null args)
532 PrefixCon [L l (BangPat noExt arg)]
533 push_bang_into_newtype_arg l _ty (RecCon rf)
534 | HsRecFields { rec_flds = L lf fld : flds } <- rf
535 , HsRecField { hsRecFieldArg = arg } <- fld
536 = ASSERT( null flds)
537 RecCon (rf { rec_flds = [L lf (fld { hsRecFieldArg
538 = L l (BangPat noExt arg) })] })
539 push_bang_into_newtype_arg l ty (RecCon rf) -- If a user writes !(T {})
540 | HsRecFields { rec_flds = [] } <- rf
541 = PrefixCon [L l (BangPat noExt (noLoc (WildPat ty)))]
542 push_bang_into_newtype_arg _ _ cd
543 = pprPanic "push_bang_into_newtype_arg" (pprConArgs cd)
544
545 {-
546 Note [Bang patterns and newtypes]
547 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
548 For the pattern !(Just pat) we can discard the bang, because
549 the pattern is strict anyway. But for !(N pat), where
550 newtype NT = N Int
551 we definitely can't discard the bang. Trac #9844.
552
553 So what we do is to push the bang inwards, in the hope that it will
554 get discarded there. So we transform
555 !(N pat) into (N !pat)
556
557 But what if there is nothing to push the bang onto? In at least one instance
558 a user has written !(N {}) which we translate into (N !_). See #13215
559
560
561 \noindent
562 {\bf Previous @matchTwiddled@ stuff:}
563
564 Now we get to the only interesting part; note: there are choices for
565 translation [from Simon's notes]; translation~1:
566 \begin{verbatim}
567 deTwiddle [s,t] e
568 \end{verbatim}
569 returns
570 \begin{verbatim}
571 [ w = e,
572 s = case w of [s,t] -> s
573 t = case w of [s,t] -> t
574 ]
575 \end{verbatim}
576
577 Here \tr{w} is a fresh variable, and the \tr{w}-binding prevents multiple
578 evaluation of \tr{e}. An alternative translation (No.~2):
579 \begin{verbatim}
580 [ w = case e of [s,t] -> (s,t)
581 s = case w of (s,t) -> s
582 t = case w of (s,t) -> t
583 ]
584 \end{verbatim}
585
586 ************************************************************************
587 * *
588 \subsubsection[improved-unmixing]{UNIMPLEMENTED idea for improved unmixing}
589 * *
590 ************************************************************************
591
592 We might be able to optimise unmixing when confronted by
593 only-one-constructor-possible, of which tuples are the most notable
594 examples. Consider:
595 \begin{verbatim}
596 f (a,b,c) ... = ...
597 f d ... (e:f) = ...
598 f (g,h,i) ... = ...
599 f j ... = ...
600 \end{verbatim}
601 This definition would normally be unmixed into four equation blocks,
602 one per equation. But it could be unmixed into just one equation
603 block, because if the one equation matches (on the first column),
604 the others certainly will.
605
606 You have to be careful, though; the example
607 \begin{verbatim}
608 f j ... = ...
609 -------------------
610 f (a,b,c) ... = ...
611 f d ... (e:f) = ...
612 f (g,h,i) ... = ...
613 \end{verbatim}
614 {\em must} be broken into two blocks at the line shown; otherwise, you
615 are forcing unnecessary evaluation. In any case, the top-left pattern
616 always gives the cue. You could then unmix blocks into groups of...
617 \begin{description}
618 \item[all variables:]
619 As it is now.
620 \item[constructors or variables (mixed):]
621 Need to make sure the right names get bound for the variable patterns.
622 \item[literals or variables (mixed):]
623 Presumably just a variant on the constructor case (as it is now).
624 \end{description}
625
626 ************************************************************************
627 * *
628 * matchWrapper: a convenient way to call @match@ *
629 * *
630 ************************************************************************
631 \subsection[matchWrapper]{@matchWrapper@: a convenient interface to @match@}
632
633 Calls to @match@ often involve similar (non-trivial) work; that work
634 is collected here, in @matchWrapper@. This function takes as
635 arguments:
636 \begin{itemize}
637 \item
638 Typechecked @Matches@ (of a function definition, or a case or lambda
639 expression)---the main input;
640 \item
641 An error message to be inserted into any (runtime) pattern-matching
642 failure messages.
643 \end{itemize}
644
645 As results, @matchWrapper@ produces:
646 \begin{itemize}
647 \item
648 A list of variables (@Locals@) that the caller must ``promise'' to
649 bind to appropriate values; and
650 \item
651 a @CoreExpr@, the desugared output (main result).
652 \end{itemize}
653
654 The main actions of @matchWrapper@ include:
655 \begin{enumerate}
656 \item
657 Flatten the @[TypecheckedMatch]@ into a suitable list of
658 @EquationInfo@s.
659 \item
660 Create as many new variables as there are patterns in a pattern-list
661 (in any one of the @EquationInfo@s).
662 \item
663 Create a suitable ``if it fails'' expression---a call to @error@ using
664 the error-string input; the {\em type} of this fail value can be found
665 by examining one of the RHS expressions in one of the @EquationInfo@s.
666 \item
667 Call @match@ with all of this information!
668 \end{enumerate}
669 -}
670
671 matchWrapper :: HsMatchContext Name -- For shadowing warning messages
672 -> Maybe (LHsExpr GhcTc) -- The scrutinee, if we check a case expr
673 -> MatchGroup GhcTc (LHsExpr GhcTc) -- Matches being desugared
674 -> DsM ([Id], CoreExpr) -- Results
675
676 {-
677 There is one small problem with the Lambda Patterns, when somebody
678 writes something similar to:
679 \begin{verbatim}
680 (\ (x:xs) -> ...)
681 \end{verbatim}
682 he/she don't want a warning about incomplete patterns, that is done with
683 the flag @opt_WarnSimplePatterns@.
684 This problem also appears in the:
685 \begin{itemize}
686 \item @do@ patterns, but if the @do@ can fail
687 it creates another equation if the match can fail
688 (see @DsExpr.doDo@ function)
689 \item @let@ patterns, are treated by @matchSimply@
690 List Comprension Patterns, are treated by @matchSimply@ also
691 \end{itemize}
692
693 We can't call @matchSimply@ with Lambda patterns,
694 due to the fact that lambda patterns can have more than
695 one pattern, and match simply only accepts one pattern.
696
697 JJQC 30-Nov-1997
698 -}
699
700 matchWrapper ctxt mb_scr (MG { mg_alts = L _ matches
701 , mg_ext = MatchGroupTc arg_tys rhs_ty
702 , mg_origin = origin })
703 = do { dflags <- getDynFlags
704 ; locn <- getSrcSpanDs
705
706 ; new_vars <- case matches of
707 [] -> mapM newSysLocalDsNoLP arg_tys
708 (m:_) -> selectMatchVars (map unLoc (hsLMatchPats m))
709
710 ; eqns_info <- mapM (mk_eqn_info new_vars) matches
711
712 -- pattern match check warnings
713 ; unless (isGenerated origin) $
714 when (isAnyPmCheckEnabled dflags (DsMatchContext ctxt locn)) $
715 addTmCsDs (genCaseTmCs1 mb_scr new_vars) $
716 -- See Note [Type and Term Equality Propagation]
717 checkMatches dflags (DsMatchContext ctxt locn) new_vars matches
718
719 ; result_expr <- handleWarnings $
720 matchEquations ctxt new_vars eqns_info rhs_ty
721 ; return (new_vars, result_expr) }
722 where
723 mk_eqn_info vars (L _ (Match { m_pats = pats, m_grhss = grhss }))
724 = do { dflags <- getDynFlags
725 ; let upats = map (unLoc . decideBangHood dflags) pats
726 dicts = collectEvVarsPats upats
727 ; tm_cs <- genCaseTmCs2 mb_scr upats vars
728 ; match_result <- addDictsDs dicts $ -- See Note [Type and Term Equality Propagation]
729 addTmCsDs tm_cs $ -- See Note [Type and Term Equality Propagation]
730 dsGRHSs ctxt grhss rhs_ty
731 ; return (EqnInfo { eqn_pats = upats, eqn_rhs = match_result}) }
732 mk_eqn_info _ (L _ (XMatch _)) = panic "matchWrapper"
733
734 handleWarnings = if isGenerated origin
735 then discardWarningsDs
736 else id
737 matchWrapper _ _ (XMatchGroup _) = panic "matchWrapper"
738
739 matchEquations :: HsMatchContext Name
740 -> [MatchId] -> [EquationInfo] -> Type
741 -> DsM CoreExpr
742 matchEquations ctxt vars eqns_info rhs_ty
743 = do { let error_doc = matchContextErrString ctxt
744
745 ; match_result <- match vars rhs_ty eqns_info
746
747 ; fail_expr <- mkErrorAppDs pAT_ERROR_ID rhs_ty error_doc
748 ; extractMatchResult match_result fail_expr }
749
750 {-
751 ************************************************************************
752 * *
753 \subsection[matchSimply]{@matchSimply@: match a single expression against a single pattern}
754 * *
755 ************************************************************************
756
757 @mkSimpleMatch@ is a wrapper for @match@ which deals with the
758 situation where we want to match a single expression against a single
759 pattern. It returns an expression.
760 -}
761
762 matchSimply :: CoreExpr -- Scrutinee
763 -> HsMatchContext Name -- Match kind
764 -> LPat GhcTc -- Pattern it should match
765 -> CoreExpr -- Return this if it matches
766 -> CoreExpr -- Return this if it doesn't
767 -> DsM CoreExpr
768 -- Do not warn about incomplete patterns; see matchSinglePat comments
769 matchSimply scrut hs_ctx pat result_expr fail_expr = do
770 let
771 match_result = cantFailMatchResult result_expr
772 rhs_ty = exprType fail_expr
773 -- Use exprType of fail_expr, because won't refine in the case of failure!
774 match_result' <- matchSinglePat scrut hs_ctx pat rhs_ty match_result
775 extractMatchResult match_result' fail_expr
776
777 matchSinglePat :: CoreExpr -> HsMatchContext Name -> LPat GhcTc
778 -> Type -> MatchResult -> DsM MatchResult
779 -- matchSinglePat ensures that the scrutinee is a variable
780 -- and then calls match_single_pat_var
781 --
782 -- matchSinglePat does not warn about incomplete patterns
783 -- Used for things like [ e | pat <- stuff ], where
784 -- incomplete patterns are just fine
785
786 matchSinglePat (Var var) ctx pat ty match_result
787 | not (isExternalName (idName var))
788 = match_single_pat_var var ctx pat ty match_result
789
790 matchSinglePat scrut hs_ctx pat ty match_result
791 = do { var <- selectSimpleMatchVarL pat
792 ; match_result' <- match_single_pat_var var hs_ctx pat ty match_result
793 ; return (adjustMatchResult (bindNonRec var scrut) match_result') }
794
795 match_single_pat_var :: Id -- See Note [Match Ids]
796 -> HsMatchContext Name -> LPat GhcTc
797 -> Type -> MatchResult -> DsM MatchResult
798 match_single_pat_var var ctx pat ty match_result
799 = ASSERT2( isInternalName (idName var), ppr var )
800 do { dflags <- getDynFlags
801 ; locn <- getSrcSpanDs
802
803 -- Pattern match check warnings
804 ; checkSingle dflags (DsMatchContext ctx locn) var (unLoc pat)
805
806 ; let eqn_info = EqnInfo { eqn_pats = [unLoc (decideBangHood dflags pat)]
807 , eqn_rhs = match_result }
808 ; match [var] ty [eqn_info] }
809
810
811 {-
812 ************************************************************************
813 * *
814 Pattern classification
815 * *
816 ************************************************************************
817 -}
818
819 data PatGroup
820 = PgAny -- Immediate match: variables, wildcards,
821 -- lazy patterns
822 | PgCon DataCon -- Constructor patterns (incl list, tuple)
823 | PgSyn PatSyn [Type] -- See Note [Pattern synonym groups]
824 | PgLit Literal -- Literal patterns
825 | PgN Rational -- Overloaded numeric literals;
826 -- see Note [Don't use Literal for PgN]
827 | PgOverS FastString -- Overloaded string literals
828 | PgNpK Integer -- n+k patterns
829 | PgBang -- Bang patterns
830 | PgCo Type -- Coercion patterns; the type is the type
831 -- of the pattern *inside*
832 | PgView (LHsExpr GhcTc) -- view pattern (e -> p):
833 -- the LHsExpr is the expression e
834 Type -- the Type is the type of p (equivalently, the result type of e)
835 | PgOverloadedList
836
837 {- Note [Don't use Literal for PgN]
838 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
839 Previously we had, as PatGroup constructors
840
841 | ...
842 | PgN Literal -- Overloaded literals
843 | PgNpK Literal -- n+k patterns
844 | ...
845
846 But Literal is really supposed to represent an *unboxed* literal, like Int#.
847 We were sticking the literal from, say, an overloaded numeric literal pattern
848 into a MachInt constructor. This didn't really make sense; and we now have
849 the invariant that value in a MachInt must be in the range of the target
850 machine's Int# type, and an overloaded literal could meaningfully be larger.
851
852 Solution: For pattern grouping purposes, just store the literal directly in
853 the PgN constructor as a Rational if numeric, and add a PgOverStr constructor
854 for overloaded strings.
855 -}
856
857 groupEquations :: DynFlags -> [EquationInfo] -> [[(PatGroup, EquationInfo)]]
858 -- If the result is of form [g1, g2, g3],
859 -- (a) all the (pg,eq) pairs in g1 have the same pg
860 -- (b) none of the gi are empty
861 -- The ordering of equations is unchanged
862 groupEquations dflags eqns
863 = groupBy same_gp [(patGroup dflags (firstPat eqn), eqn) | eqn <- eqns]
864 where
865 same_gp :: (PatGroup,EquationInfo) -> (PatGroup,EquationInfo) -> Bool
866 (pg1,_) `same_gp` (pg2,_) = pg1 `sameGroup` pg2
867
868 subGroup :: (m -> [[EquationInfo]]) -- Map.elems
869 -> m -- Map.empty
870 -> (a -> m -> Maybe [EquationInfo]) -- Map.lookup
871 -> (a -> [EquationInfo] -> m -> m) -- Map.insert
872 -> [(a, EquationInfo)] -> [[EquationInfo]]
873 -- Input is a particular group. The result sub-groups the
874 -- equations by with particular constructor, literal etc they match.
875 -- Each sub-list in the result has the same PatGroup
876 -- See Note [Take care with pattern order]
877 -- Parameterized by map operations to allow different implementations
878 -- and constraints, eg. types without Ord instance.
879 subGroup elems empty lookup insert group
880 = map reverse $ elems $ foldl accumulate empty group
881 where
882 accumulate pg_map (pg, eqn)
883 = case lookup pg pg_map of
884 Just eqns -> insert pg (eqn:eqns) pg_map
885 Nothing -> insert pg [eqn] pg_map
886 -- pg_map :: Map a [EquationInfo]
887 -- Equations seen so far in reverse order of appearance
888
889 subGroupOrd :: Ord a => [(a, EquationInfo)] -> [[EquationInfo]]
890 subGroupOrd = subGroup Map.elems Map.empty Map.lookup Map.insert
891
892 subGroupUniq :: Uniquable a => [(a, EquationInfo)] -> [[EquationInfo]]
893 subGroupUniq =
894 subGroup eltsUDFM emptyUDFM (flip lookupUDFM) (\k v m -> addToUDFM m k v)
895
896 {- Note [Pattern synonym groups]
897 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
898 If we see
899 f (P a) = e1
900 f (P b) = e2
901 ...
902 where P is a pattern synonym, can we put (P a -> e1) and (P b -> e2) in the
903 same group? We can if P is a constructor, but /not/ if P is a pattern synonym.
904 Consider (Trac #11224)
905 -- readMaybe :: Read a => String -> Maybe a
906 pattern PRead :: Read a => () => a -> String
907 pattern PRead a <- (readMaybe -> Just a)
908
909 f (PRead (x::Int)) = e1
910 f (PRead (y::Bool)) = e2
911 This is all fine: we match the string by trying to read an Int; if that
912 fails we try to read a Bool. But clearly we can't combine the two into a single
913 match.
914
915 Conclusion: we can combine when we invoke PRead /at the same type/. Hence
916 in PgSyn we record the instantiaing types, and use them in sameGroup.
917
918 Note [Take care with pattern order]
919 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
920 In the subGroup function we must be very careful about pattern re-ordering,
921 Consider the patterns [ (True, Nothing), (False, x), (True, y) ]
922 Then in bringing together the patterns for True, we must not
923 swap the Nothing and y!
924 -}
925
926 sameGroup :: PatGroup -> PatGroup -> Bool
927 -- Same group means that a single case expression
928 -- or test will suffice to match both, *and* the order
929 -- of testing within the group is insignificant.
930 sameGroup PgAny PgAny = True
931 sameGroup PgBang PgBang = True
932 sameGroup (PgCon _) (PgCon _) = True -- One case expression
933 sameGroup (PgSyn p1 t1) (PgSyn p2 t2) = p1==p2 && eqTypes t1 t2
934 -- eqTypes: See Note [Pattern synonym groups]
935 sameGroup (PgLit _) (PgLit _) = True -- One case expression
936 sameGroup (PgN l1) (PgN l2) = l1==l2 -- Order is significant
937 sameGroup (PgOverS s1) (PgOverS s2) = s1==s2
938 sameGroup (PgNpK l1) (PgNpK l2) = l1==l2 -- See Note [Grouping overloaded literal patterns]
939 sameGroup (PgCo t1) (PgCo t2) = t1 `eqType` t2
940 -- CoPats are in the same goup only if the type of the
941 -- enclosed pattern is the same. The patterns outside the CoPat
942 -- always have the same type, so this boils down to saying that
943 -- the two coercions are identical.
944 sameGroup (PgView e1 t1) (PgView e2 t2) = viewLExprEq (e1,t1) (e2,t2)
945 -- ViewPats are in the same group iff the expressions
946 -- are "equal"---conservatively, we use syntactic equality
947 sameGroup _ _ = False
948
949 -- An approximation of syntactic equality used for determining when view
950 -- exprs are in the same group.
951 -- This function can always safely return false;
952 -- but doing so will result in the application of the view function being repeated.
953 --
954 -- Currently: compare applications of literals and variables
955 -- and anything else that we can do without involving other
956 -- HsSyn types in the recursion
957 --
958 -- NB we can't assume that the two view expressions have the same type. Consider
959 -- f (e1 -> True) = ...
960 -- f (e2 -> "hi") = ...
961 viewLExprEq :: (LHsExpr GhcTc,Type) -> (LHsExpr GhcTc,Type) -> Bool
962 viewLExprEq (e1,_) (e2,_) = lexp e1 e2
963 where
964 lexp :: LHsExpr GhcTc -> LHsExpr GhcTc -> Bool
965 lexp e e' = exp (unLoc e) (unLoc e')
966
967 ---------
968 exp :: HsExpr GhcTc -> HsExpr GhcTc -> Bool
969 -- real comparison is on HsExpr's
970 -- strip parens
971 exp (HsPar _ (L _ e)) e' = exp e e'
972 exp e (HsPar _ (L _ e')) = exp e e'
973 -- because the expressions do not necessarily have the same type,
974 -- we have to compare the wrappers
975 exp (HsWrap _ h e) (HsWrap _ h' e') = wrap h h' && exp e e'
976 exp (HsVar _ i) (HsVar _ i') = i == i'
977 exp (HsConLikeOut _ c) (HsConLikeOut _ c') = c == c'
978 -- the instance for IPName derives using the id, so this works if the
979 -- above does
980 exp (HsIPVar _ i) (HsIPVar _ i') = i == i'
981 exp (HsOverLabel _ l x) (HsOverLabel _ l' x') = l == l' && x == x'
982 exp (HsOverLit _ l) (HsOverLit _ l') =
983 -- Overloaded lits are equal if they have the same type
984 -- and the data is the same.
985 -- this is coarser than comparing the SyntaxExpr's in l and l',
986 -- which resolve the overloading (e.g., fromInteger 1),
987 -- because these expressions get written as a bunch of different variables
988 -- (presumably to improve sharing)
989 eqType (overLitType l) (overLitType l') && l == l'
990 exp (HsApp _ e1 e2) (HsApp _ e1' e2') = lexp e1 e1' && lexp e2 e2'
991 -- the fixities have been straightened out by now, so it's safe
992 -- to ignore them?
993 exp (OpApp _ l o ri) (OpApp _ l' o' ri') =
994 lexp l l' && lexp o o' && lexp ri ri'
995 exp (NegApp _ e n) (NegApp _ e' n') = lexp e e' && syn_exp n n'
996 exp (SectionL _ e1 e2) (SectionL _ e1' e2') =
997 lexp e1 e1' && lexp e2 e2'
998 exp (SectionR _ e1 e2) (SectionR _ e1' e2') =
999 lexp e1 e1' && lexp e2 e2'
1000 exp (ExplicitTuple _ es1 _) (ExplicitTuple _ es2 _) =
1001 eq_list tup_arg es1 es2
1002 exp (ExplicitSum _ _ _ e) (ExplicitSum _ _ _ e') = lexp e e'
1003 exp (HsIf _ _ e e1 e2) (HsIf _ _ e' e1' e2') =
1004 lexp e e' && lexp e1 e1' && lexp e2 e2'
1005
1006 -- Enhancement: could implement equality for more expressions
1007 -- if it seems useful
1008 -- But no need for HsLit, ExplicitList, ExplicitTuple,
1009 -- because they cannot be functions
1010 exp _ _ = False
1011
1012 ---------
1013 syn_exp :: SyntaxExpr GhcTc -> SyntaxExpr GhcTc -> Bool
1014 syn_exp (SyntaxExpr { syn_expr = expr1
1015 , syn_arg_wraps = arg_wraps1
1016 , syn_res_wrap = res_wrap1 })
1017 (SyntaxExpr { syn_expr = expr2
1018 , syn_arg_wraps = arg_wraps2
1019 , syn_res_wrap = res_wrap2 })
1020 = exp expr1 expr2 &&
1021 and (zipWithEqual "viewLExprEq" wrap arg_wraps1 arg_wraps2) &&
1022 wrap res_wrap1 res_wrap2
1023
1024 ---------
1025 tup_arg (L _ (Present _ e1)) (L _ (Present _ e2)) = lexp e1 e2
1026 tup_arg (L _ (Missing t1)) (L _ (Missing t2)) = eqType t1 t2
1027 tup_arg _ _ = False
1028
1029 ---------
1030 wrap :: HsWrapper -> HsWrapper -> Bool
1031 -- Conservative, in that it demands that wrappers be
1032 -- syntactically identical and doesn't look under binders
1033 --
1034 -- Coarser notions of equality are possible
1035 -- (e.g., reassociating compositions,
1036 -- equating different ways of writing a coercion)
1037 wrap WpHole WpHole = True
1038 wrap (WpCompose w1 w2) (WpCompose w1' w2') = wrap w1 w1' && wrap w2 w2'
1039 wrap (WpFun w1 w2 _ _) (WpFun w1' w2' _ _) = wrap w1 w1' && wrap w2 w2'
1040 wrap (WpCast co) (WpCast co') = co `eqCoercion` co'
1041 wrap (WpEvApp et1) (WpEvApp et2) = et1 `ev_term` et2
1042 wrap (WpTyApp t) (WpTyApp t') = eqType t t'
1043 -- Enhancement: could implement equality for more wrappers
1044 -- if it seems useful (lams and lets)
1045 wrap _ _ = False
1046
1047 ---------
1048 ev_term :: EvTerm -> EvTerm -> Bool
1049 ev_term (EvExpr (Var a)) (EvExpr (Var b)) = a==b
1050 ev_term (EvExpr (Coercion a)) (EvExpr (Coercion b)) = a `eqCoercion` b
1051 ev_term _ _ = False
1052
1053 ---------
1054 eq_list :: (a->a->Bool) -> [a] -> [a] -> Bool
1055 eq_list _ [] [] = True
1056 eq_list _ [] (_:_) = False
1057 eq_list _ (_:_) [] = False
1058 eq_list eq (x:xs) (y:ys) = eq x y && eq_list eq xs ys
1059
1060 patGroup :: DynFlags -> Pat GhcTc -> PatGroup
1061 patGroup _ (ConPatOut { pat_con = L _ con
1062 , pat_arg_tys = tys })
1063 | RealDataCon dcon <- con = PgCon dcon
1064 | PatSynCon psyn <- con = PgSyn psyn tys
1065 patGroup _ (WildPat {}) = PgAny
1066 patGroup _ (BangPat {}) = PgBang
1067 patGroup _ (NPat _ (L _ OverLit {ol_val=oval}) mb_neg _) =
1068 case (oval, isJust mb_neg) of
1069 (HsIntegral i, False) -> PgN (fromInteger (il_value i))
1070 (HsIntegral i, True ) -> PgN (-fromInteger (il_value i))
1071 (HsFractional r, False) -> PgN (fl_value r)
1072 (HsFractional r, True ) -> PgN (-fl_value r)
1073 (HsIsString _ s, _) -> ASSERT(isNothing mb_neg)
1074 PgOverS s
1075 patGroup _ (NPlusKPat _ _ (L _ OverLit {ol_val=oval}) _ _ _) =
1076 case oval of
1077 HsIntegral i -> PgNpK (il_value i)
1078 _ -> pprPanic "patGroup NPlusKPat" (ppr oval)
1079 patGroup _ (CoPat _ _ p _) = PgCo (hsPatType p)
1080 -- Type of innelexp pattern
1081 patGroup _ (ViewPat _ expr p) = PgView expr (hsPatType (unLoc p))
1082 patGroup _ (ListPat (ListPatTc _ (Just _)) _) = PgOverloadedList
1083 patGroup dflags (LitPat _ lit) = PgLit (hsLitKey dflags lit)
1084 patGroup _ pat = pprPanic "patGroup" (ppr pat)
1085
1086 {-
1087 Note [Grouping overloaded literal patterns]
1088 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1089 WATCH OUT! Consider
1090
1091 f (n+1) = ...
1092 f (n+2) = ...
1093 f (n+1) = ...
1094
1095 We can't group the first and third together, because the second may match
1096 the same thing as the first. Same goes for *overloaded* literal patterns
1097 f 1 True = ...
1098 f 2 False = ...
1099 f 1 False = ...
1100 If the first arg matches '1' but the second does not match 'True', we
1101 cannot jump to the third equation! Because the same argument might
1102 match '2'!
1103 Hence we don't regard 1 and 2, or (n+1) and (n+2), as part of the same group.
1104 -}