+Note [Desugaring explicit lists]
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+Explicit lists are desugared in a cleverer way to prevent some
+fruitless allocations. Essentially, whenever we see a list literal
+[x_1, ..., x_n] we:
+
+1. Find the tail of the list that can be allocated statically (say
+ [x_k, ..., x_n]) by later stages and ensure we desugar that
+ normally: this makes sure that we don't cause a code size increase
+ by having the cons in that expression fused (see later) and hence
+ being unable to statically allocate any more
+
+2. For the prefix of the list which cannot be allocated statically,
+ say [x_1, ..., x_(k-1)], we turn it into an expression involving
+ build so that if we find any foldrs over it it will fuse away
+ entirely!
+
+ So in this example we will desugar to:
+ build (\c n -> x_1 `c` x_2 `c` .... `c` foldr c n [x_k, ..., x_n]
+
+ If fusion fails to occur then build will get inlined and (since we
+ defined a RULE for foldr (:) []) we will get back exactly the
+ normal desugaring for an explicit list.
+
+This optimisation can be worth a lot: up to 25% of the total
+allocation in some nofib programs. Specifically
+
+ Program Size Allocs Runtime CompTime
+ rewrite +0.0% -26.3% 0.02 -1.8%
+ ansi -0.3% -13.8% 0.00 +0.0%
+ lift +0.0% -8.7% 0.00 -2.3%
+
+Of course, if rules aren't turned on then there is pretty much no
+point doing this fancy stuff, and it may even be harmful.
+
+=======> Note by SLPJ Dec 08.
+
+I'm unconvinced that we should *ever* generate a build for an explicit
+list. See the comments in GHC.Base about the foldr/cons rule, which
+points out that (foldr k z [a,b,c]) may generate *much* less code than
+(a `k` b `k` c `k` z).
+
+Furthermore generating builds messes up the LHS of RULES.
+Example: the foldr/single rule in GHC.Base
+ foldr k z [x] = ...
+We do not want to generate a build invocation on the LHS of this RULE!
+
+We fix this by disabling rules in rule LHSs, and testing that
+flag here; see Note [Desugaring RULE left hand sides] in Desugar
+
+To test this I've added a (static) flag -fsimple-list-literals, which
+makes all list literals be generated via the simple route.
+
+
+\begin{code}
+dsExplicitList :: PostTcType -> [LHsExpr Id] -> DsM CoreExpr
+-- See Note [Desugaring explicit lists]
+dsExplicitList elt_ty xs
+ = do { dflags <- getDOptsDs
+ ; xs' <- mapM dsLExpr xs
+ ; let (dynamic_prefix, static_suffix) = spanTail is_static xs'
+ ; if opt_SimpleListLiterals -- -fsimple-list-literals
+ || not (dopt Opt_EnableRewriteRules dflags) -- Rewrite rules off
+ -- Don't generate a build if there are no rules to eliminate it!
+ -- See Note [Desugaring RULE left hand sides] in Desugar
+ || null dynamic_prefix -- Avoid build (\c n. foldr c n xs)!
+ then return $ mkListExpr elt_ty xs'
+ else mkBuildExpr elt_ty (mkSplitExplicitList dynamic_prefix static_suffix) }
+ where
+ is_static :: CoreExpr -> Bool
+ is_static e = all is_static_var (varSetElems (exprFreeVars e))
+
+ is_static_var :: Var -> Bool
+ is_static_var v
+ | isId v = isExternalName (idName v) -- Top-level things are given external names
+ | otherwise = False -- Type variables
+
+ mkSplitExplicitList prefix suffix (c, _) (n, n_ty)
+ = do { let suffix' = mkListExpr elt_ty suffix
+ ; folded_suffix <- mkFoldrExpr elt_ty n_ty (Var c) (Var n) suffix'
+ ; return (foldr (App . App (Var c)) folded_suffix prefix) }
+
+spanTail :: (a -> Bool) -> [a] -> ([a], [a])
+spanTail f xs = (reverse rejected, reverse satisfying)
+ where (satisfying, rejected) = span f $ reverse xs
+\end{code}
+