Vector in scheme

1
votes

From the documentation of equals? in Racket:

Equal? recursively compares the contents of pairs, vectors, and strings, applying eqv? on other objects such as numbers and symbols. A rule of thumb is that objects are generally equal? if they print the same. Equal? may fail to terminate if its arguments are circular data structures.

(equal? 'a 'a)                          ===>  #t`
(equal? '(a) '(a))                      ===>  #t`

What exactly is a vector in scheme? For example, is (1. 2) a vector? Is (1 2) a vector? Is (1 2 3 4) a vector? etc.

The docs list the mention of vector and vector? etc, but I'm wondering if they just use vector to mean "list" or something else: https://people.csail.mit.edu/jaffer/r5rs/Disjointness-of-types.html#Disjointness-of-types

1
schemelispracket
FYI they barely mention vectors in SICP, you won't hear about them until the later chapters. Singly-linked lists are the preferred data structure in Scheme. – Óscar López
BTW if you are doing SICP, they use MIT scheme which also has documentation online. If you are using a different version, it may still be a good idea to read what it has to say: web.mit.edu/scheme_v9.2/doc/mit-scheme-ref/index.html – Justin Meiners

1 Answers

2
votes

A vector is, well, a vector. It's a different data structure, similar to what we normally call an "array" in other programming languages. It comes in two flavors, mutable and immutable - for example:

(vector 1 2 3) ; creates a mutable vector via a procedure call
=> '#(1 2 3)

'#(1 2 3) ; an immutable vector literal
=> '#(1 2 3)

(vector-length '#(1 2 3))
=> 3

(vector-ref '#(1 2 3) 1)
=> 2

(define vec (vector 1 2 3))
(vector-set! vec 1 'x)
vec
=> '#(1 x 3)

You might be asking yourself what are the advantages of a vector, compared to a good old list. Well, that mutable vectors can be modified it in place, and accessing an element given its index is a constant O(1) operation, whereas in a list the same operation is O(n). Similarly for the length operation. The disadvantage is that you cannot grow a vector's size after it's created (unlike Python lists); if you need to add more elements you have to create a new vector.

There are lots of vector-specific operations that mirror the procedures available for lists; we have vector-map, vector-filter and so on, but we also have things like vector-map! that modify the vector in-place, without creating a new one. Take a look at the documentation for more details!