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]