
/* stream.q: a lazy list data structure
   $Id: stream.q,v 1.40 2007/10/03 14:54:57 agraef Exp $ */

/* Originally written by Klaus Barthelmann and Albert Graef April 1993. */

/* This file is part of the Q programming system.

   The Q programming system is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   The Q programming system is distributed in the hope that it will be
   useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */

include stdlib, tuple;

/* The Stream type used to be defined here, but is now provided as a builtin.
   Moreover, the interpreter provides syntactic sugar which makes streams look
   very much like lists: {} = nil_stream, {X1,...,Xn|Y} = cons_stream X1
   (...(cons_stream Xn|Y)...), {X1,...,Xn} = cons_stream X1 (... (cons_stream
   Xn|nil_stream)). Notations for stream enumerations ({X..Y}, {X..}, etc.)
   and stream comprehensions ({X : Y, ...}) are provided, too. */

// public type Stream = special const nil_stream, cons_stream X Xs;

public isstream X;

isstream _:Stream	= true;
isstream _		= false otherwise;

/* Convert between tuples, lists and streams. */

public stream Xs, ::list Xs;

stream []		= {};
stream [X|Xs]		= {X|stream Xs};

stream Xs:Tuple		= stream (list Xs);

list {}			= [];
list {X|Xs}		= [X|list Xs];

tuple Xs:Stream		= tuple (list Xs);

/* Control stream evaluation (Q 7.1 and later). */

/* The hdstrict and tlstrict functions convert a stream into head- or tail-
   strict form, by forcing the heads or tails of the stream, respectively.
   Conversely, the hdlazy and tllazy functions make a stream even "lazier"
   than it normally is, by causing heads and tails of the result stream to be
   memoized. This reduces computation times when a stream is to be traversed
   repeatedly. */

public hdstrict Xs, tlstrict Xs, hdlazy Xs, tllazy Xs;

hdstrict {}		= {};
hdstrict {X|Xs}		= {~X|hdstrict Xs};

tlstrict {}		= {};
tlstrict {X|Xs}		= {X|~(tlstrict Xs)};

hdlazy {}		= {};
hdlazy {X|Xs}		= {&X|hdlazy Xs};

tllazy {}		= {};
tllazy {X|Xs}		= {X|&(tllazy Xs)};

/* The strict and lazy operations produce streams which are both head- and
   tail-strict resp. -lazy. We also provide the operations strict_lazy and
   lazy_strict which implement the other, mixed evaluation modes. */

public strict Xs, lazy Xs, strict_lazy Xs, lazy_strict Xs;

strict {}		= {};
strict {X|Xs}		= {~X|~(strict Xs)};

lazy {}			= {};
lazy {X|Xs}		= {&X|&(lazy Xs)};

strict_lazy {}		= {};
strict_lazy {X|Xs}	= {~X|&(strict_lazy Xs)};

lazy_strict {}		= {};
lazy_strict {X|Xs}	= {&X|~(lazy_strict Xs)};

/* The following definitions implement stream versions of the corresponding
   list operations. Of course, you don't want to apply operations like (#),
   last, etc. to infinite streams; it will take them an infinite time to
   compute the result. This also happens with foldl; foldr on an infinite
   stream works, though, provided that the folded function doesn't evaluate
   its second argument. Also note that 'cat' is extended to work with any
   mixture of streams and lists. This operation is strict and will always
   return a list, thus it won't work with infinite streams either. For a lazy
   stream concatenation function see 'streamcat' below. */

#{}			= 0;
#{X|Xs}			= 1+#Xs;

{X|Xs}!0		= X;
{X|Xs}!N:Int		= Xs!(N-1) if N>0;

{}++Xs:Stream		= Xs;
{X|Xs}++Ys:Stream	= {X|Xs++Ys};

all P {}		= true;
all P {X|Xs}		= P X and then all P Xs;

any P {}		= false;
any P {X|Xs}		= P X or else any P Xs;

