Am 19.07.2014 09:51, schrieb David Feuer:

Background: I was looking at the code for Data.List.inits in
base-4.7.0.0 (function renamed for clarity):

initsDL                   :: [a] -> [[a]]
initsDL xs                =  [] : case xs of
                                   []      -> []
                                   x : xs' -> map (x :) (initsDL xs')

The recursive maps made me suspicious. I decided to try writing a
different version:

initsHO xs = map ($ []) (scanl q id xs)
   where
     q f x = f . (x:)

I mentioned this on #haskell and noted that it would be a nice exercise
to write it with less fancy function footwork using map reverse. rasfar
responded (modulo naming) with

initsR xs = map reverse (scanl q [] xs)
   where
     q acc x = x : acc

The 'map' gives efficient access to the first elements of the sub-lists, thus it seems that initsDL is faster than initsR when you access only prefixes of the sub-lists. E.g.

Prelude> head $ last $ inits [0..10000000::Int]