# let-floating

**Janis Voigtlaender
**
Janis Voigtlaender <voigt@orchid.inf.tu-dresden.de>

*Mon, 15 Oct 2001 11:10:41 +0200 (MET DST)*

Hello,
I've got a question regarding let-floating [1].=20
Consider the following two versions of the quicksort algorithm:
>* qsort1 l =3D f l []
*>* where f [] =3D (\y -> y)
*>*=09 f (x:xs) =3D let (xs_1,xs_2) =3D part (<x) xs=20
*>*=09=09 in (\y -> f xs_1 (x:(f xs_2 y)))
*
>* qsort2 l =3D f l []
*>* where f [] =3D (\y -> y)
*>* f (x:xs) =3D (\y -> let (xs_1,xs_2) =3D part (<x) xs
*>*=09 in f xs_1 (x:(f xs_2 y)))
*
where the following auxiliary function is used for partitioning a list acco=
rding=20
to some predicate p:
>* part p l =3D part' p l [] []
*>* part' p [] =3D (\y_1 y_2 -> (y_1,y_2))
*>* part' p (x:xs) =3D (\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=20
(profiling shows that the problem is garbage collection). However, qsort2 c=
an be=20
obtained from qsort1 by floating the let-binding into the lambda-abstractio=
n. Of=20
course, [1] states that this is no good idea unless we know that the=20
lambda-abstraction will be applied only once (as is the case here, right?).=
=20
There it is also stated that an analysis phase is added to GHC that spots s=
uch=20
"one-shot-lambdas". I use a fairly old GHC, so my question is:
Is there a compiler (which version?) that optimizes qsort1 to (essentially)=
=20
qsort2 ?
Any hints concerning the possibility/impossibility of this would be helpful=
.
Thanks and regards, Janis.
[1] Simon L. Peyton Jones, Will Partain, Andr=E9 Santos: "Let-floating: Mov=
ing=20
Bindings to Give Faster Programs", ICFP 1996.
--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de