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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
