Point, this is not a huge issue, since both components of the pair are Real. But if we had a non-polymorphic pair with fixed types like our IntStringPair, we'd have to go through with defining an entirely separate type, something like StringIntPair which seems like a huge waste of time and effort. Instead, we can do the following:
(: exchange (All (A B) (-> (Pairof A B) (Pairof B A))))
;; Given an arbitrary pair (x,y), produce the pair (y,x)
(define (exchange pair)
(match pair
[(Pairof x y) (Pairof y x)]))
Let's define another recursive polymorphic type. We've seen binary trees, but one might wonder why we even need two children for each tree in the first place. What if we only had one? In this sense, we can define a unary tree.
Formally, a unary tree is either
This gives us the following type definition.
(define-type (UnaryTree A) (U 'Empty (Cons A)))
(define-struct (Cons A)
([root : A]
[sub : (UnaryTree A)]))
This definition looks as you'd expect. We can program with these in the same way as we've done with other recursive structures. Here we use the name Cons to avoid clashing with the name Node (in case you're using the same file as last class) and for more intriguing reasons that we'll see shortly.
We can try writing some functions. First, let's figure out the size of our tree. As before, we want to define this recursively: we know that the size of an empty tree is 0 and the size of a non-empty tree is going to be one more than the size of the subtree.
(: size (All (A) (-> (UnaryTree A) Integer)))
;; Computes the number of nodes in a unary tree
(define (size t)
(match t
['Empty 0]
[(Cons first rest) (+ 1 (size rest))]))
This turns out to be slightly simpler than the binary tree, since we only have one subtree to deal with. Because of this, traversing down a tree becomes much less complex—notice that unlike binary trees, there is no question of the order in which we visit nodes.
Let's write a few functions. The first will take a unary tree of strings and produce a unary tree with the lengths of those strings.
(: strings-lengths (-> (UnaryTree String) (UnaryTree Integer)))
;; Given a unary tree of strings, computes a unary tree with each
;; string's length
(define (first-letter t)
(match t
['Empty 'Empty]
[(Cons first rest) (Cons (string-length first)
(strings-lengths rest))]))
The next function that we'll write does almost the same thing, but it discriminates: given a tree of integers, we want to keep only those integers that are less than 140.
(: lte140 (-> (UnaryTree Integer) (UnaryTree Integer)))
;; Given a unary tree of integers, produce a unary tree with only those
;; integers that are at most 140
(define (lte140 t)
(match t
['Empty 'Empty]
[(Cons first rest) (if (<= first 140)
(Cons first (lte140 rest))
(lte140 rest))]))
This function is a first hint at one of the consequential differences in the structure of unary trees and binary trees. Suppose we were to try the same thing on a set of integers in a binary tree. The problem arises when we try to remove a node: how do we preserve the property of a binary tree? This is not quite as simple as what we do with the unary tree, which is simply to skip over the value.
Our last function for today is involves some aggregation. We want to plot some points, given as (Pairof Integer Integer) on to an image.
(: points (-> (UnaryTree (Pairof Integer Integer)) Image))
;; Plots points (with x and y between 0 and 100) onto a square of
;; size 100 by 100. Points with coordinates outside of this range
;; are not displayed.
(define (points pts)
(match pts
['Empty (empty-scene 100 100)]
[(Cons (Pairof x y) rest)
(place-image (circle 2 'solid 'red)
x y
(points rest))]))
This one is interesting in how we set it up: instead of having an empty base case as usual, we make our base case a blank canvas on which we put our points. This is another point of departure from binary trees. With a binary tree, we would not be able to use the same trick of making the base case the background for our plot, since every leaf in the tree has two "base cases" from which to work with.