Speeding up Data.List.inits

[Edward Kmett]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140719/1b7f1212/attachment-0001.html>