Desugaring list comprehensions and array comprehensions
\begin{code}
-{-# OPTIONS -w #-}
+{-# OPTIONS -fno-warn-incomplete-patterns #-}
-- The above warning supression flag is a temporary kludge.
-- While working on this module you are encouraged to remove it and fix
-- any warnings in the module. See
import {-# SOURCE #-} DsExpr ( dsLExpr, dsLocalBinds )
-import BasicTypes
import HsSyn
import TcHsSyn
import CoreSyn
+import MkCore
import DsMonad -- the monadery used in the desugarer
import DsUtils
import DynFlags
import CoreUtils
-import Var
+import Id
import Type
-import TysPrim
import TysWiredIn
import Match
import PrelNames
import PrelInfo
import SrcLoc
-import Panic
import Outputable
-
-import Control.Monad ( liftM2 )
+import FastString
\end{code}
List comprehensions may be desugared in one of two ways: ``ordinary''
dflags <- getDOptsDs
let quals = map unLoc lquals
- if not (dopt Opt_RewriteRules dflags) || dopt Opt_IgnoreInterfacePragmas dflags
+ if not (dopt Opt_EnableRewriteRules dflags) || dopt Opt_IgnoreInterfacePragmas dflags
-- Either rules are switched off, or we are ignoring what there are;
-- Either way foldr/build won't happen, so use the more efficient
-- Wadler-style desugaring
|| isParallelComp quals
-- Foldr-style desugaring can't handle parallel list comprehensions
then deListComp quals body (mkNilExpr elt_ty)
- else do -- Foldr/build should be enabled, so desugar
- -- into foldrs and builds
- [n_tyvar] <- newTyVarsDs [alphaTyVar]
-
- let n_ty = mkTyVarTy n_tyvar
- c_ty = mkFunTys [elt_ty, n_ty] n_ty
- [c, n] <- newSysLocalsDs [c_ty, n_ty]
-
- result <- dfListComp c n quals body
- build_id <- dsLookupGlobalId buildName
- return (Var build_id `App` Type elt_ty `App` mkLams [n_tyvar, c, n] result)
+ else mkBuildExpr elt_ty (\(c, _) (n, _) -> dfListComp c n quals body)
+ -- Foldr/build should be enabled, so desugar
+ -- into foldrs and builds
where
-- We must test for ParStmt anywhere, not just at the head, because an extension
-- Given such a statement it gives you back an expression representing how to compute the transformed
-- list and the tuple that you need to bind from that list in order to proceed with your desugaring
dsTransformStmt :: Stmt Id -> DsM (CoreExpr, LPat Id)
-dsTransformStmt (TransformStmt (stmts, binders) usingExpr maybeByExpr) = do
+dsTransformStmt (TransformStmt stmts binders usingExpr maybeByExpr) = do
(expr, binders_tuple_type) <- dsInnerListComp (stmts, binders)
usingExpr' <- dsLExpr usingExpr
-- Given such a statement it gives you back an expression representing how to compute the transformed
-- list and the tuple that you need to bind from that list in order to proceed with your desugaring
dsGroupStmt :: Stmt Id -> DsM (CoreExpr, LPat Id)
-dsGroupStmt (GroupStmt (stmts, binderMap) groupByClause) = do
+dsGroupStmt (GroupStmt stmts binderMap by using) = do
let (fromBinders, toBinders) = unzip binderMap
fromBindersTypes = map idType fromBinders
toBindersTupleType = mkBigCoreTupTy toBindersTypes
-- Desugar an inner comprehension which outputs a list of tuples of the "from" binders
- (expr, fromBindersTupleType) <- dsInnerListComp (stmts, fromBinders)
+ (expr, from_tup_ty) <- dsInnerListComp (stmts, fromBinders)
-- Work out what arguments should be supplied to that expression: i.e. is an extraction
-- function required? If so, create that desugared function and add to arguments
- (usingExpr', usingArgs) <-
- case groupByClause of
- GroupByNothing usingExpr -> liftM2 (,) (dsLExpr usingExpr) (return [expr])
- GroupBySomething usingExpr byExpr -> do
- usingExpr' <- dsLExpr (either id noLoc usingExpr)
-
- byExpr' <- dsLExpr byExpr
-
- us <- newUniqueSupply
- [fromBindersTuple] <- newSysLocalsDs [fromBindersTupleType]
- let byExprWrapper = mkTupleCase us fromBinders byExpr' fromBindersTuple (Var fromBindersTuple)
-
- return (usingExpr', [Lam fromBindersTuple byExprWrapper, expr])
+ usingExpr' <- dsLExpr (either id noLoc using)
+ usingArgs <- case by of
+ Nothing -> return [expr]
+ Just by_e -> do { by_e' <- dsLExpr by_e
+ ; us <- newUniqueSupply
+ ; [from_tup_id] <- newSysLocalsDs [from_tup_ty]
+ ; let by_wrap = mkTupleCase us fromBinders by_e'
+ from_tup_id (Var from_tup_id)
+ ; return [Lam from_tup_id by_wrap, expr] }
-- Create an unzip function for the appropriate arity and element types and find "map"
(unzip_fn, unzip_rhs) <- mkUnzipBind fromBindersTypes
-- Generate the expressions to build the grouped list
let -- First we apply the grouping function to the inner list
- inner_list_expr = mkApps usingExpr' ((Type fromBindersTupleType) : usingArgs)
+ inner_list_expr = mkApps usingExpr' ((Type from_tup_ty) : usingArgs)
-- Then we map our "unzip" across it to turn the lists of tuples into tuples of lists
-- We make sure we instantiate the type variable "a" to be a list of "from" tuples and
-- the "b" to be a tuple of "to" lists!
unzipped_inner_list_expr = mkApps (Var map_id)
- [Type (mkListTy fromBindersTupleType), Type toBindersTupleType, Var unzip_fn, inner_list_expr]
+ [Type (mkListTy from_tup_ty), Type toBindersTupleType, Var unzip_fn, inner_list_expr]
-- Then finally we bind the unzip function around that expression
bound_unzipped_inner_list_expr = Let (Rec [(unzip_fn, unzip_rhs)]) unzipped_inner_list_expr
core_rest <- deListComp quals body list
dsLocalBinds binds core_rest
-deListComp (stmt@(TransformStmt _ _ _) : quals) body list = do
+deListComp (stmt@(TransformStmt {}) : quals) body list = do
(inner_list_expr, pat) <- dsTransformStmt stmt
deBindComp pat inner_list_expr quals body list
-deListComp (stmt@(GroupStmt _ _) : quals) body list = do
+deListComp (stmt@(GroupStmt {}) : quals) body list = do
(inner_list_expr, pat) <- dsGroupStmt stmt
deBindComp pat inner_list_expr quals body list
\begin{code}
+deBindComp :: OutPat Id
+ -> CoreExpr
+ -> [Stmt Id]
+ -> LHsExpr Id
+ -> CoreExpr
+ -> DsM (Expr Id)
deBindComp pat core_list1 quals body core_list2 = do
let
u3_ty@u1_ty = exprType core_list1 -- two names, same thing
core_rest <- dfListComp c_id n_id quals body
dsLocalBinds binds core_rest
-dfListComp c_id n_id (stmt@(TransformStmt _ _ _) : quals) body = do
+dfListComp c_id n_id (stmt@(TransformStmt {}) : quals) body = do
(inner_list_expr, pat) <- dsTransformStmt stmt
-- Anyway, we bind the newly transformed list via the generic binding function
dfBindComp c_id n_id (pat, inner_list_expr) quals body
-dfListComp c_id n_id (stmt@(GroupStmt _ _) : quals) body = do
+dfListComp c_id n_id (stmt@(GroupStmt {}) : quals) body = do
(inner_list_expr, pat) <- dsGroupStmt stmt
-- Anyway, we bind the newly grouped list via the generic binding function
dfBindComp c_id n_id (pat, inner_list_expr) quals body
pat core_rest (Var b)
-- now build the outermost foldr, and return
- foldr_id <- dsLookupGlobalId foldrName
- return (Var foldr_id `App` Type x_ty
- `App` Type b_ty
- `App` mkLams [x, b] core_expr
- `App` Var n_id
- `App` core_list1)
-
+ mkFoldrExpr x_ty b_ty (mkLams [x, b] core_expr) (Var n_id) core_list1
\end{code}
%************************************************************************
unzip_fn <- newSysLocalDs unzip_fn_ty
- foldr_id <- dsLookupGlobalId foldrName
[us1, us2] <- sequence [newUniqueSupply, newUniqueSupply]
let nil_tuple = mkBigCoreTup (map mkNilExpr elt_tys)
folder_body_outer_case = mkTupleCase us2 xs folder_body_inner_case ax (Var ax)
folder_body = mkLams [ax, axs] folder_body_outer_case
- unzip_body = mkApps (Var foldr_id) [Type elt_tuple_ty, Type elt_list_tuple_ty, folder_body, nil_tuple, Var ys]
- unzip_body_saturated = mkLams [ys] unzip_body
-
- return (unzip_fn, unzip_body_saturated)
+ unzip_body <- mkFoldrExpr elt_tuple_ty elt_list_tuple_ty folder_body nil_tuple (Var ys)
+ return (unzip_fn, mkLams [ys] unzip_body)
where
elt_tuple_ty = mkBigCoreTupTy elt_tys
elt_tuple_list_ty = mkListTy elt_tuple_ty
-> DsM CoreExpr
dsPArrComp [ParStmt qss] body _ = -- parallel comprehension
dePArrParComp qss body
+
+-- Special case for simple generators:
+--
+-- <<[:e' | p <- e, qs:]>> = <<[: e' | qs :]>> p e
+--
+-- if matching again p cannot fail, or else
+--
+-- <<[:e' | p <- e, qs:]>> =
+-- <<[:e' | qs:]>> p (filterP (\x -> case x of {p -> True; _ -> False}) e)
+--
+dsPArrComp (BindStmt p e _ _ : qs) body _ = do
+ filterP <- dsLookupGlobalId filterPName
+ ce <- dsLExpr e
+ let ety'ce = parrElemType ce
+ false = Var falseDataConId
+ true = Var trueDataConId
+ v <- newSysLocalDs ety'ce
+ pred <- matchSimply (Var v) (StmtCtxt PArrComp) p true false
+ let gen | isIrrefutableHsPat p = ce
+ | otherwise = mkApps (Var filterP) [Type ety'ce, mkLams [v] pred, ce]
+ dePArrComp qs body p gen
+
dsPArrComp qs body _ = do -- no ParStmt in `qs'
sglP <- dsLookupGlobalId singletonPName
let unitArray = mkApps (Var sglP) [Type unitTy, mkCoreTup []]
- dePArrComp qs body (mkLHsPatTup []) unitArray
+ dePArrComp qs body (noLoc $ WildPat unitTy) unitArray
--
dePArrComp (LetStmt ds : qs) body pa cea = do
mapP <- dsLookupGlobalId mapPName
- let xs = map unLoc (collectLocalBinders ds)
+ let xs = collectLocalBinders ds
ty'cea = parrElemType cea
v <- newSysLocalDs ty'cea
clet <- dsLocalBinds ds (mkCoreTup (map Var xs))
let'v <- newSysLocalDs (exprType clet)
- let projBody = mkDsLet (NonRec let'v clet) $
+ let projBody = mkCoreLet (NonRec let'v clet) $
mkCoreTup [Var v, Var let'v]
errTy = exprType projBody
- errMsg = "DsListComp.dePArrComp: internal error!"
+ errMsg = ptext (sLit "DsListComp.dePArrComp: internal error!")
cerr <- mkErrorAppDs pAT_ERROR_ID errTy errMsg
ccase <- matchSimply (Var v) (StmtCtxt PArrComp) pa projBody cerr
let pa' = mkLHsPatTup [pa, mkLHsPatTup (map nlVarPat xs)]
-- where
-- {x_1, ..., x_n} = DV (qs)
--
+dePArrParComp :: [([LStmt Id], [Id])] -> LHsExpr Id -> DsM CoreExpr
dePArrParComp qss body = do
(pQss, ceQss) <- deParStmt qss
dePArrComp [] body pQss ceQss
-- empty parallel statement lists have no source representation
panic "DsListComp.dePArrComp: Empty parallel list comprehension"
deParStmt ((qs, xs):qss) = do -- first statement
- let res_expr = mkLHsVarTup xs
+ let res_expr = mkLHsVarTuple xs
cqs <- dsPArrComp (map unLoc qs) res_expr undefined
parStmts qss (mkLHsVarPatTup xs) cqs
---
zipP <- dsLookupGlobalId zipPName
let pa' = mkLHsPatTup [pa, mkLHsVarPatTup xs]
ty'cea = parrElemType cea
- res_expr = mkLHsVarTup xs
+ res_expr = mkLHsVarTuple xs
cqs <- dsPArrComp (map unLoc qs) res_expr undefined
let ty'cqs = parrElemType cqs
cea' = mkApps (Var zipP) [Type ty'cea, Type ty'cqs, cea, cqs]
-> DsM (CoreExpr, Type)
mkLambda ty p ce = do
v <- newSysLocalDs ty
- let errMsg = do "DsListComp.deLambda: internal error!"
+ let errMsg = ptext (sLit "DsListComp.deLambda: internal error!")
ce'ty = exprType ce
cerr <- mkErrorAppDs pAT_ERROR_ID ce'ty errMsg
res <- matchSimply (Var v) (StmtCtxt PArrComp) p ce cerr