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