Actually, presumably you meant:
reverse2 ys (x:xs) = reverse2 (x:ys) xs
(stupid cut & paste late at night). with this fix (and now we actually are reversing the list with reverse2), we get the following timings for reverse2: 11:49pm enescu:~/ time a.out 2000000 4.64u 0.31s 0:05.18 95.5% 11:49pm enescu:~/ time a.out 2000000 4.87u 0.25s 0:06.23 82.1% which seems to say they perform comparably, as we would expect. sorry for freaking out earlier :) - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume On Wed, 6 Feb 2002, Hal Daume III wrote:
Well, I assume you meant:
reverse1 [] ys = ys reverse1 (x:xs) ys = reverse1 xs (x:ys)
reverse2 ys [] = ys reverse2 ys (x:xs) = reverse1 (x:ys) xs
If so, and you make two programs:
main = print (length $! reverse1 [1..2000000] [])
and
main = print (length $! reverse2 [] [1..2000000])
compile them with ghc -O2 -fvia-c, and time them we get:
FOR REVERSE1:
11:42pm enescu:~/ time a.out 2000000 4.84u 0.28s 0:06.01 85.1% 11:42pm enescu:~/ time a.out 2000000 4.71u 0.24s 0:05.25 94.2%
FOR REVERSE2:
11:43pm enescu:~/ time a.out 2000000 1.00u 0.03s 0:01.09 94.4% 11:43pm enescu:~/ time a.out 2000000 0.99u 0.01s 0:00.99 101.0%
curiously, REVERSE2 did significantly better; I have no idea why. Perhaps one of the Simons could comment on this. Moreover, if this is a general phenomenon, why doesn't GHC simply permute the order of parameters to allow it to optimize best?
Regards,
Hal
-- Hal Daume III
"Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
On Wed, 6 Feb 2002, [iso-8859-1] Jos� Romildo Malaquias wrote:
Hello.
Please, tell me which set of definitions below should I expected to be more efficient: the reverse1 or the reverse2 functions.
reverse1 [] ys = ys reverse1 (x:xs) ys = reverse2 (x:ys) xs
reverse2 ys [] = ys reverse2 ys (x:xs) = reverse2 (x:ys) xs
The difference rely on the position of the argument in which the pattern matching is done in the function definition.
Regards.
Romildo -- Prof. Jos� Romildo Malaquias Departamento de Computa��o http://iceb.ufop.br/~romildo Universidade Federal de Ouro Preto romildo@iceb.ufop.br Brasil romildo@uber.com.br _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell