Hello, I've got a question regarding let-floating [1]. Consider the following two versions of the quicksort algorithm:
> qsort1 l = f l [] > where f [] = (\y -> y) > f (x:xs) = let (xs_1,xs_2) = part (<x) xs > in (\y -> f xs_1 (x:(f xs_2 y))) > qsort2 l = f l [] > where f [] = (\y -> y) > f (x:xs) = (\y -> let (xs_1,xs_2) = part (<x) xs > in f xs_1 (x:(f xs_2 y))) where the following auxiliary function is used for partitioning a list according to some predicate p: > part p l = part' p l [] [] > part' p [] = (\y_1 y_2 -> (y_1,y_2)) > part' p (x:xs) = (\y_1 y_2 -> if p x then part' p xs (x:y_1) y_2 > else part' p xs y_1 (x:y_2)) If compiled with "ghc -O", qsort1 runs considerably slower than qsort2 (profiling shows that the problem is garbage collection). However, qsort2 can be obtained from qsort1 by floating the let-binding into the lambda-abstraction. Of course, [1] states that this is no good idea unless we know that the lambda-abstraction will be applied only once (as is the case here, right?). There it is also stated that an analysis phase is added to GHC that spots such "one-shot-lambdas". I use a fairly old GHC, so my question is: Is there a compiler (which version?) that optimizes qsort1 to (essentially) qsort2 ? Any hints concerning the possibility/impossibility of this would be helpful. Thanks and regards, Janis. [1] Simon L. Peyton Jones, Will Partain, Andr� Santos: "Let-floating: Moving Bindings to Give Faster Programs", ICFP 1996. -- Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
