[GHC] #915: Implement list fusion using streams instead of foldr/build

[GHC]

#915: Implement list fusion using streams instead of foldr/build
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  (none)
            Type:  task              |               Status:  closed
        Priority:  normal            |            Milestone:  7.6.1
       Component:  libraries/base    |              Version:  6.8
      Resolution:  invalid           |             Keywords:  fusion
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:  N/A
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by sgraf):

 On my journey through fusion land, I fell in love with the idea of stream
 fusion and spent quite some time thinking about the `concatMap` problem.

 Apart from the HERMIT approach based on rewriting a (albeit large) subset
 of `concatMap` calls, I think the solution lies in call-pattern
 specialisation of function arguments, as already recognised in section 6.2
 of the [https://www.microsoft.com/en-us/research/wp-
 content/uploads/2016/07/spec-constr.pdf original paper on call-pattern
 specialisation].

 The paper goes on to argue that it's too brittle to have rules matching on
 lambda terms. But then again, I don't see why we even need a RULE matching
 on a specific lambda term (or even terms with `exprArity` > 0), as these
 things are pretty much unique everytime they occur. E.g., having a RULE
 deduplicate specialisations would probably not help much anyway. So, if we
 would employ some other mechanism than rewrite rules to specialise call
 sites, as I understand `SpecConstr` currently does, I think we would be
 fine, wouldn't we?

 At least this could get rid of the `concatMap` roadblock, are there any
 others I'm not aware of?

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/915#comment:48>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler