The Kitchen Sink and Other Oddities

Atabey Kaygun

Experiments with Infinite Recursive Sequences

Description of the problem

For today’s post, a stream is a potentially infinite sequence of objects.

  1. I would like my streams to be functional. That is no internal state.

  2. 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\).

Implementation

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))))
NATURAL

Here 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))))
ODD

In 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))))))))
PRIME

I 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))))
TAKE

Let 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)

Filtering a stream

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-UNTIL

Let 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-STREAM

Let 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-P

The 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.