Janis Voigtlaender Janis Voigtlaender <voigt@orchid.inf.tu-dresden.de>
Mon, 15 Oct 2001 11:10:41 +0200 (MET DST)


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=
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?).=
There it is also stated that an analysis phase is added to GHC that spots s=
"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=E9 Santos: "Let-floating: Mov=
Bindings to Give Faster Programs", ICFP 1996.

Janis Voigtlaender