inits

[Chris Kuklewicz]

Tim Toorop wrote:
> Chris Kuklewicz wrote:
>> Ross Paterson wrote:
>>  
>>> On Mon, Apr 10, 2006 at 03:54:09PM +0100, Chris Kuklewicz wrote:
>>>    
>>>> If the goal is speed, then this definition is running over 10%
>>>> faster with ghc
>>>> -O2 on my powerbook for (sum $ map length $ inits [1..10000])
>>>>
>>>> inits' = helper id
>>>>     where helper f [] = (f []):[]
>>>>           helper f (x:xs) = (f []):helper (f.(x:)) xs
>>>>       
>>> I rather like
>>>
>>>     inits = map ($ []) . scanl (.) id . map (:)
>>>
>>>     
>>
>> That takes 3 times longer than the helper function definition. 
>> Barring fusion,
>> it is creating an extra list.  The "scanl" makes a list, the "map"
>> makes a list
>> and the "(f [])" makes a list.
>>
>> The helper function makes a list with "(f[])" and with "(...):helper...".
>>
>>  
>>> but this is also competitive:
>>>
>>>     inits = map reverse . scanl (flip (:)) []
>>>
>>>     
>>
>> I would never try "reverse" when looking for performance, but that
>> runs at the
>> same speed as the helper and allocates the same amount of space.
>>
>>   
> I think we need to create a test case or something, before we say one
> function is better then the other.

Defining best is tricky.  That is why I told everyone my usage was (sum $ map
length $ inits [1..10000]).

> Just like with the helper function.  The originally proposed function is
> sometimes a tad faster then the helper function.
> And sometimes very much slower.

Could you tell me what your usage is?

> So we need to know what is important in the use of inits.

I am going out on a limb here and say : The usage metric must consume all of the
output of inits.

If someone wants
(1) less than all the output of inits, and
(2) wants the highest performance
then they should consider writing a more specialized function to use instead of
inits.

If someone wants
(1) all of the output of inits
(2) wants the highest performance
then they should not have to replace the inits in Data.List

> And then see which one is faster with probably -O2 added.

Testing performance without -O2 is interesting, but anyone who cares whether
Data.List.inits gets replaced will be using optimizations.

> Because the functions seem act very differently in the ghci (VERY!)

Of course.

> 
> -- 
> Tim Toorop
>