3. Collections¶
A document read from JSON or YAML is Data: a tree of records, lists and
scalars. Data accepts any shape, so the checker knows little about what is
inside it. It cannot add up a Data list, because nothing says the elements
are numbers:
doc : Data = [412, 280, 310]
doc | sum
check error[type-mismatch]: `sum` needs Collection<Int> or Collection<Float> or Collection<Decimal>, not Data
--> <expression>:2:7
|
2 | doc | sum
| ^^^
The same numbers written as a list are a List<Int>, and sum accepts it:
[412, 280, 310] | sum
1002
A collection is a group of values of one type. Its type names the type of
its elements, so every step over it is checked: sum needs numbers, sort
needs values with an order, and List<Int> says the elements are Int.
Lists, sets and maps¶
HQL has three kinds of collection. They differ in what they promise about repeated values, order, and how you find an element:
List<T> |
Set<T> |
Map<K, V> |
|
|---|---|---|---|
| Written | [412, 280, 280] |
{"sf", "novel"} |
Map(["Dune"], [412]) |
| Repeated values | kept | removed | each key once |
| Order | by position, 0 to size - 1 |
none | none |
| Find an element | by position, xs[0] |
by value, contains |
by key, get |
A promise is part of the type, so the checker relies on it. A list has
positions, so xs[0] is allowed. A set has none, so a step that needs
positions is rejected before the program runs. A map's keys are unique, so a
lookup gives at most one value.
The collection types¶
The types at the top are abstract. They have no values of their own and appear in the signatures of functions:
Iterable<T>is anything whose elements can be visited one by one.Collection<T>is a finite group of elements in which a value may occur more than once.size,countandcontainstake anyCollection.Seq<T>is aCollectionin which every element has a position, from0tosize - 1.
The types at the bottom are the ones you build. A List<T> is a Seq<T>. A
Set<T> is a Collection<T> with no repeated values and no positions. A
Map<K, V> is not a Collection at all: it associates keys with values, and
OrderedMap and SortedMap add an order to its keys.
A function that asks for a Collection<Int> accepts both a List<Int> and a
Set<Int>. A function that asks for a Seq<Int> accepts only the list.
From Data to collections¶
Data from outside arrives as Data with no promises. A contract states what
the program expects of it, and a contract field can be a collection:
type BookData : DataContract = {
title: String
tags: List<String>
}
Reading a document as BookData checks every record, and every element of
each tags list. After that, the tags are a List<String> and the usual
steps apply to them:
raw : List<Data> = [
{title: "Dune", tags: ["desert", "spice"]},
{title: "Ubik", tags: ["sf", "desert"]},
]
raw | BookData | flat_map(b => b.tags) | Set
{"desert", "spice", "sf"}
flat_map collects the tags of every book into one list, and Set removes
the repeated "desert". A tag that is not a String is rejected when the
document is read, and the error names the element by its path:
raw : List<Data> = [{title: "Dune", tags: ["desert", 7]}]
raw | BookData | flat_map(b => b.tags) | Set
execute error[contract-violation]: this does not read as BookData: field `tags.1`: 7 is not String
--> <expression>:6:1
|
6 | raw | BookData | flat_map(b => b.tags) | Set
| ^^^^^^^^^^^^^^
= expected: BookData
This is how a program works with data whose shape it does not control. It
leaves most of the document as Data, and names a contract for the part it
uses. Each step after the contract works on typed collections, and the
checker checks it.
Contracts nest. A field can be a list of another contract, and validation follows the document all the way down:
type BookData : DataContract = {
title: String
pages: Int
}
type Shelf : DataContract = {
books: List<BookData>
}
doc : Data = {
owner: "ada",
books: [{title: "Dune", pages: 412}, {title: "Emma", pages: "many"}],
}
doc | Shelf
execute error[contract-violation]: this does not read as Shelf: field `books.1.pages`: "many" is not Int
--> <expression>:13:1
|
13 | doc | Shelf
| ^^^^^^^^^^^
= expected: Shelf
A JSON or YAML document has lists, but no sets and no maps. A JSON object is
a Data record, not a Map. A program builds sets and maps from the typed
lists a contract gives it, as the pages on sets and maps
show.
Conversions are written¶
A value is never converted to another collection type implicitly. Binding a list to a name declared as a set is a type error:
seen : Set<Int> = [1, 2]
seen
check error[type-mismatch]: `seen` is declared Set<Int> but its value is List<Int>; a binding never converts, so construct it: `Set(…)`
--> <expression>:1:19
|
1 | seen : Set<Int> = [1, 2]
| ^^^^^^
Each collection type has a constructor of the same name: List(xs),
Set(xs) and Map(keys, values). A constructor can also be written as a
step, because x | T is T(x):
["novel", "essay", "novel", "poetry"] | Set | size
3
Steps on any collection shows every conversion between the three.
In this chapter¶
| Page | What it covers |
|---|---|
| Lists | positions, indexing and slicing, joining, ordering, pairs |
| Sets | distinct values, membership, union, intersection, difference |
| Maps | lookup by key, keys and values, OrderedMap and SortedMap |
| Steps on any collection | what a step returns, counting, reducing, converting |
How braces write a set, a Data record or an empty map is in
Sets, Data and maps.
What is next¶
Steps take functions, such as b => b.tags and (a, n) => a + n.
Chapter 4 is about functions themselves: naming them,
passing them, and making them generic.