prelude: maps and sets
Maps from keys to values, and sets of values each held once
Functions on map(k, v) and set(a), and list.groupBy, which gives a map. They are attached definitions on map and set, so m \insert(k, v) resolves to map.insert when m is a map, and are in the prelude, so no import is needed. Maps and sets are immutable: every function gives back a new one. For now a map keeps its entries in the order their keys were first added, a set its elements in the order they were first added, and a lookup takes time in proportion to the size (see Maps and sets).
Maps
A map(k, v) holds one value of type v for each of its keys, of type k. It is written with the square-bracket literal syntax and =>, and calling a map looks a key up:
def prices = ["tea" => 3, "cake" => 4]
println(prices("tea"))
println(prices("pie"))
-- #some(3)
-- #notFound
A literal whose items are all key => value is a map(k, v). A key written twice in a literal holds the value written last. [] is the empty list unless a map is expected, as in def none: map(string, int) = []; map.empty is the empty map anywhere. for prices | name, price -> ... walks a map’s entries.
A map’s keys need an Eq and a Hash of their type, so every function that looks one up requires [Eq(k), Hash(k)]. Numbers, strings, tags, records, tuples and lists can all be keys, and so can a nominal type that attaches its own == and hash; a type that holds a function cannot, and nor can a nominal type that attaches == without hash. When the keys are tags of different names, write the key type, as in def lights: map(#red | #green, string) = ...: inference does not yet join the tags of separate keys. Two maps are == when they hold the same keys, each with an equal value, whatever order the keys were added in; the values are compared by their own Eq. Maps cannot be ordered with <, or be keys themselves, yet.
A map can be printed and interpolated when its keys and values can: it is written as its literal is, its entries in the order its keys were first added, each key and value by its own ToString. The empty map is written [=>].
"{["tea" => 3, "cake" => 1]}" -- "[tea => 3, cake => 1]"
Sets
A set(a) holds each of its elements once. There is no set literal yet: a set is made from a list with set.fromList, or from set.empty with set.insert. Literals that build any collection type, through the target type’s builder, are planned; see Collections. for s | x -> ... walks a set’s elements.
def seen = set.fromList([3, 1, 3, 2])
println(set.contains(seen, 2))
println(set.length(seen))
-- true
-- 3
A set’s elements need an Eq and a Hash of their type, as a map’s keys do, so every function that looks one up requires [Eq(a), Hash(a)]. Two sets are == when they hold the same elements, whatever order they were added in. Sets cannot be ordered with <, or be keys or elements of a set, yet. A set can be printed and interpolated when its elements can: it is written as set.toList of it would be, "{set.fromList([3, 1, 3])}" as "[3, 1]".
Reference
map.empty
def map.empty: map(k, v)
The map with no keys. [] where a map is expected is this map.
map.fromList
def map.fromList: [Eq(k), Hash(k)] list((k, v)) -> map(k, v)
The map holding each of entries, in order: of two entries with the same key, the later wins.
map.fromArray
def map.fromArray: [Eq(k), Hash(k)] array((k, v)) -> map(k, v)
The map holding each of entries, in order: of two entries with the same key, the later wins.
What a literal builds a map with where a map is expected, as [] is, or written map[...].
map.fromSeq
def map.fromSeq: [Eq(k), Hash(k), c] ([c] seq((k, v))) -> map(k, v)
The map holding each of the entries of s, pulled now, in order: of two entries with the same
key, the later wins, as in map.fromList. It requires the contexts the sequence’s steps do.
map.build
def map.build: [Eq(k), Hash(k), c, d] ([c] () -> [d] seq((k, v))) -> map(k, v)
The map of the entries block yields: map.build { yield ("a", 1) }. The same as
seq(block) \map.fromSeq.
map.toList
def map.toList: map(k, v) -> list((k, v))
The entries of m, each a key and its value, in the order the keys were first added.
map.toSeq
def map.toSeq: map(k, v) -> seq((k, v))
The entries of m as a sequence of key-value pairs, in the order map.toList gives them.
map.get
def map.get: [Eq(k), Hash(k)] map(k, v), k -> #some(v) | #notFound
The value m holds for key, or #notFound. Calling the map, m(key), is the same.
map.containsKey
def map.containsKey: [Eq(k), Hash(k)] map(k, v), k -> bool
Whether m holds a value for key.
map.insert
def map.insert: [Eq(k), Hash(k)] map(k, v), k, v -> map(k, v)
m with key holding value, in place of any value it held before.
map.remove
def map.remove: [Eq(k), Hash(k)] map(k, v), k -> map(k, v)
m without key or its value. A map that has no key is given back as it is.
map.length
def map.length: map(k, v) -> int
The number of keys.
list.groupBy
def list.groupBy: [Eq(b), Hash(b), c] list(a), ([c] a -> b) -> map(b, list(a))
The elements of xs grouped by key: a map from each key to the elements that have it, in
order. The keys are in the order they first appear.
map.keys
def map.keys: map(k, v) -> list(k)
The keys of m, in the order they were first added.
map.values
def map.values: map(k, v) -> list(v)
The values of m, in the order their keys were first added.
map.isEmpty
def map.isEmpty: map(k, v) -> bool
Whether m has no keys.
map.fold
def map.fold: [c] map(k, v), b, ([c] (b, k, v) -> b) -> b
step applied to acc and each key and value of m in turn, in the order of map.toList.
map.reduce
def map.reduce: [c] map(k, v), ([c] (v, v) -> v) -> #some(v) | #none
The values of m combined with f, in order, starting from the first: ["a" => 4, "b" => 5] \map.reduce { * } is #some(20), and an empty map, having no first value, gives #none. To
start from another value, use map.fold.
map.map
def map.map: [c] map(k, v), ([c] v -> w) -> map(k, w)
m with f applied to each value. The keys stay as they are, in the same order.
map.filter
def map.filter: [c] map(k, v), ([c] (k, v) -> bool) -> map(k, v)
The entries of m whose key and value pass keep, in the same order.
map.filterMap
def map.filterMap: [c] map(k, v), ([c] (k, v) -> #some(w) | #skip) -> map(k, w)
The entries of m whose key and value f gives #some for, each with the new value it gives,
in the same order: a map.filter and a map.map in one walk. Keys f gives #skip for
are left out.
map.any
def map.any: [c] map(k, v), ([c] (k, v) -> bool) -> bool
Whether test holds for any key and its value (so false for an empty map). It stops at the
first entry it holds for.
map.all
def map.all: [c] map(k, v), ([c] (k, v) -> bool) -> bool
Whether test holds for every key and its value (so true for an empty map). It stops at the
first entry it fails for.
map.update
def map.update: [Eq(k), Hash(k), c] map(k, v), k, ([c] #some(v) | #notFound -> v) -> map(k, v)
m with key holding f of what m holds for it, #some(value) or #notFound. A key m
does not have is added at the end.
map.union
def map.union: [Eq(k), Hash(k)] map(k, v), map(k, v) -> map(k, v)
The entries of m, then those of other whose keys m does not have. Where both have a key,
the value is other’s, as a later entry wins in map.fromList, so defaults \map.union(overrides)
gives the overrides.
map.unionWith
def map.unionWith: [Eq(k), Hash(k), c] map(k, v), map(k, v), ([c] (v, v) -> v) -> map(k, v)
As map.union, but where both have a key the value is combine of m’s value and other’s.
set.empty
def set.empty: set(a)
The set with no elements.
set.fromList
def set.fromList: [Eq(a), Hash(a)] list(a) -> set(a)
The set of the elements of xs, each once, in the order they first appear.
set.fromArray
def set.fromArray: [Eq(a), Hash(a)] array(a) -> set(a)
The set of the elements of xs, each once, in the order they first appear. What a literal
builds a set with, set[1, 2], or [1, 2] where a set is expected.
set.fromSeq
def set.fromSeq: [Eq(a), Hash(a), c] ([c] seq(a)) -> set(a)
The set of the elements of s, pulled now, each once, in the order they first appear. It
requires the contexts the sequence’s steps do.
set.build
def set.build: [Eq(a), Hash(a), c, d] ([c] () -> [d] seq(a)) -> set(a)
The set of what block yields: set.build { yield 1 yield 1 } holds one 1. The same as
seq(block) \set.fromSeq.
set.toList
def set.toList: set(a) -> list(a)
The elements of s, in the order they were first added.
set.toSeq
def set.toSeq: set(a) -> seq(a)
The elements of s as a sequence, in the order set.toList gives them.
set.contains
def set.contains: [Eq(a), Hash(a)] set(a), a -> bool
Whether s holds x.
set.insert
def set.insert: [Eq(a), Hash(a)] set(a), a -> set(a)
s with x added at the end. A set that holds x is given back as it is.
set.remove
def set.remove: [Eq(a), Hash(a)] set(a), a -> set(a)
s without x. A set that does not hold x is given back as it is.
set.length
def set.length: set(a) -> int
The number of elements.
set.isEmpty
def set.isEmpty: set(a) -> bool
Whether s has no elements.
set.fold
def set.fold: [c] set(a), b, ([c] (b, a) -> b) -> b
step applied to acc and each element of s in turn, in the order of set.toList.
set.reduce
def set.reduce: [c] set(a), ([c] (a, a) -> a) -> #some(a) | #none
The elements of s combined with f, in order, starting from the first: set[1, 2, 3, 4, 5] \set.reduce { * } is #some(120), and an empty set, having no first element, gives #none. To
start from another value, use set.fold.
set.map
def set.map: [Eq(b), Hash(b), c] set(a), ([c] a -> b) -> set(b)
The set of f of each element of s. Elements that f makes equal are kept once, where the
first of them was.
set.filter
def set.filter: [c] set(a), ([c] a -> bool) -> set(a)
The elements of s that pass keep, in the same order.
set.filterMap
def set.filterMap: [Eq(b), Hash(b), c] set(a), ([c] a -> #some(b) | #skip) -> set(b)
The set of the values f gives as #some, leaving out the elements it gives #skip for: a
set.filter and a set.map in one walk. Values that come out equal are kept once, where the
first of them was.
set.select
def set.select: [Eq(b), Hash(b), c, d] set(a), ([c] a -> [d] seq(b)) -> set(b)
The set of the values f yields for each element in turn. Values that come out equal are kept
once, where the first of them was. A lambda with yield in it is a sequence (see Yield), as
in list.select.
set.any
def set.any: [c] set(a), ([c] a -> bool) -> bool
Whether test holds for any element (so false for an empty set). It stops at the first element
it holds for.
set.all
def set.all: [c] set(a), ([c] a -> bool) -> bool
Whether test holds for every element (so true for an empty set). It stops at the first
element it fails for.
set.isSubset
def set.isSubset: [Eq(a), Hash(a)] set(a), set(a) -> bool
Whether t holds every element of s.
set.union
def set.union: [Eq(a), Hash(a)] set(a), set(a) -> set(a)
The elements of s, then those of t that s does not hold.
set.intersection
def set.intersection: [Eq(a), Hash(a)] set(a), set(a) -> set(a)
The elements of s that t holds too, in the order of s.
set.difference
def set.difference: [Eq(a), Hash(a)] set(a), set(a) -> set(a)
The elements of s that t does not hold, in the order of s.