[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:  7.8.4
             Component:              |          Version:  7.8.3
  libraries/base                     |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Easy (less than 1
  Unknown/Multiple                   |  hour)
       Type of failure:  Runtime     |       Blocked By:
  performance bug                    |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by nomeata):

 Replying to [comment:4 dfeuer]:
 > Replying to [comment:1 nomeata]:
 >
 > > I would find it strange to add such complexity “just for” `inits`.
 Now, if we had such a `Queue` type (which looks useful in general) in base
 anyways, using it would be a different story...
 >
 > If it were added, it wouldn't be called `Queue`, because (unlike the
 real banker's queue) it's actually incapable of implementing `uncons`
 efficiently. It's really just a very limited, but very fast and light,
 list builder. If it's useful for things other than implementing `inits`, I
 would not be opposed to adding it in a separate module with some
 sufficiently clear name. I don't know enough about what sorts of things
 should and should not be provided by base to really comment much beyond
 that.

 After reading more of the code I agree that this not too big “just for”
 inits, and I’m in favor of adding it.

 I also thought about ways to make it even faster. In particular, I tried
 to make `GHC` get rid of `Queue` and simply pass the three values around
 as arguments to the inner loop, and also make this fuse. With this
 definition it works:

 {{{
 myScanl' :: (b -> a -> b) -> b -> [a] -> [b]
 myScanl' f a bs = build $ \c n ->
     a `seq` a `c`
     foldr (\b g x -> (let b' = f x b in b' `seq` (b' `c` g b')))
           (\b -> b `seq` n)
           bs
           a

 initsQ2 :: [a] -> [[a]]
 initsQ2 = map toListQ . myScanl' snocQ emptyQ
 }}}

 and yields consistently better results than `initsQ`. (See attached
 report, `initsQ2`. Ignore `initsQDL`, thats the same, but with the rear
 list implemented as a difference list, which makes little difference.)

 This raises the question whether we want such a fusing strict `scanl'` in
 `Data.List` as well – it turned out to be useful here.

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