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:voigt@tcs.inf.tu-dresden.de