--------------------------------------------------------------------------------
-- stream.lua
-- A very preliminary lazy stream library
--
-- (c) 2007 Fabien Fleutot, <metalua@gmail.com>
--------------------------------------------------------------------------------
-- Released under the MIT public licence.
--------------------------------------------------------------------------------


-{ extension "lazy" }
-{ extension "ternary" }

module ("stream", package.seeall)

--------------------------------------------------------------------------------
-- The empty stream value. [nil] would cause troubles in strict variables mode,
-- and [false] remains easy to test.
--------------------------------------------------------------------------------
empty = false

--------------------------------------------------------------------------------
-- Create a finite stream with all the elements passed as arguments.
--------------------------------------------------------------------------------
function create(...)
   local args, s = {...}, empty
   for i = #args, 1, -1 do s = { hd = args[i], tl = s } end
   return s
end

--------------------------------------------------------------------------------
-- Build a stream with head [a] and tail [b]. At some point, a syntax extension
-- will be required to avoid eager evaluation of [a] and [b]. 
--------------------------------------------------------------------------------
cons    = |a,b| %{ hd=a, tl=b }      

--------------------------------------------------------------------------------
-- If [s] is the stream x[1] ... x[n], this returns the stream 
-- f(x[1]) ... f(x[n]).
--------------------------------------------------------------------------------
map     = |f,s| s ? %{ hd=f(s.hd), tl=map(f, s.tl) },  empty

--------------------------------------------------------------------------------
-- Concatenate two streams together.
--------------------------------------------------------------------------------
cat2    = |a,b| a ? %{ hd=a.hd, tl=cat2(a.tl, b) }, b

--------------------------------------------------------------------------------
-- Collapse a stream of streams into a flat stream.
--------------------------------------------------------------------------------
flatten = |s|   s ? cat2 (s.hd, flatten(s.tl)),  empty

--------------------------------------------------------------------------------
-- Keeps only the elements of [s] which satisfy predicate [p].
-- The head of the resulting stream is computed eagerly, to determine
-- whether the resulting stream is empty.
--------------------------------------------------------------------------------
filter  = |p,s| s ? p(s.hd) ? %{ hd = s.hd, tl=filter(p, s.tl) }, 
                              filter(p, s.tl),  empty

--------------------------------------------------------------------------------
-- If [n] is non-nil, return the list of the stream's [n] first elements.
-- If [n] is nil or false, convert the whole (hopefully finite) stream into
-- a list.
--------------------------------------------------------------------------------
take   = |n,s| n and n<=0 or not s ? { }, { s.hd, unpack(take (n and n-1, s.tl)) }
/body>