I'm not sure about the theory of it, but if I load the module in GHCi and run head $ last $ initsR [0..100000::Int] I get a response *immediately*. If I run head $ last $ initsDL [0..100000::Int] I wrote this email while waiting for that to complete, and gave up on it. There may be an asymptotic performance bug here. On Sat, Jul 19, 2014 at 4:14 AM, Henning Thielemann < schlepptop@henning-thielemann.de> wrote:
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]