Sitelet https://beautifulracket.com/explainer/data-structures.html
Thank you for your comment

Beau­tiful Racket / explainers

Data structures

Racket’s data struc­tures have distinct char­ac­ter­is­tics that often recom­mend one over another for a partic­ular job:  + Chart adapted from Jens Axel Søgaard.

Struc­tureAccessValuesIndexMutable?
pairrandomtwonothingno
listsequentialvariablenothingno
hash tablerandomvariablekeysoptional
association listsequentialvariablecarno
vectorrandomfixedintegersoptional
structure typerandomfixedidentifiersoptional

Hash tables, vectors, and struc­ture types are avail­able in mutable (meaning, internal values can be changed) and immutable vari­ants. As a rule, unless you need a mutable struc­ture, choose an immutable one, because Racket can better opti­mize immutable struc­tures for speed.

Pairs

A pair holds two values. A pair is made with cons, and the values can be retrieved with car and cdr. If you’ve got exactly two values, great. If you’ve got more, look else­where.

Lists

A list holds any number of values. Because lists are made from a sequence of linked pairs, they’re opti­mized for sequen­tial access, and thus are the char­ac­ter­istic data struc­tures used in iter­a­tion and recur­sion. Random access (with list-ref) is feasible with short lists. For long lists, random access can be slow, so a vector is the better option.

Vectors

A vector is an array of values, indexed by loca­tion and opti­mized for random access. Though vectors come in immutable and mutable vari­ants, the length of a vector is always fixed.  + But see grow­able vectors, which can be resized.

A basic mutable vector can be made with vector. Values are retrieved with vector-ref, and changed with vector-set!:

