Functional Data Structures in Guile Scheme

Introduction
Lazy Streams
Banker's Queues
Skew Binary Random-Access Lists
Usage Examples
Conclusion

Introduction

This file implements several key data structures from Chris Okasaki's "Purely Functional Data Structures" using Guile Scheme. It demonstrates important concepts like lazy evaluation, structural decomposition, and amortized analysis.

Lazy Streams

Streams are a fundamental lazy data structure that form the basis for many other structures in the book.

(define-module (lazy-streams)
  #:export (stream-cons stream-car stream-cdr stream-null? stream-map))

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons a b)
     (cons a (delay b)))))

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

(define (stream-null? stream) (null? stream))

(define (stream-map f stream)
  (if (stream-null? stream)
      '()
      (stream-cons (f (stream-car stream))
                   (stream-map f (stream-cdr stream)))))

Banker's Queues

Banker's queues demonstrate the use of lazy evaluation for amortization.

(define-module (bankers-queue)
  #:use-module (lazy-streams)
  #:export (empty enqueue dequeue front empty?))

(define-record-type <queue>
  (make-queue lenf f lenr r)
  queue?
  (lenf queue-lenf)
  (f queue-f)
  (lenr queue-lenr)
  (r queue-r))

(define empty (make-queue 0 '() 0 '()))

(define (empty? q) (and (zero? (queue-lenf q)) (zero? (queue-lenr q))))

(define (check q)
  (let ((lenf (queue-lenf q))
        (f (queue-f q))
        (lenr (queue-lenr q))
        (r (queue-r q)))
    (if (<= lenr lenf)
        q
        (make-queue (+ lenf lenr) 
                    (stream-append f (stream-reverse r))
                    0 
                    '()))))

(define (enqueue q x)
  (check (make-queue (queue-lenf q) 
                     (queue-f q) 
                     (1+ (queue-lenr q)) 
                     (cons x (queue-r q)))))

(define (dequeue q)
  (if (empty? q)
      (error "dequeue called on empty queue")
      (let ((f (queue-f q)))
        (if (stream-null? (stream-cdr f))
            (make-queue 0 '() 0 '())
            (check (make-queue (1- (queue-lenf q)) 
                               (stream-cdr f) 
                               (queue-lenr q) 
                               (queue-r q)))))))

(define (front q)
  (if (empty? q)
      (error "front called on empty queue")
      (stream-car (queue-f q))))

(define (stream-append s1 s2)
  (if (stream-null? s1)
      s2
      (stream-cons (stream-car s1)
                   (stream-append (stream-cdr s1) s2))))

(define (stream-reverse s)
  (stream-reverse-aux s '()))

(define (stream-reverse-aux s acc)
  (if (stream-null? s)
      acc
      (stream-reverse-aux (stream-cdr s)
                          (stream-cons (stream-car s) acc))))

Skew Binary Random-Access Lists

Skew binary random-access lists demonstrate the use of numerical representations for data structures.

(define-module (skew-binary-list)
  #:export (empty cons head tail lookup update))

(define-record-type <tree>
  (make-tree element left right)
  tree?
  (element tree-element)
  (left tree-left)
  (right tree-right))

(define empty '())

(define (cons x ts)
  (match ts
    (((<tree> y a b) (<tree> z c d) . rest)
     (if (= (tree-size a) (tree-size c))
         (make-tree x (make-tree y a b) (make-tree z c d) . rest)
         (make-tree x '() '() . ts)))
    (_ (make-tree x '() '() . ts))))

(define (head ts)
  (match ts
    (((<tree> x _ _) . _) x)
    (_ (error "head: empty list"))))

(define (tail ts)
  (match ts
    (((<tree> _ '() '()) . rest) rest)
    (((<tree> _ a b) . rest) (tree-to-list a (tree-to-list b rest)))
    (_ (error "tail: empty list"))))

(define (tree-to-list t rest)
  (if (tree? t)
      (cons (make-tree (tree-element t) '() '()) 
            (tree-to-list (tree-left t) 
                          (tree-to-list (tree-right t) rest)))
      rest))

(define (lookup ts i)
  (if (null? ts)
      (error "lookup: index out of bounds")
      (let* ((t (car ts))
             (size (tree-size t)))
        (if (< i size)
            (tree-lookup t i)
            (lookup (cdr ts) (- i size))))))

(define (update ts i y)
  (if (null? ts)
      (error "update: index out of bounds")
      (let* ((t (car ts))
             (size (tree-size t)))
        (if (< i size)
            (cons (tree-update t i y) (cdr ts))
            (cons t (update (cdr ts) (- i size) y))))))

(define (tree-size t)
  (if (tree? t)
      (+ 1 (* 2 (tree-size (tree-left t))))
      0))

(define (tree-lookup t i)
  (if (zero? i)
      (tree-element t)
      (if (even? i)
          (tree-lookup (tree-right t) (quotient (- i 2) 2))
          (tree-lookup (tree-left t) (quotient (- i 1) 2)))))

(define (tree-update t i y)
  (if (zero? i)
      (make-tree y (tree-left t) (tree-right t))
      (if (even? i)
          (make-tree (tree-element t)
                     (tree-left t)
                     (tree-update (tree-right t) (quotient (- i 2) 2) y))
          (make-tree (tree-element t)
                     (tree-update (tree-left t) (quotient (- i 1) 2) y)
                     (tree-right t)))))

Usage Examples

(use-modules (lazy-streams)
             (bankers-queue)
             (skew-binary-list))

;; Streams example
(define nats
  (stream-cons 0
               (stream-map 1+ nats)))

(display "First 5 natural numbers: ")
(let loop ((s nats) (n 5))
  (if (zero? n)
      (newline)
      (begin
        (display (stream-car s))
        (display " ")
        (loop (stream-cdr s) (1- n)))))

;; Banker's Queue example
(define q empty)
(set! q (enqueue q 1))
(set! q (enqueue q 2))
(set! q (enqueue q 3))

(display "Front of queue: ")
(display (front q))
(newline)

(set! q (dequeue q))
(display "Front after dequeue: ")
(display (front q))
(newline)

;; Skew Binary Random-Access List example
(define lst empty)
(set! lst (cons 1 lst))
(set! lst (cons 2 lst))
(set! lst (cons 3 lst))
(set! lst (cons 4 lst))

(display "Element at index 2: ")
(display (lookup lst 2))
(newline)

(set! lst (update lst 1 10))
(display "Element at index 1 after update: ")
(display (lookup lst 1))
(newline)

Conclusion

These implementations demonstrate key concepts from Okasaki's book:

Lazy evaluation with streams
Amortized data structures with Banker's Queues
Numerical representations with Skew Binary Random-Access Lists

The use of Scheme's macros and first-class functions allows for elegant implementations of these advanced functional data structures.