Python from Wise Guy's Viewpoint

[prunesquallor at comcast.net]

I think I have a stumper.  I'll be impressed if a type checker can
validate this.  The same-fringe function takes a pair of arbitrary
trees and lazily determines if they have the same leaf elements in the
same order.  Computation stops as soon as a difference is found so
that if one of the trees is infinite, it won't cause divergence.

(defun lazy-sequence (x y)
  (if (null x)
      (funcall y)
      (funcall x
        (lambda (xh xt)
          (lambda (z)
            (funcall z xh
              (lambda ()
                (lazy-sequence
                 (funcall xt)
                 y))))))))

(defun lazy-fringe (x)
  (cond ((null x) '())
        ((consp x) (lazy-sequence (lazy-fringe (car x)) 
                                  (lambda () (lazy-fringe (cdr x)))))
        (t (lambda (z)
             (funcall z x (lambda () ()))))))

(defun lazy-same (s1 s2)
  (cond ((null s1) (null s2))
        ((null s2) nil)
        (t (funcall s1 
             (lambda (h1 t1)
               (funcall s2
                 (lambda (h2 t2)
                    (if (eql h1 h2)
                        (lazy-same (funcall t1) (funcall t2))
                        nil))))))))

(defun same-fringe (l1 l2)
  (lazy-same (lazy-fringe l1) (lazy-fringe l2)))

(defun testit ()
  (assert (same-fringe '((1 2) (3 (4))) '(1 (2 3) (4))))
  (let ((circular-list (list 3)))
    (setf (cdr circular-list) circular-list)
    (assert (not (same-fringe `((1 2) (3 ,circular-list)) `(1 (2 3) (3 4)))))))