I was looking into working with potentially infinite recursive sequences few days ago. The idea was that if we forgo an internal state, then working with such a sequence amounts to having a recursive function with a head, ie. not just the last element in the sequence but all of the sequence we already constructed. The next element in the sequence depended only on the head of the sequence. Using this, it was easy to implement natural numbers, arithmetic progressions and even Fibonacci sequence. The sequence of prime numbers as a recursive sequence was a little work, but it can be done. I also wrote some experimental code for filtering such sequences using predicates.
For implementing something like map or
mapcar I need something else. For today’s experiment, a
stream is a cons pair of two functions: an iterator which will
construct new elements on top of the head of the sequence and an
extractor which pulls a single element from the stream.
If the extractor is going to pull the last element in the returned
sequence, this means no extra work is required. I am going to set it to
nil as the default case as in the case of natural numbers
or any arithmetic progression:
(defvar natural
(cons (lambda (x)
(if (null x)
(list 0)
(cons (1+ (car x)) x)))
nil))
NATURAL
(defun arithmetic-progression (a b)
(cons (lambda (x)
(if (null x)
(list b)
(cons (+ a (car x)) x)))
nil))
ARITHMETIC-PROGRESSIONEven with the Fibonacci sequence, or with the sequence of prime numbers the extractor is trivial.
(defvar fibonacci
(cons (lambda (x)
(cond ((null x) (list 1))
((< (length x) 2) (cons 1 x))
(t (cons (+ (car x) (cadr x)) x))))
nil))
FIBONACCI
(defvar prime
(cons (lambda (x)
(cond ((null x) (list 2))
((= (car x) 2) (cons 3 x))
(t (let ((y (reverse x))
(m (1+ (floor (sqrt (car x))))))
(do ((i (+ (car x) 2) (+ i 2)))
((do ((j y (cdr j)))
((or (> (car j) m)
(zerop (mod i (car j))))
(> (car j) m)))
(cons i x)))))))
nil))
PRIMEThis change will require me to modify the take function
using extractors:
(defun s-take (stream n &optional (head nil))
(destructuring-bind
(iterate . extract) stream
(do* ((i n (1- i))
(run head (funcall iterate run))
(res nil (and extract (cons (funcall extract run) res))))
((zerop i) (or res run)))))
S-TAKEThe variable res holds part of the data we want to
extract from the stream if the extractor is not
nil. Now, you can see why I set the extractor to
nil. I could also use car but by doing so both
run and res do contain the same elements.
Twice the memory for no gain.
Let us test the streams we defined above:
(s-take natural 10)
(9 8 7 6 5 4 3 2 1 0)
(s-take (arithmetic-progression 13 4) 10)
(121 108 95 82 69 56 43 30 17 4)
(s-take prime 10)
(29 23 19 17 13 11 7 5 3 2)The s-take function that I wrote above is a special kind
of a reducer which uses cons as the aggregator. We can
replace it with any two to one function
fn:T -> T -> T
(defun s-reduce (stream n &optional (fn #'cons) head)
(let ((iterate (car stream))
(extract (or (cdr stream) #'car)))
(do* ((i n (1- i))
(run head (funcall iterate run))
(res nil (funcall fn (funcall extract run) res)))
((zerop i) res))))
S-REDUCENow, let me test it to calculate 10!. For that I am going to need the
first 10 natural numbers starting at 1 (hence (list 1)
argument) and the aggregator is the product. But before I do that I must
guarantee that nil arguments are turned into the unit of
the product (hence (or x 1) and (or y 1)
arguments)
(s-reduce
natural
9
(lambda (x y) (* (or x 1) (or y 1)))
(list 1))
3628800As for filtering, now I have:
(defun s-filter (stream &rest preds)
(let* ((iterate (car stream))
(extract (or (cdr stream) #'car)))
(cons (lambda (x)
(do* ((y (funcall iterate x) (funcall iterate y))
(z (funcall extract y) (funcall extract y)))
((every (lambda (pred) (funcall pred z)) preds) y)))
extract)))
S-FILTERThis time around, one can send a sequence of predicates and we will filter the stream using all of the predicates.
(defun primep (n)
(cond
((< n 2) nil)
((= n 2) t)
((evenp n) nil)
(t (let ((m (floor (sqrt n))))
(do ((i 3 (+ i 2)))
((or (zerop (mod n i)) (> i m))
(> i m)))))))
PRIMEP
(s-take (s-filter fibonacci #'primep) 9)
(514229 28657 1597 233 89 13 5 3 2)
(defun decimal-palindrome-p (n)
(string-equal (format nil "~d" n)
(reverse (format nil "~d" n))))
DECIMAL-PALINDROME-P
(s-take
(s-filter
(arithmetic-progression 151 3)
#'oddp
#'primep
#'decimal-palindrome-p)
10)
(126676621 125000521 118626811 117101711 7159517 3127213 1684861 1532351
30203 3)Now, with streams with extractors (an idea I already used in filtering) mapping becomes easy:
(defun s-map (stream &rest fns)
(cons (car stream)
(lambda (x)
(let ((y (funcall (or (cdr stream) #'car) x)))
(dolist (fn fns y)
(setf y (funcall fn y)))))))
S-MAPThe mapping functions do not alter the iterator. Instead, we compose them one by one with the current extractor. As with filter, I am going to send a sequence of functions and they will be applied to the stream from left to right.
(defun binary-palindrome-p (n)
(string-equal (format nil "~b" n)
(reverse (format nil "~b" n))))
BINARY-PALINDROME-P
(defun fn (n)
(if (oddp n)
n
(fn (/ n 2))))
FN
(s-take
(s-filter
(s-map
(arithmetic-progression 41 13)
#'fn
(lambda (x) (+ (* x x) x 1)))
#'binary-palindrome-p)
5)
(1114081 272629633 4328521473 5113 381)What I wrote above is heavily influenced by what Rich Hickey did with reducers and transducers. But this all came out from reading SICP’s streams. I was thinking of constructing primes as a stream. It came to me that it would be easier, and perhaps conceptually clearer, to construct streams as recursive functions that depend only on the head of the stream. To be clear: when I say the head I mean the whole initial segment \((a_n,a_{n-1},\ldots,a_1)\) of the stream, not just the last element \(a_n\). This way, the stream can also be functional, that is, whoever has the head has also the next element. With clever use of memoization, there would be no collisions, no blocking, no semaphores, no nothing.
To be fair, there are a couple of things missing in my
implementation. For example, this approach is good for infinite
sequences, but I need a way of signaling that a stream has reached its
end if it happens to be a finite sequence. This can be done via
returning multiple values in the extractor: one value and one boolean
(t when the end is reached, and nil
otherwise). Then all of the functions I wrote above need to be corrected
accordingly.