We may need more complicated, structured data. Suppose we were interested in processing some property taxes. What is a property? One answer would be the property itself but that property has a lot of other information associated with it that we may also be interested in:
and so on. So a property has a lot more information associated with it than we may have first thought. More importantly, there's no obvious way to think of a property as one of the types we've seen before. Instead, we can see that a property is made up of multiple pieces of information, at least from the point of view of an accountant.
This is the idea behind structures (sometimes also called product types) in Racket. Very often, we will have data that is made up of multiple pieces of information that we would still like to treat as one "thing". For instance, from the example above, it wouldn't make sense to treat the land value for a particular property as its own piece of data—it's only useful to us if it's associated with the tweet.
Let's look at something simpler. We have a lot of built-in types that are fine for handling one number, but what about representations of things like pairs or triples? For instance, suppose we wanted to work with points on a 2-D plane.
Recall that a point $p$ on a plane can be represented by its coordinates $p = (x,y)$, where $x, y \in \mathbb R$. We can do all sorts of things with points, like compute their midpoint. Recall that this is defined for $p_1 = (x_1,y_1)$ and $p_2 = (x_2,y_2)$ by \[mid(p_1, p_2) = \left( \frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right).\]
This seems to give us all the information we need, but we might run into a problem here: what is the type of such a function? A plain reading of this would have us try to write something like \[mid : \mathbb R^2 \times \mathbb R^2 \to \mathbb R^2.\]
If we tried to expand it, we would get something like \[mid : \mathbb R \times \mathbb R \times \mathbb R \times \mathbb R \to \mathbb R \times \mathbb R.\]
This would translate to a type ascription like
(: mid (-> Real Real Real Real Real Real))
which would not really work, since this is the type ascription for a function that takes five Reals as input and produces a single Real.
One unsatisfying solution to this would be to write two different functions—one for the $x$-coordinate and one for the $y$-coordinate:
(: mid-x (-> Real Real Real))
;; Computes the x-coordinate of the midpoint betwen two points (x1,y1) and (x2,y2)
(define (mid-x x1 x2)
(/ (+ x1 x2) 2))
(: mid-y (-> Real Real Real))
;; Computes the y-coordinate of the midpoint betwen two points (x1,y1) and (x2,y2)
(define (mid-y y1 y2)
(/ (+ y1 y2) 2))Wow, gross. Not only is this ridiculous conceptually, it's problematic because there's no way to force someone to use these two functions together on the same pair of points. This is bound to lead to all sorts of errors that could've easily been avoided.
Luckily, Racket gives us a way to define structures for representing compound data. Suppose we want to define a structure for a point. We do this by doing the following.
(define-struct Point
([x : Real]
[y : Real]))This says that we want to define a structure with the name Point. A Point has two fields:
x, which is a Real, and
y, which is also a Real.
Here, we see why these are sometimes referred to as product types. A point is an element of $\mathbb R^2$, which you might also write as $\mathbb R \times \mathbb R$. So in fact, product types are sets of tuples.
There's a very simple way to generalize this construct. If we want to define a structure with the name Structure-Name and fields x-1, x-2, ..., x-n, we write
(define-struct Structure-Name
([x-1 : Type-1]
[x-2 : Type-2]
...
[x-n : Type-n]))Note that just as when defining expressions and functions, we need to tell Racket what types are expected for each field in the structure.
Let's go back to the tweet example. We can create a very basic structure representing a property record that includes some useful information about the property.
(define-struct Property
([address : String]
[land-value : Integer]
[trees : Integer]
[impv-area : Integer]
[district : String]
[pops : Boolean]))So how do we work with structures? When a structure is created, Racket provides a number of functions based on the names of the structure and fields. We'll illustrate this with Point, but keep in mind that the name of the functions will change with the names that you give your structures and their fields.
If we want to bind a name to a Point, we give it the type Point.
(: p Point)To create a Point, we use the make-Point or Point functions. Both of these functions are of type (-> Real Real Point).
(define p (make-Point 4 1/3)) ; both of these are equivalent and
(define p (Point 4 1/3)) ; will bind p to a Point (4, 1/3)Such a function is called a constructor, since it creates an instance of the struct in question. Note that the order in which the constructor assigns values is the order in which the fields are listed in the definition of the structure.
To access a field, we use the functions Point-x and Point-y to get the values x and y, respectively. Both Point-x and Point-y happen to be of type (-> Point Real), because x and y are Real. Of course, this will change depending on the type of the fields.
(Point-x p) ; p is (4, 1/3) so this gives us 4
(Point-y (Point -7.2 1/2)) ; this gives us 1/2These are called accessors, because they give access or allow you to select certain fields in a struct.
To determine whether a value is a Point, we use the predicate Point?. This is a function of type (-> Any Boolean) that tests whether a given expression is a Point.
(Point? p) ; #t
(Point? (Point -7.2 1/2)) ; #t
(Point? 22/7) ; #f
(Point? "this is a point") ; #f Of course, these are all simple enough that we could have written them ourselves, and sometimes it's nice to think through how we would do it, but it is quite convenient that it can be done for us.
Now, we rewrite our distance and midpoint functions from before so that they properly reflect the usage of points.
(: dist (-> Point Point Real))
;; Computes the Euclidean distance betwen two points p1 = (x1,y1) and p2 = (x2,y2)
(define (dist p1 p2)
(sqrt (+ (sqr (- (Point-x p2) (Point-x p1)))
(sqr (- (Point-y p2) (Point-y p1))))))Just as we'd like, we are given Points and can extract the relevant coordinates from those points using the accessors.
More interesting is the midPoint function, where in addition accessing the Points, we are creating a Point as well.
(: midp (-> Point Point Point))
;; Computes the midpoint betwen two points p1 = (x1,y1) and p2 = (x2,y2)
(define (midp p1 p2)
(Point (/ (+ (Point-x p1) (Point-x p2)) 2)
(/ (+ (Point-y p1) (Point-y p2)) 2)))We can now use Points in the same way we'd use any other kind of value.
One thing that you may have realized as you have been writing programs is that there are many situations where you have to repeat certain expressions. For example, consider the following function for determining which quadrant a point lies in.
(: quad (-> Point Integer))
;; Given a point, which quadrant does it lie in?
(define (quad p)
(cond
[(and (> (Point-x p) 0) (> (Point-y p) 0)) 1]
[(and (< (Point-x p) 0) (> (Point-y p) 0)) 2]
[(and (< (Point-x p) 0) (< (Point-y p) 0)) 3]
[(and (> (Point-x p) 0) (< (Point-y p) 0)) 4]
[else 0]))
That is a lot of repeated calls to Point-x and Point-y. We tend to run into this issue a lot when working with structures.
Instead of writing those expressions over and over again, it would be nice if we could just give it a name and refer to the name. One might remember that we have a mechanism for this: the define keyword, but this doesn't really suit our purposes. The big problem with this is that the definitions that we're interested in depend on the inputs of a particular function.
Luckily, there is a way to do this. These are called local definitions. Here is how to deploy them.
(: quad (-> Point Integer))
;; Given a point, which quadrant does it lie in?
(define (quad p)
(local
{(define x (Point-x p))
(define y (Point-y p))}
(cond
[(and (> x 0) (> y 0)) 1]
[(and (< x 0) (> y 0)) 2]
[(and (< x 0) (< y 0)) 3]
[(and (> x 0) (< y 0)) 4]
[else 0]))
The general form of this expression is
(local
{defn-1
defn-2
...
defn-n}
expr)
Here, the defns are regular old definitions and expr is an expression, as usual. The interpretation of this expression is as follows: within this expression, we have the definitions as defined. In essence, what we've really done is defined a bunch of definitions specificially for use in expr.
One issue that gets introduced with this notion is the idea of scope. The problem arises when you reuse names. Here's a simple example
(: add1x (-> Integer Integer))
;; Adds 1 to x, given
(define (add1x x)
(add1 x))
(: sub1x (-> Integer Integer))
;; subtracts 1 from x, given
(define (sub1x x)
(sub1 x))
It is fairly clear in this case that these two names are different: they only exist within their own functions. Where it is perhaps less clear is when we have situations like the following.
(local
{(define x 100)}
(+ (local
{(define x 30)
(define y 22)}
(+ x y))
x))
Generally, the rule for scope is quite simple: the name to use is the one that's the "closest". So in the expression above, we can systematically evaluate it as usual. Since the names are "bound" to the closest definition, the innermost expression (+ x y) will evaluate to 52. Then the result of this is added to x which is defined to be 100 and we arrive at the value 152.
As an aside, the rules for scope come to us from mathematical logic, where they tend to have fewer possible names. However, the same rules apply: the name gets bound to the closest quantifier. For instance, in the statement \[\forall x (P(x) \wedge \neg \exists y \forall x Q(x,y)),\] the two $x$'s are bound to different quantifiers.