Map

From the SETL Wiki

A map in SETL is an associative collection, roughly equivalent to dictionaries, hashes and associative arrays in other languages. Unlike most languages, a map is a special case of a set, of which all members are pairs (tuples of length 2.) The equivalent in Java would be accessing an instance of java.util.Map solely through its entrySet. Although a hash table or tree will be used internally by the interpreter whenever a set is populated with pairs, this structure is not exposed directly.

Keys can be of any type in SETL, unlike some languages which permit only integers and strings.

A single-valued map (or smap) is a special case of a map in which no key is duplicated.

Since all maps are sets, all set operations are also valid for maps.

A few additional primitives are also defined for maps:

• The domain of a map is the set of all keys in the map, i.e. the first element of each pair in the map.
• The range of a map is the set of all values in the map, i.e. the second element of each pair in the map.
• The lessf operator removes all pairs having a specified key from the map.
• Indexing. The form m(k) refers to the value (which must be unique) associated with the key k in the map m. The form m{k} refers to the set of zero or more values associated with k in m. Examples:

  m	Expression	Result
  {[1, 2], [3, 4]}	m(1)	2
  	m(2)	om
  	m{1}	{2}
  	m{2}	{}
  	domain m	{1, 3}
  	range m	{2, 4}
  {[1, 10], [1, 11], [2, 10]}	m(1)	error
  	m{1}	{10, 11}
  	m(2)	20
  	m{2}	{10}
  	domain m	{1, 2}
  	range m	{10, 11}

The forms m(k) and m{k} can also appear on the right of an assignment statement:

m (before)	Assignment	m (after)
{[1, 2], [3, 4]}	m(1) := 6;	{[1, 6], [3, 4]}
	m(2) := 7;	{[1, 6], [2, 7], [3, 4]}
	m(3) := om;	{[1, 2]}
	m{1} := {6, 7};	{[1, 6], [1, 7], [3, 4]}
	m{2} := {};	{[1, 6], [3, 4]}

Possible implementations of maps include:

• Each set represented by a tree or hash, with non-pair elements stored directly, indexed by the hash code of the whole element, and pairs stored as distinct keys and values, indexed by the hash code of the key alone. This is the default representation in CIMS SETL.
• Each set represented by a pair of trees or hashes, one containing the elements which are pairs (indexed by a hash of the key alone) and the other containing the non-pairs (indexed by a hash of the whole element.)