Speeding up Data.List.inits

[David Feuer]

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 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]
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140719/26d0e06b/attachment.html>