[Haskell-cafe] Progress on shootout entries

[Jan-Willem Maessen]

On Jan 4, 2006, at 8:11 AM, Chris Kuklewicz wrote:

> Krasimir Angelov wrote:
>> ...
>> In this particular case the flop function is very slow.
>> ...
>> It can be optimized using a new mangle function:
>>
>> mangle :: Int -> [a] -> [a]
>> mangle m xs = xs'
>>   where
>>     (rs,xs') = splitAt m xs rs
>>
>>     splitAt :: Int -> [a] -> [a] -> ([a], [a])
>>     splitAt 0    xs  ys = (xs,ys)
>>     splitAt _    []  ys = ([],ys)
>>     splitAt m (x:xs) ys = splitAt (m - 1) xs (x:ys)
>>
>> The mangle function transforms the list in one step while the  
>> original
>> implementation is using reverse, (++) and splitAt. With this function
>> the new flop is:
>>
>> flop :: Int8 -> [Int8] -> Int8
>> flop acc (1:xs) = acc
>> flop acc list@(x:xs) = flop (acc+1) (mangle (fromIntegral x) list)
>
> You seem to have also discovered the fast way to flop.
>
> This benchmarks exactly as fast as the similar entry assembled by
> Bertram Felgenhauer using Jan-Willem Maessen's flop code:
>
>> ...
>> flop :: Int -> [Int] -> [Int]
>> flop n xs = rs
>>   where (rs, ys) = fl n xs ys
>>         fl 0 xs     ys = (ys, xs)
>>         fl n (x:xs) ys = fl (n-1) xs (x:ys)

Indeed, I believe these are isomorphic.  My "fl" function is the  
"splitAt" function above, perhaps more descriptively named  
"splitAtAndReverseAppend"...

-Jan-Willem Maessen