Good catch, the common inits and tails version of subsequences makes pretty heavy use of that, as do many of the uses of inits where you use it to get k-element substrings.

I'd be curious if an okasaki-style catenable output restricted deque could recover both efficient head access and reasonably efficient appends, but the overhead of that is probably way out of line with the performance at stake!

-Edward

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]

_______________________________________________
Libraries mailing list
Libraries@haskell.org
http://www.haskell.org/mailman/listinfo/libraries