(define vec (vector 'sym "str" 42))
vec ; '#(sym "str" 42)
(vector-ref vec 0) ; 'sym
(vector-ref vec 1) ; "str"
(vector-ref vec 2) ; 42
(vector-set! vec 0 'foo)
(vector-set! vec 1 "bar")
vec ; '#(foo "bar" 42)
(vector-set! vec 1 25)
vec ; '#(foo 25 42)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
(define vec (vector 'sym "str" 42))
vec ; '#(sym "str" 42)
(vector-ref vec 0) ; 'sym
(vector-ref vec 1) ; "str"
(vector-ref vec 2) ; 42
(vector-set! vec 0 'foo)
(vector-set! vec 1 "bar")
vec ; '#(foo "bar" 42)
(vector-set! vec 1 25)
vec ; '#(foo 25 42)
copy to clipboard

Vectors and lists can be mutu­ally converted with vector->list and list->vector.

Hash tables

A hash table is a mapping of keys to values, which can them­selves be any data type. Hash values can be retrieved with hash-ref:

(define ht (hash
            'foo "bar"
            '(1 2 3) expt
            42 #'(start-zombie-apocalypse)))

(hash-ref ht '(1 2 3)) ; #<procedure:expt>
(hash-ref ht 42) ; #<syntax:5:17 (start-zombie-apocalypse)>
(hash-ref ht 'foo) ; "bar"
1
2
3
4
5
6
7
8
(define ht (hash
            'foo "bar"
            '(1 2 3) expt
            42 #'(start-zombie-apocalypse)))

(hash-ref ht '(1 2 3)) ; #<procedure:expt>
(hash-ref ht 42) ; #<syntax:5:17 (start-zombie-apocalypse)>
(hash-ref ht 'foo) ; "bar"
copy to clipboard

A hash table can be mutable—meaning, values can be added, deleted, or updated—or immutable. An immutable hash table is created with hash (as demon­strated above). A mutable hash table is created with make-hash, and then can be changed with hash-set!:

(define mht (make-hash))
(hash-set! mht 'foo "bar")
(hash-ref mht 'foo) ; "bar"
(hash-set! mht 'foo 42)
(hash-ref mht 'foo) ; 42
1
2
3
4
5
(define mht (make-hash))
(hash-set! mht 'foo "bar")
(hash-ref mht 'foo) ; "bar"
(hash-set! mht 'foo 42)
(hash-ref mht 'foo) ; 42
copy to clipboard

By default, a hash table uses equal? to compare keys. Hash tables that use the faster equality func­tions (eq? and eqv?) are also avail­able. If your keys are only symbols, you can use hasheq or make-hasheq; if your keys are only symbols or numbers, you can use hasheqv or make-hasheqv.

A vector is faster than a hash table, so if you can use sequen­tial inte­gers for keys, a vector is the better choice.

Asso­ci­a­tion lists

The humble asso­ci­a­tion list is often over­looked for small jobs. It’s not a distinct data struc­ture, but rather a list where every element is a pair that holds a key and value (aka an asso­ci­a­tion):

(define assns (list (cons 'k1 "v1") (cons 'k2 "v2")))
assns ; '((k1 . "v1") (k2 . "v2"))
1
2
(define assns (list (cons 'k1 "v1") (cons 'k2 "v2")))
assns ; '((k1 . "v1") (k2 . "v2"))
copy to clipboard

Asso­ci­a­tion lists are easy to make and break, with the help of map:

(define assns (map cons (range 5) '(a b c d e)))
assns ; '((0 . a) (1 . b) (2 . c) (3 . d) (4 . e))
(define keys (map car assns))
keys ; '(0 1 2 3 4)
(define vals (map cdr assns))
vals ; '(a b c d e)
1
2
3
4
5
6
(define assns (map cons (range 5) '(a b c d e)))
assns ; '((0 . a) (1 . b) (2 . c) (3 . d) (4 . e))
(define keys (map car assns))
keys ; '(0 1 2 3 4)
(define vals (map cdr assns))
vals ; '(a b c d e)
copy to clipboard

As lists, asso­ci­a­tion lists work with the usual list func­tions. They can also be used with assoc (and its vari­ants assv, assq, and assf) to find partic­ular element pairs:

(define assns (map cons (range 5) '(a b c d e)))
(assoc 3 assns) ; '(3 . d)
1
2
(define assns (map cons (range 5) '(a b c d e)))
(assoc 3 assns) ; '(3 . d)
copy to clipboard

Asso­ci­a­tion lists also can be used in a hash-table-ish way with generic dictio­nary func­tions like dict-ref:

(require racket/dict)
(define assns (map cons (range 5) '(a b c d e)))
(dict-ref assns 3) ; 'd
1
2
3
(require racket/dict)
(define assns (map cons (range 5) '(a b c d e)))
(dict-ref assns 3) ; 'd
copy to clipboard

Struc­ture types

A struc­ture type is a user-defined data struc­ture with an arbi­trary number of fields. Like a hash table, a struc­ture type allows access to its fields by name. Like a vector, the number of fields is fixed by the struc­ture-type defi­n­i­tion.

The struct form defines the struc­ture type itself, and also manu­fac­tures a pred­i­cate, plus getters (and, for mutable struc­ture types, setters) for each field. The #:transparent option makes the struc­ture type print­able in the REPL:

(struct style (color size weight) #:transparent #:mutable)
(define s (style "red" 42 'bold))
s ; (style "red" 42 'bold)
(style? s) ; #t
(style-color s) ; "red"
(set-style-color! s "blue")
(style-color s) ; "blue"
1
2
3
4
5
6
7
(struct style (color size weight) #:transparent #:mutable)
(define s (style "red" 42 'bold))
s ; (style "red" 42 'bold)
(style? s) ; #t
(style-color s) ; "red"
(set-style-color! s "blue")
(style-color s) ; "blue"
copy to clipboard

It’s not uncommon for a Rack­e­teer to throw some values into a list as a quick-and-dirty data struc­ture. But for anything that will be used more than once, a struc­ture type is better:

  1. The getters and setters have read­able names.

  2. The struc­ture type can have fields added to its defi­n­i­tion without changing existing refer­ences.

  3. An instance of a struc­ture type is repre­sented as a single object in memory, so it can be passed around a program “by refer­ence” (meaning, it’s not dupli­cated if passed from one func­tion to another).

  4. A struc­ture type has its own unique pred­i­cate, which can be effi­ciently tested (say, inside a contract).

The disad­van­tage of a struc­ture type is that it’s a distinct data type from a hash table, vector, or list, so it can’t be directly used with library func­tions that consume those types. There’s a little more house­keeping to get values in & out.

Classes

Classes—in the object-oriented program­ming (OOP) sense—are a big deal in many languages. But not in Racket.

Racket has them, of course. They’re used in a couple parts of the library (most promi­nently, the GUI frame­work). Other­wise, rarely. In DSLs, almost never.

Why is that? OOP encour­ages program­mers to think about func­tions as things that are tucked inside data struc­tures as “methods”. Classes them­selves often rely on state and muta­tion.

Whereas with func­tional program­ming gener­ally, and Racket in partic­ular, we’re encour­aged to think about data struc­tures as things that are consumed by func­tions. And of course, to avoid state and muta­tion where possible. So it’s an inver­sion of priority.

Thus, as a conse­quence of the func­tional style, most Rack­e­teers don’t find classes neces­sary. But they aren’t avoiding OOP as a polit­ical gesture. If you want to rock it OOP-style in Racket, go ahead. No one will ever say you’re wrong.

← prev next →