[GHC] #9345: Data.List.inits is extremely slow

[GHC]

#9345: Data.List.inits is extremely slow
-------------------------------------+-------------------------------------
        Reporter:  dfeuer            |                   Owner:
            Type:  bug               |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  libraries/base    |                 Version:  7.8.3
        Keywords:                    |  Differential Revisions:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |              Difficulty:  Easy (less
       Test Case:                    |  than 1 hour)
        Blocking:                    |              Blocked By:
                                     |         Related Tickets:
-------------------------------------+-------------------------------------
 As discussed on libraries at haskell.org, `Data.List.inits` is extremely slow
 (try running `print $ length $ inits [1..100000]` if you don't believe
 me). As discussed, there are at least two reasonable fixes. One of them
 (named `initsR` in the attached) is a one-liner and gives very good
 performance in general, but poor performance in certain cases that may or
 may not appear in real code. The other (named `initsQ` in the attached) is
 slightly more complex and slightly slower in general, but its performance
 appears to be robust. I would personally lean toward `initsQ` for
 `Data.List`.

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