append {} Y		= {Y};
append {X|Xs} Y		= {X|append Xs Y};

cat Xs:Stream		= cat Xs where Xs:List = list Xs;
cat [Xs:Stream|Xss]	= cat [Xs|Xss] where Xs:List = list Xs;

cons X Xs:Stream	= {X|Xs};

do F {}			= ();
do F {X|Xs}		= F X || do F Xs;

dowith F {X|Xs} {Y|Ys}	= F X Y || dowith F Xs Ys;
dowith F _:Stream _:Stream
			= () otherwise;

dowith3 F {X|Xs} {Y|Ys} {Z|Zs}
			= F X Y Z || dowith3 F Xs Ys Zs;
dowith3 F _:Stream _:Stream _:Stream
			= () otherwise;

drop N:Int {}		= {};
drop N:Int {X|Xs}	= drop (N-1) Xs if N>0;
			= {X|Xs} otherwise;

/* Note that the filter function, as well as dropwhile and takewhile will
   evaluate at least the head element of the stream if the given predicate P
   is not a special form. The same element may have to be evaluated again when
   the resulting stream is traversed later. This may be inefficient, and may
   also produce surprising results if the computation of the element involves
   side-effects. You can avoid this by making the input stream head-lazy
   (using the hdlazy function from above, which causes the values of the
   stream elements to be memoized). */

dropwhile P {}		= true;
dropwhile P {X|Xs}	= dropwhile P Xs if P X;
			= {X|Xs} otherwise;

filter P {}		= {};
filter P {X|Xs}		= {X|filter P Xs} if P X;
			= filter P Xs otherwise;

foldl F A {}		= A;
foldl F A {X|Xs}	= foldl F (F A X) Xs;

foldl1 F {X|Xs}		= foldl F X Xs;

foldr F A {}		= A;
foldr F A {X|Xs}	= F X (foldr F A Xs);

foldr1 F {X}            = X;
foldr1 F {X,Y|Xs}       = F X (foldr1 F {Y|Xs});

hd {X|Xs}		= X;

hds {}			= {};
hds {Xs:Stream|Xss}	= hds Xss if null Xs;
			= {hd Xs|hds Xss} otherwise;

init {X}		= {};
init {X|Xs}		= {X|init Xs} otherwise;

last {X}		= X;
last {X|Xs}		= last Xs otherwise;

map F {}		= {};
map F {X|Xs}		= {F X|map F Xs};

null {}			= true;
null _:Stream		= false otherwise;

pop {X|Xs}		= Xs;

prd Xs:Stream		= foldl (*) 1 Xs;

push Xs:Stream X	= {X|Xs};

reverse Xs:Stream	= foldl push {} Xs;

scanl F A {}		= {A};
scanl F A {X|Xs}	= {A|scanl F (F A X) Xs};

scanl1 F {}		= {};
scanl1 F {X|Xs}		= scanl F X Xs;

/* To make the scanr functions work in linear time, we memoize the heads of
   the result stream. Also note that these operations are intrinsically
   tail-strict because we can't know the head of the result stream before all
   of its tails have been computed. */

scanr F A {}		= {A};
scanr F A {X|Xs}	= {&(F X Y)|Ys} where Ys = scanr F A Xs, {Y|_} = Ys;

scanr1 F {}		= {};
scanr1 F {X}		= {X};
scanr1 F {X|Xs}		= {&(F X Y)|Ys} where Ys = scanr1 F Xs, {Y|_} = Ys;

sub Xs:Stream I:Int J:Int
			= take (J-I+1) (drop I Xs);

sum Xs:Stream		= foldl (+) 0 Xs;

take N:Int {}		= {};
take N:Int {X|Xs}	= {X|take (N-1) Xs} if N>0;
			= {} otherwise;

takewhile P {}		= {};
takewhile P {X|Xs}	= {X|takewhile P Xs} if P X;
			= {} otherwise;

