Speeding up Data.List.inits

[Henning Thielemann]

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]