That "fringe" function, reimplemented in Racket

fringe.rkt

#lang racket

;; The fringe of a tree is all the things in it that aren't conses - including
;; '(). For example, the fringe of '((1 . 2) ((3)) 4) is '(1 2 3 () () 4 ()).
(define example '((1 . 2) ((3)) 4))
(define example-fringe '(1 2 3 () () 4 ()))

;; (fringe tree) computes a "stream" of the fringe of a tree. In this case, a
;; "stream" is a function that takes a function getter and calls (getter elem
;; rest), where elem is the next element in the stream and rest is a stream of
;; remaining elements. If the stream is exhausted, elem is '(exhausted) and rest
;; is '().
(define stream/c
  (recursive-contract
   (-> (-> (or/c (not/c pair?) (list/c 'exhausted)) (or/c stream/c '()) any) any)
   #:chaperone))

(define/contract (fringe tree)
  (-> any/c stream/c)
  ;; node is the next node to visit. alt is our continuation (the rest of the
  ;; stream).
  (define ((fringen node alt) getter)
    (if (not (pair? node))
        ;; if it's not a cons, it's an element of the fringe, so call the getter.
        (getter node alt)
        ;; otherwise, examine the car with a continuation that examines the cdr.
        ((fringen (car node) (fringen (cdr node) alt)) getter)))
  (fringen tree (lambda (getter) (getter '(exhausted) '()))))

(define/contract (stream2list s)
  (-> stream/c list?)
  (s (lambda (elem rest)
       (match elem
         ['(exhausted) '()]
         [_ (cons elem (stream2list rest))]))))

;; A simple test.
(require rackunit)
(check-equal? (stream2list (fringe example)) example-fringe)

;; A version of fringe that uses Racket's built-in streams rather than encoding
;; them as higher-order functions. Not as lazy as the original.
(require racket/stream)
(define/contract (fringe-naive tree)
  (-> any/c stream?)
  (match tree
    [(cons x y) (stream-append (fringe-naive x) (fringe-naive y))]
    [elem (stream elem)]))

(check-equal? (stream->list (fringe-naive example)) example-fringe)

;; A lazier version using Racket streams. Still not as lazy as the original,
;; which does no work until you give it a getter; this will examine the tree
;; until it finds the first element.
(define/contract (fringe-lazy tree)
  (-> any/c stream?)
  (define (helper tree cont)
    (match tree
      [(cons x y) (helper x (lambda () (helper y cont)))]
      [elem (stream-cons elem (cont))]))
  (helper tree (lambda () empty-stream)))

(check-equal? (stream->list (fringe-lazy example)) example-fringe)