Infinite vec­tor in Scheme

Created: Fri Dec 7 15:12:36 CET 2018

Last mod­i­fied: Fri Mar 8 17:55:47 CET 2019


While im­ple­ment­ing the 5command lan­guage (which is like brain­fuck with­out loops) I needed an in­fi­nite data-struc­ture as a back­end.

My ap­proach is the fol­low­ing:

This works in Chez Scheme. Just add the fol­low­ing de­f­i­n­i­tion of er­ror for dif­fer­ent im­plem­n­ta­tions.

(define (error . args)
  (begin
    (display args)
    (newline)
    (exit 1)))

Limitations

Regarding the last state­ment, you can re­place 100 with a value de­rived from the dif­fer­ence be­tween (abs n) and the vec­tor’s length in the code list­ing below

Code list­ings

(define (make-infinite-vector n x)
  (define acc-pos (make-vector n x))
  (define acc-neg (make-vector 1 x))
  (define (vector-copy! source destination)
    (define (helper i)
      (if (= (vector-length source) i)
          destination
          (begin
            (vector-set! destination
                         i
                         (vector-ref source i))
            (helper (+ i 1)))))
    (helper 0))
  (lambda (command . args)
    (define (select-vector n)
      (let ((vec (if (> n 0) acc-pos acc-neg)))
        (if (>= (abs n) (vector-length vec))
            (if (> n 0)
                (begin
                  (set! acc-pos
                        (make-vector
                          (+ 100
                             (vector-length acc-pos))
                          x))
                  (vector-copy! vec acc-pos))
                (begin
                  (set! acc-neg
                        (make-vector
                          (+ 100
                             (vector-length acc-neg))
                          x))
                  (vector-copy! vec acc-neg)))
            vec)))
    (define (infinite-vector-set! n x)
      (vector-set! (select-vector n) (abs n) x))
    (define (infinite-vector-ref n)
      (vector-ref (select-vector n) (abs n)))
    (case command
      ('set! (infinite-vector-set! (car args)
                                   (cadr args)))
      ('ref (infinite-vector-ref (car args)))
      (else (error 'infinite-vector
                   "Not a proper instruction"
                   command)))))

Usage ex­am­ple:

(define vec (make-infinite-vector 10 0))

; fills the vector with a thousand 'item
(let f ((i 1000))
  (begin
    (vec 'set! i 'item) 
    (format #t
            "New value at ~a is: ~a~%"
            i
            (vec 'ref i))
    (if (zero? i)
        'done
        (f (- i 1)))))

source code