For today’s post, a stream is a potentially infinite sequence of objects.
I would like my streams to be functional. That is no internal state.
I want my streams to be fully recursive. That is a next item \(a_{n+1}\) in a stream will depend on some (and in some cases all) of \(a_1,\ldots,a_n\).
The requirements I set above force a stream to be a function that accepts an ordered list of objects \((a_n,a_{n-1},\ldots,a_1)\) and returns \((a_{n+1},a_n,\ldots,a_1)\). So, for example a stream for natural numbers will look like
(defvar natural
(lambda (x)
(if (null x)
(list 0)
(cons (1+ (car x)) x))))
NATURALHere are two streams for even and odd numbers.
(defvar even
(lambda (x)
(if (null x)
(list 0)
(cons (+ 2 (car x)) x))))
EVEN
(defvar odd
(lambda (x)
(if (null x)
(list 1)
(cons (+ 2 (car x)) x))))
ODDIn all of these examples, the next term in the stream depends only on the last term in the stream. Here is another example
(defvar fibonacci
(lambda (x)
(cond ((null x) (list 1))
((< (length x) 2) (cons 1 x))
(t (cons (+ (car x) (cadr x)) x)))))
FIBONACCI
(defvar prime
(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))))))))
PRIMEI am going to need a function that pulls a specific number of items from a stream:
(defun take (stream n &optional (x nil))
(if (zerop n)
x
(take stream (1- n) (funcall stream x))))
TAKELet us test the streams we defined above:
(take natural 10)
(9 8 7 6 5 4 3 2 1 0)
(take even 12)
(22 20 18 16 14 12 10 8 6 4 2 0)
(take odd 6 '(3 1))
(15 13 11 9 7 5 3 1)
(take fibonacci 15)
(610 377 233 144 89 55 34 21 13 8 5 3 2 1 1)
(take prime 10)
(29 23 19 17 13 11 7 5 3 2)First, I am going to need a function which will pull items from a stream until a predicate is satisfied:
(defun take-until (stream pred &optional (x nil))
(let ((i (funcall stream x)))
(if (funcall pred (car i))
i
(take-until stream pred i))))
TAKE-UNTILLet me test:
(take-until prime (lambda (i) (> i 40)))
(41 37 31 29 23 19 17 13 11 7 5 3 2)Now, a function that returns a new stream from another stream by selecting elements satisfying a predicate
(defun filter-stream (stream pred)
(lambda (y)
(take-until stream pred y)))
FILTER-STREAMLet us test. Let me write the first 12 odd numbers in the Fibonacci sequence:
(defvar aa (filter-stream fibonacci #'oddp))
AA
(take aa 12)
(1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1)This is clearly not I intended to do. The sequence contains 12 odd
numbers but it also contains more. We must modify the take
function:
(defun take (stream n &optional (x nil))
(do* ((run (funcall stream x) (funcall stream run))
(res (list (car run)) (cons (car run) res))
(i (1- n) (1- i)))
((zerop i) res)))
TAKE
(take aa 12)
(1597 987 377 233 89 55 21 13 5 3 1 1)Now, let me get the first 9 odd primes from Fibonacci sequence:
(defun odd-prime-p (n)
(if (and (oddp n) (> n 2))
(let ((m (floor (sqrt n))))
(do ((i 3 (+ i 2)))
((or (> i m) (zerop (mod n i)))
(> i m))))))
ODD-PRIME-P
(take (filter-stream fibonacci #'odd-prime-p) 9)
(433494437 514229 28657 1597 233 89 13 5 3)Now, we define a more interesting predicate:
(defun decimal-palindrome-p (n)
(string-equal
(format nil "~d" n)
(reverse (format nil "~d" n))))
DECIMAL-PALINDROME-PThe following returns the first 100 decimal-palindromic odd primes:
(take (filter-stream (filter-stream odd #'odd-prime-p) #'decimal-palindrome-p) 100)
(94349 94049 93739 93239 93139 91019 90709 79997 79697 79397 78887 78787
78487 77977 77477 77377 76667 76367 75557 74747 74047 73637 73237 73037
72727 72227 71917 71317 70607 70507 70207 39293 38783 38183 38083 37573
37273 36563 36263 35753 35353 35153 35053 34843 34543 33533 32423 32323
31513 31013 30803 30703 30403 30203 30103 19991 19891 19391 18481 18181
17971 17471 16661 16561 16361 16061 15551 15451 14741 14341 13931 13831
13331 12821 12721 12421 11411 11311 10601 10501 10301 929 919 797 787 757
727 383 373 353 313 191 181 151 131 101 11 7 5 3)How about the Fibonacci sequence? What are the first 5 binary-palindromic numbers in Fibonacci sequence?
(defun binary-palindrome-p (n)
(string-equal
(format nil "~b" n)
(reverse (format nil "~b" n))))
BINARY-PALINDROME-P
(take (filter-stream (filter-stream fibonacci #'oddp) #'binary-palindrome-p) 5)
(21 5 3 1 1)I ran the code for 6 but got no answer within 5 minutes. Even if there is one, it must be pretty large.