# Inﬁnite vec­tor in Scheme

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

Last mod­i­ﬁed: 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­ﬁ­nite data-struc­ture as a back­end.

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

• when­ever we try to reach a value at po­si­tion `n` equal or greater than the length of a vec­tor, we cre­ate an­other vec­tor of greater size and copy the previous vec­tor in it,
• to han­dle neg­a­tive in­dexes such as `n = -143`, we sim­ply use a sec­ond vec­tor, and use `(abs n)` as an in­dex.

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

• `vector-copy!` as­sumes that `destination` is big­ger than `source`,
• I used `100` as a step value when re­al­lo­cat­ing a vec­tor,
• You can spec­ify the size of `acc-pos` which is used for pos­i­tive in­dexes,
• In its cur­rent state, the code as­sumes that you won’t try to ac­cess a value located at in­dex `n` greater than `100 + vector's length`.

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