### 12` `Collections of Structured Data

The set of messages matching a tag.

The list of messages in a conversation.

The set of friends of a user.

Do Now!

How are collective data different from structured data?

In structured data, we have a fixed number of possibly different kinds of values. In collective data, we have a variable number of the same kind of value. For instance, we don’t say up front how many songs must be in a playlist or how many pages a user can have; but every one of them must be a song or a page. (A page may, of course, be conditionally defined, but ultimately everything in the collection is still a page.)

Observe that we’ve mentioned both sets and lists above. The difference between a set and a list is that a set has no order, but a list has an order. This distinction is not vital now but we will return to it later [Sets as Collective Data].

A family tree of people.

The filesystem on your computer.

A seating chart at a party.

A social network of pages.

We have already seen tables [Introduction to Tabular Data], which are a form of collective, structured data. Now we will look at a few more, and how to program them.

#### 12.1` `Lists as Collective Data

`song-list = [list: lver, so, wnkkhs]`

```
check:
song-list.length() is 3
song-list.first is lver
end
```

Thus, what we have seen earlier about building functions over lists
[Processing Lists] applies here too. To illustrate, suppose
we wish to write the function `oldest-song-age`

, which consumes a
list of songs and produces the oldest song in the list. (There may be
more than one song from the same year; the age—

`lvar`

.
```
oldest-song([list: lver, so, wnkkhs]) is lvar
oldest-song([list: so, wnkkhs]) is wnkkhs
oldest-song([list: wnkkhs]) is wnkkhs
oldest-song([list: ]) is ???
```

What do we write in the last case? Recall that we saw this problem
earlier [`my-max`

: Examples]: there is no answer in the empty case. In
fact, the computation here is remarkably similar to that of
`my-max`

, because it is essentially the same computation, just
asking for the minimum year (which would make the song the
oldest).

From our examples, we can see a solution structure echoing that of
`my-max`

. For the empty list, we signal an error. Otherwise, we
compute the oldest song in the rest of the list, and compare its year
against that of the first. Whichever has the older year is the answer.

```
fun oldest-song(sl :: List<ITunesSong>) -> ITunesSong:
cases (List) sl:
| empty => raise("not defined for empty song lists")
| link(f, r) =>
cases (List) r:
| empty => f
| else =>
osr = oldest-song(r)
if osr.year < f.year:
osr
else:
f
end
end
end
end
```

Note that there is no guarantee there will be only oldest song, and
this is reflected in the possibility that `osr.year`

may
equal `f.year`

. However, our problem statement allowed us
to pick just one such song, which is what we’ve done.

Do Now!

Modify the solution above to

`oldest-song-age`

, which computes the age of the oldest song(s).

```
fun oldest-song-age(sl :: List<ITunesSong>) -> Number:
os = oldest-song(sl)
song-age(os)
where:
oldest-song-age(song-list) is 71
end
```

#### 12.2` `Sets as Collective Data

Your Web browser records which Web pages you’ve visited, and some Web sites use this information to color visited links differently than ones you haven’t seen. This color is typically independent of how many times you have visited the page.

During an election, a poll agent might record that you have voted, but does not need to record how many times you have voted, and does not care about the order in which people vote.

`song-set = [set: lver, so, wnkkhs]`

Do Now!

How can we tell whether Pyret cares about the order?

```
check:
song-set2 = [set: so, wnkkhs, lver]
song-set is song-set2
end
```

Exercise

How many different orders are there?

```
check:
song-set3 = [set: lver, so, wnkkhs, so, so, lver, so]
song-set is song-set3
song-set3.size() is 3
end
```

##### 12.2.1` `Picking Elements from Sets

This lack of an ordering, however, poses a problem. With lists, it was
meaningful to talk about the “first” and corresponding “rest”. By
definition, with sets there is not “first” element. In fact, Pyret
does not even offer fields similar to `first`

and `rest`

. In
its place is something a little more accurate but complex.

The `.pick`

method returns a random element of a set. It
produces a value of type `Pick`

(which we get from the
`pick`

library). When we pick an element, there are two
possibilities. One is that the set is empty (analogous to a list being
empty), which gives us a `pick-none`

value. The other option is
called `pick-some`

, which gives us an actual member of the set.

`pick-some`

variant of `Pick`

has two fields, not
one. To understand why takes a moment’s work. Let’s explore it by
choosing an element of a set:
```
fun an-elt(s :: Set):
cases (Pick) s.pick():
| pick-none => raise("empty set")
| pick-some(e, r) => e
end
end
```

`r`

field in the
`pick-some`

case.)Do Now!

Can you guess why we didn’t write examples for

`an-elt`

?

Do Now!

Run

`an-elt(song-set)`

. What element do you get?Run it again. Run it five more times.

Do you get the same element every time?

Do Now!

Given that

`an-elt`

does not return a predictable element, what (if any) tests can we write for it?

`an-elt`

will
produce, we do know it will produce an element of the set. Therefore,
what we can write are tests that ensure the resulting element is a
member of the set—##### 12.2.2` `Computing with Sets

Once we have picked an element from a set, it’s often useful to obtain
the set consisting of the remaining elements. We have already seen
that choosing the first field of a `pick-some`

is similar to
taking the “first” of a set. We therefore want a way to get the
“rest” of the set. However, we want the rest to what we obtain after
excluding this particular “first”. That’s what the second
field of a `pick-some`

is: what’s left of the set.

`my-len`

[Some Example Exercises]:
```
fun my-set-size(shadow s :: Set) -> Number:
cases (Pick) s.pick():
| pick-none => 0
| pick-some(e, r) =>
1 + my-set-size(r)
end
end
```

`my-len`

, the random nature of picking elements makes it harder to
write examples that the actual function’s behavior will match.#### 12.3` `Combining Structured and Collective Data

As the above examples illustrate, a program’s data organization will often involve multiple kinds of compound data, often deeply intertwined. Let’s first think of these in pairs.

Exercise

Come up with examples that combine:

structured and conditional data,

structured and collective data, and

conditional and collective data.

You’ve actually seen examples of each of these above. Identify them.

Finally, we might even have all three at once. For instance, a filesystem is usually a list (collective) of files and folders (conditional) where each file has several attributes (structured). Similarly, a social network has a set of pages (collective) where each page is for a person, organization, or other thing (conditional), and each page has several attributes (structured). Therefore, as you can see, combinations of these arise naturally in all kinds of applications that we deal with on a daily basis.

Exercise

Take three of your favorite Web sites or apps. Identify the kinds of data they present. Classify these as structured, conditional, and collective. How do they combine these data?