Maps and sets
How map(k, v) and set(a) are built
What maps and sets do is described on maps and sets and in Collections. This page says how the compiler builds them. Their known gaps, what is left and the open questions are on Maps and sets in Work in progress.
How it works
- The types.
map(k, v)andset(a)are types the compiler knows, as it knowslist(a);Map(k, v)andSet(a)are the same types, by their capitalised names (Nanyx.Compiler/Maps.fs,Sets.fsandBuiltinTypeNames.fs). - Literals.
[k => v, ...]with no other expected type is a map: the parser makes it a call to the prelude’s__mapwith the list of the entries as tuples,__map([(k, v), ...])(MapSyntaxinNanyx.Parser/Ast.fs), so the type checker and the backend see an ordinary call. A set literal, or a map literal of an expected type, goes throughfromArray(Syntax). - Keys need
EqandHash, as Hash(a) describes. The hash is not used yet: lookups compare with==. - Calling a map is a lookup. The type checker types
m(k)as the call tomap.get(inferLookupinInfer.fs, which reads a call of an array asarray.atthe same way) and records it inReadAs, andExpressionRewrites.writeAsReadwrites it as that call for the backend. A call of a field that holds a function,statement.setInt(position, value), is read the same way, as a block that keeps the field’s value in a local and calls it (FieldCalls, #1513). - Representation. A map holds the list of its entries, each key once, in the order the keys were first added, and
a set the list of its elements. The prelude builds and reads them through four intrinsics,
__nanyx_map_of_entries,__nanyx_map_entries,__nanyx_set_of_elementsand__nanyx_set_elements, which the backend compiles to nothing: amap(k, v)is held as alist((k, v)), and aset(a)as alist(a). ==compares contents, in any order (#618). The compiler’s own comparison, which works by structure, would compare the lists underneath in order, so a map or a set, and any structure that holds one, is always compared by an==the compiler derives from its parts (MapShapeandSetShapeinStructuralInstances.fs, as for a list whose elements have their own==). The derived==calls the prelude’s__mapEqualsByor__setEqualsBywith a function that compares two values or elements. It takes time in proportion to the product of the sizes, as a lookup does.- A call that needs
Eqof a type with variables in it, such aslist.distincton alist(set(a))inside a function that requires[Eq(a)], is passed the derived==as a closure over theEq(a)the function was given (#630).