Lazy seq fundamentals
This issue is for fundamental support for lazy seqs: creating the lazy seq record type, the lazy-seq
macro, a few new functions, and updating sequence functions to support lazy seqs. See #46 for additional constructors like range
and repeat
, and #47 for sequence-processing functions like filter
and take
.
References / Notes
- Making Clojure Lazier: rough design notes from when lazy seqs were added to Clojure
- SRFI-41: defines "streams", which are basically the same thing. But I don't think SRFI-41 offers any leverage over implementing lazy seqs from scratch.
- Moritz Heidkamp created a lazy-seq egg for CHICKEN and wrote an article about it (and comparing to SRFI-41). I don't think this will offer any leverage either, because it was ported to Scheme semantics, so it would be more work to adapt back to Clojure semantics than implementing from scratch would be.
I think that a lazy seq record will need two slots:
- A thunk (function that takes no args) that produces the sequence. This thunk would be the body from the
lazy-seq
macro call. - A cache to hold the sequence produced by the thunk the first time it is called. Often this will be a cons pair where the car is the first value of the sequence, and the cdr will be another lazy seq.
I think that after the cached value is computed, the thunk is no longer needed and the thunk slot could (should) be unset so the thunk can be garbage collected.
I think we can ignore "chunking" for now.
New macros and functions
Update functions to accept lazy seqs
Update the followin functions specifically for lazy seqs
-
seq (return internal cached sequence; call thunk if needed) -
seq? (return true) -
seqable? (return true) -
empty (return empty list)
Update the following functions to have a fallback case that works generically for seqs:
-
count -
into -
nth
After updating all the above functions, the following functions should now accept lazy seqs. Add tests to make sure:
-
first -
rest -
next -
map -
some -
every?
Update functions to return lazy seqs
For compatibility with Clojure, these functions (which currently return lists) should return lazy seqs:
-
map -
re-seq -
distinct