inits

[Tim Toorop]

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.
Just like with the helper function.  The originally proposed function is 
sometimes a tad faster then the helper function.
And sometimes very much slower.
So we need to know what is important in the use of inits.
And then see which one is faster with probably -O2 added.
Because the functions seem act very differently in the ghci (VERY!)

--
Tim Toorop