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,
#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]: 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