%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 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<X then Ln in
	 L=Y|Ln
	 {Partition M2 X Ln R}
      else Rn in
	 R=Y|Rn
	 {Partition M2 X L Rn}
      end
   [] nil then L=nil R=nil
   end
end

declare
fun lazy {LQuicksort L}
   % Use first element of L as pivot
   case L of X|L2 then Left Right SL SR in
      {Partition L2 X Left Right}
      SL={LQuicksort Left}
      SR={LQuicksort Right}
      {LAppend SL X|SR}
   [] nil then nil end
end

% Example execution:
declare
Xs={LQuicksort [5 8 4 7 3 2 7 6 0 5 4 1 0 4]}
{Browse Xs}

% This will calculate the first three smallest elements
% and display the third smallest element:
{Browse Xs.2.2.1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%