[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:                            
        Type:  task              |       Status:  new                       
    Priority:  normal            |    Milestone:  6.12 branch               
   Component:  libraries/base    |      Version:  6.8                       
    Keywords:  fusion            |   Difficulty:  Project (more than a week)
          Os:  Unknown/Multiple  |     Testcase:  N/A                       
Architecture:  Unknown/Multiple  |      Failure:  None/Unknown              
---------------------------------+------------------------------------------

Comment(by batterseapower):

 AFAIK this ticket is no closer to being practical now that when dons added
 that comment 18 months ago. To implement it you need to change:

    * The list libraries, to use Stream based definitions
    * The desugaring for list comprehensions in GHC

 However, it is still the case that noone knows how to implement concat /
 concatMap efficiently and without improving GHCs Core optimisers. Since
 concatMap is crucial to the the desugaring of list comprehensions, and
 also kind of important to users generally, stream fusion isn't really
 ready for prime time yet, IMHO.

 An alternative to coming up with a clever library modification would be to
 improve GHCs optimiser. I found that the suggested approach of running a
 SAT pass in a fixed point loop with constructor specialisation was fairly
 reliable, but I haven't got around to either committing my improved SAT
 pass or making the fixed point I used not so much of a hack. Even if I did
 so, it is upsetting that stream fusion requires so much more work on the
 part of the optimiser to get right, compared to the fairly simply rewrite
 rule story with foldr/build.

 (Both approaches suffer from fragility in the face of a lack of INLINE
 pragmas).

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