tl {_|Xs}		= Xs;

tls {}			= {};
tls {Xs:Stream|Xss}	= tls Xss if null Xs;
			= {tl Xs|tls Xss} otherwise;

top {X|Xs}		= X;

transpose {}		= {};
transpose {Xs:Stream|Xss}
			= transpose Xss if null Xs;
			= {{hd Xs|hds Xss}|transpose {tl Xs|tls Xss}}
			    otherwise;

/* We have to go to some lengths here to make the unzip operations lazy enough
   so that they will work with infinite input streams. To these ends, we defer
   the recursive unzip invocations until the tails of the output streams are
   actually needed. This is done using a memoizing suspension so that the
   recursive unzip calls are done only once. */

/* NOTE: This implementation differs from the one in the Haskell prelude in
   that the result is head-strict. This is because we want to make unzip fail
   immediately if the head of the input stream is not a tuple with the right
   number of elements. */

unzip {(X,Y)|Us}	= ({X|fst Us},{Y|snd Us})
			    where 'Us = '&(unzip Us);
unzip {}		= ({},{});

unzip3 {(X,Y,Z)|Us}	= ({X|fst Us},{Y|snd Us},{Z|trd Us})
			    where 'Us = '&(unzip3 Us);
unzip3 {}		= ({},{},{});

zip {X|Xs} {Y|Ys}	= {(X,Y)|zip Xs Ys};
zip _:Stream _:Stream	= {} otherwise;

zip3 {X|Xs} {Y|Ys} {Z|Zs}
			= {(X,Y,Z)|zip3 Xs Ys Zs};
zip3 _:Stream _:Stream _:Stream
			= {} otherwise;

zipwith F {X|Xs} {Y|Ys}	= {F X Y|zipwith F Xs Ys};
zipwith F _:Stream _:Stream
			= {} otherwise;

zipwith3 F {X|Xs} {Y|Ys} {Z|Zs}
			= {F X Y Z|zipwith3 F Xs Ys Zs};
zipwith3 F _:Stream _:Stream _:Stream
			= {} otherwise;

/* Stream concatenation. This is similar to 'cat' and also accepts an
   arbitrary mixture of streams, lists and tuples, but works in a lazy fashion
   and always returns a stream. */

public streamcat Xs;

streamcat {}		= {};
streamcat {{}|Yss}	= streamcat Yss;
streamcat {[]|Yss}	= streamcat Yss;
streamcat {{X|Xs}|Yss}	= {X|streamcat {Xs|Yss}};
streamcat {[X|Xs]|Yss}	= {X|streamcat {Xs|Yss}};

streamcat []		= {};
streamcat [{}|Yss]	= streamcat Yss;
streamcat [[]|Yss]	= streamcat Yss;
streamcat [{X|Xs}|Yss]	= {X|streamcat {Xs|Yss}};
streamcat [[X|Xs]|Yss]	= {X|streamcat {Xs|Yss}};

/* Q 7.8: Tuples are handled by converting them to lists on the fly. */

streamcat Xs:Tuple	= streamcat Xs where Xs:List = list Xs;
streamcat {Xs:Tuple|Xss}
			= streamcat {Xs|Xss} where Xs:List = list Xs;

/* Stream generation functions. */

public iterate F A;
iterate F A		= {A|iterate F (F A)};

public numstream N;
numstream N:Real	= iterate (+1) N;

public numstreamby K N;
numstreamby K:Real N:Real
			= iterate (+K) N;

public mkstream X;
mkstream X		= {X|mkstream X};

/* Additional Haskell-like stream generation operations (Q 7.1 and later). */

public special repeat X, repeatn ~N X;
public cycle Xs;

repeat X		= {X|repeat X};
repeatn N:Int X		= take N (repeat X);
cycle {X|Xs}		= {X|Xs++cycle {X|Xs}};
cycle [X|Xs]		= {X|stream Xs++cycle [X|Xs]};
