I have been wanting to comment on jcs’s post on streams in lisp, and his take on what I did. But, I was traveling and having too much fun playing with Collatz sequences.
He is correct in that transporting the streams code from scheme to lisp is almost trivial, and jcs did that nicely and concisely in his post. As he also noticed, what I was trying to do was different. Probably, this is a good opportunity to explain.
In SICP,
Abelson and Sussman conceive them as potentially infinite lazy lists.
And they use the same interface as the regular lists. So, they have a
car and a cdr which obey the same algebraic
rules as the regular lists:
x = (cons (car x) (cdr x))If one would like to develop streams from ground up as a functional data structure, one option is to think of them as objects with two specific functions: an iterator and an extractor. An iterator receives a head for the stream and returns another head, this time for the iterated stream. An extractor receives a head and returns a single element which you’d like to construct out of the stream and the head at the hand.
To make things clear: when I say the head I mean the whole
sequence of elements constructed at a moment. Also, in the
implementations below they are in the reverse order: from the last to
the first. Don’t blame me: car is cheaper than
(lambda (x) (car (reverse x))).
In this picture, a stream is purely functional: whoever has the head has the stream. No locks or semaphores. They are immutable, efficient, and with clever use of memoization for the iterators and extractors they are really fast.
The code for the interface consisted of three functions only. I had a
take function:
(defun s-take (stream n &optional head)
(destructuring-bind
(iterator . extractor) stream
(do* ((x head (funcall iterator x))
(y nil (cons (funcall extractor x) y))
(i n (1- i)))
((zerop i) y))))
S-TAKEwhich would take from the stream a specific number of items; a
map function which would apply a sequence of functions to
the values after we extract them:
(defun s-map (stream &rest fns)
(destructuring-bind
(iterator . extractor) stream
(cons iterator
(lambda (x)
(let ((y (funcall extractor x)))
(dolist (fn fns y)
(setf y (funcall fn y))))))))
S-MAPand finally; a filter function which would filter the
values extracted according to a list of predicates:
(defun s-filter (stream &rest preds)
(destructuring-bind
(iterator . extractor) stream
(cons (lambda (x)
(do* ((y (funcall iterator x) (funcall iterator y))
(z (funcall extractor y) (funcall extractor y)))
((every (lambda (pred) (funcall pred z)) preds) y)))
extractor)))
S-FILTERFor simple streams such as the natural numbers or arithmetic progressions, the extractor returns the last element of the head and the iterator increases this value and affixes to the head.
(defvar natural-numbers
(cons (lambda (x)
(if (null x)
(list 1)
(cons (1+ (car x)) x)))
#'car))
NATURAL-NUMBERS
(s-take natural-numbers 10)
(10 9 8 7 6 5 4 3 2 1)
(defun arithmetic-progression (a b)
(cons (lambda (x)
(if (null x)
(list b)
(cons (+ a (car x)) x)))
#'car))
ARITHMETIC-PROGRESSION
(s-take (arithmetic-progression 12 3) 10)
(111 99 87 75 63 51 39 27 15 3)For the Fibonnacci sequence, the extractor is the same, but the iterator takes the last two values and affixes the sum to the head.
(defvar fibonacci
(cons (lambda (x)
(cond
((null x) (list 1))
((= 1 (length x)) (list 1 1))
(t (cons (+ (car x) (cadr x)) x))))
#'car))
FIBONACCI
(s-take fibonacci 10)
(55 34 21 13 8 5 3 2 1 1)During the course of my experiments (2015-01-01-functional_streams.html) here and here I gave several examples (some of which I reproduced here), but today I will give a new one: I’d like to construct a stream of integers which will give the sums of squares of the first \(n\) integers. In that case, the iterator takes the last value of the list, adds one to it and then affixes to the head. The extractor on the other hand, takes the whole list and finds the sum of the squares.
(defvar sums-of-squares
(cons (lambda (x)
(if (null x)
(list 1)
(cons (1+ (car x)) x)))
(lambda (x) (reduce #'+ (mapcar (lambda (i) (* i i)) x)))))
SUMS-OF-SQUARES
(s-take sums-of-squares 10)
(385 285 204 140 91 55 30 14 5 1)Of course, we can get the same stream from
natural-numbers using a map:
(s-take
(s-map
natural-numbers
(lambda (x) (* x (1+ x) (1+ (* 2 x)) (/ 6))))
10)
(385 285 204 140 91 55 30 14 5 1)but I was trying to make a point in saying that the extractor is an integral part of the stream, and in practice, may need to know the full head of the stream at the time of extraction, not just the last element.
Now, we can filter and map this stream to get new stream(s):
(defun binary-palindrome-p (x)
(string-equal
(format nil "~b" x)
(reverse (format nil "~b" x))))
BINARY-PALINDROME-P
(s-take
(s-map
(s-filter
sums-of-squares
#'oddp
#'binary-palindrome-p)
(lambda (x) (format nil "~b" x)))
4)
(110011000101101000110011 1100110011 101 1)I forgot: there is also room for a reducer in the s-take
interface which can easily obtained by changing the reducer from
cons to any other reducer:
(defun s-take (stream n &optional head (reducer #'cons))
(destructuring-bind
(iterator . extractor) stream
(do* ((x head (funcall iterator x))
(y nil (funcall reducer (funcall extractor x) y))
(i n (1- i)))
((zerop i) y))))and one can call it as
(s-take
(s-map
natural-numbers
(lambda (x) (* x x))
10
nil
(lambda (x y) (+ (or x 0) (or y 0))))
385