Going lazy with Racket
Generate sequences that have their elements computed as you go seems challenging, but fear not, we can tackle it!
So, I stumble upon this when I was trying to solve day 10 of Advent of Code 2020 (my code is here, but I’m laaaaate!). I’d like to get sequences of consecutive elements that meet some criteria. For example, getting all consecutive odd numbers in the list '(1 3 5 6 7 8) will return '((1 3 5) (7)).
I was pretty sure that exists, but I couldn’t find it. So I build it myself.
First, I’m using the excellent collections-lib from Alexis King. It provides a nice unified interface to all collections in Racket. It’s essentially lazy, so it avoids running through elements until they are needed. My version needs to be compatible.
The strategy is to build a recursive code using plain lists first, then replace "
cons”and "empty”for "stream-cons”and "empty-stream”.
First, I’ve built the code to group consecutive elements on a plain list with good old recursion. My first reflex was using an accumulator to make use of tail-call optimization but that just made the transformation more difficult. Then I’ve reverted back to non-tail-call recursion so changing the code was straightforward.
Here the version using a simple list:
Using it like (in-groups odd? '(1 3 5 6 7 8)) returns '((1 3 5) (7)).
Then, I’ve replaced all cons and empty for stream-cons and empty-stream and voilà! It’s done! Now I can freely use all the benefits of collections-lib and lazy collections.
Here is the final version:
Using it like (in-groups odd? '(1 3 5 6 7 8)) returns #<stream>, so we have to use sequence->list, like this (sequence->list (in-groups odd? '(1 3 5 6 7 8))) to get the same answer as before.
Lazy senquences are not tail-recursive, but they don’t keep piling up on your stack.
The only changes were on lines 7 and 14, where I replaced cons and empty by stream-cons and empty-stream.
Note that group is a plain list on both versions. I haven’t tried a double lazy version, but it might be not that difficult to do it.
I hope that helps you to get a little more comfortable with lazy sequences in Racket.
Lazy sequences built with stream-cons also have a very interesting effect. They are not tail-recursive, but they don’t keep piling up on your stack. So that might be useful on some tree walking algorithms.
*Three-toed sloth image by Sergio Delgado licensed under Creative Commons.
