%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lazy quicksort in Oz
% An example of how lazy execution can make some functions
% incremental in an efficient way
% Author: Peter Van Roy
% Date: March 14, 2007
% This file gives an example of the power of lazy execution.
% We show how taking a standard eager algorithm and
% annotating it as lazy can give a smart incremental
% algorithm with no extra work.
% Lazy functions can be either incremental or monolithic.
% A function is monolithic if requesting part of the output
% causes *all* the output to be calculated. Otherwise, if
% the function only calculates part of the output then it
% is incremental.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Example of a monolithic function
% For example, the list reverse function is monolithic.
% Here is the definition of a lazy reverse.
declare
fun {LReverse Xs}
fun lazy {LRev Xs Rs}
case Xs of X|Xr then {LRev Xr X|Rs}
[] nil then Rs end
end
in
{LRev Xs nil}
end
% If you ask for part of the output (like the first
% element of the reverse of [a b c d]), then the
% *whole* output is calculated. This example will
% display [d c b a]:
declare
Xs={LReverse [a b c d]}
{Browse Xs.1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The quicksort function, on the other hand, is incremental.
% That means if you sort a list lazily and you ask for just
% the first element of the output, then the function will
% not do the whole sort, but just do part of the work,
% enough to output the smallest element of the input list.
% If you ask for the k first outputs (the k smallest
% elements) of a list of size n, then the lazy quicksort
% will calculate them in a time O(n + k log n). This
% is much more efficient than sorting the whole list and
% taking the first k of the result, which would be
% O(n log n). It is also much more efficient than
% selecting the k smallest elements one at a time, which
% would be O(k n). In fact, the lazy quicksort is a very
% efficient algorithm for finding the smallest k elements
% out of n elements!
% It is an interesting exercise to see exactly how the
% execution of the lazy quicksort works. Each invocation
% of a lazy function does not execute the body but just
% creates a lazy suspension that contains the body.
% When the function's output is needed, then the lazy
% suspension is activated, which executes the body.
% If you follow this through, you will see that only
% a few of the calls to LQuicksort and LAppend are
% actually executed if you request the first element
% of the output list.
% Lazy quicksort definition: this is exactly the same
% definition as a standard eager quicksort, except that
% the quicksort and the append utility are made lazy.
% The partition procedure is eager.
% Lazy append utility
declare
fun lazy {LAppend Xs Ys}
case Xs of X|Xr then
X|{LAppend Xr Ys}
[] nil then Ys
end
end
% Partition is not lazy; it does not have to be.
declare
proc {Partition L2 X L R}
case L2
of Y|M2 then
if Y