Fun with Racket and Associative Lists
Let's start with the idea of an associative list. An alist is basically a list of lists, where the first value of each inner list is a key and the second is a value. Here are a few alists, in different langauges:
[["name", "foo"], ["occupation", "bar"], ["age", 20]] #Python
'((name . "foo") (occupation . "bar") (age . 20)) ; Racket
Why would you want to do this when dictionaries are so convenient? You wouldn't. Alists predate dictionaries. They're old, and you'll generally find something better. That said, they're a convenient tool to reach for when using Lisp-based languages, and if you're recursively acting on key-value pairs they should be more efficient than hash tables.
First, let's start with a few procedures to manipulate alists.
(assoc key alst)
Assoc takes an alist named alst, and a symbol named key (Note: symbols are like enums, but you don't need to pre-define them). If it finds a key-value pair with the same key, it returns that. If not, it returns a boolean False.
(define (alist-delete alst key)
(filter-not (lambda (x) (equal? (car x) key)) alst))
This is a procedure made to return a new alist without the given key. It effectively deletes that key-value pair from the alist. We have to define this, because as far as I can tell Racket does not have this in it's standard library.
(define (alist-add alst pair)
(if (assoc (car pair) alst)
(alist-add (alist-delete alst (car pair)) pair)
(cons pair alst)))
This procedure returns a new alist, and adds a new pair to it. If the given pair already exists, it overwrites the pair previously in the alist. We overwrite the previous pair by adding it to a version of the alist with that pair deleted.
Now let's make an alist constructor, so we can guarantee any alist made with it will have specific values:
(define (person #:x x #:y y #:name name)
`((x . ,x) (y . ,y) (name . ,name)))
This procedure definition uses keywords, so you don't have to remember the order of it's arguments. It returns an alist representing a person, with x and y coordinates and a name.
My goal is to make a procedure that takes an alist of directions, and a person, and make them move in those directions. Here it is:
(define (parse-instructions instructions person)
(if (empty? instructions)
person
(let* ((todo (car (car instructions)))
(amount (cdr (car instructions)))
(move-person
(lambda (key operator)
(alist-add person
(cons key
(operator
(cdr (assoc key person))
amount))))))
(parse-instructions
(cdr instructions)
(match todo
('up (move-person 'y +))
('down (move-person 'y -))
('left (move-person 'x -))
('right (move-person 'x +)))))))
That's a pretty spicy procedure. Let's break it down.
The procedure takes an alist of instructions and a person. The first thing it does is to check whether the alist of instructions is empty. If it is, it gives us the person.
If the alist of instructions contains instructions, it skims the first instruction off the top of the alist, moves the person by said first instruction, and does everything all over again with the rest of the instruction alist.
This is a recursive procedure. It runs itself, but every time it does so it removes the instruction it just did. Eventually the list of instructions will empty, which is why the first thing it does is check whether the instruction list is empty.
While writing the procedure, I noticed that I was copy-pasting code for each instruction. I grouped the copied code into a procedure named move-person, and it has made the code easier to read. It takes a key ('x or 'y) and an operator (+ or –) and moves the key coordinate by adding to or subtracting from it. Essentially it abstracts the movement into “When you go left you subtract from the x axis”, and “when you go up you add to the y axis”, which is pretty neat.
Let's put it to the test.
(define my-instructions
'((up . 10)
(left . 3)
(up . 3)
(right . 15)
(down . 2)))
(define my-guy
(person #:x 0 #:y 0 #:name "foo"))
(parse-instructions my-instructions my-guy)
-> '((y . 11) (x . 12) (name . "foo"))