Atlas of Lie Groups and Representations

Documentation contents

atlas Library · Script File

hash.at

Hash tables for any type |T| that can provide hahshing and equality testing.

The functions that implement this are combined into a |HashInfo<T>| structure,
from which the generic function |make_hash| can make am empty |Hash<T>| value.
Filling the table and other functionality is provided by the |Hash<T>|
component functions. These are, in order of frequencey of use:
. |match| to possibly add an entry, retuning its sequence number in all cases
- |could_add| is similar but reports whether the element was new
- |index| gets an element from its sequence number
- |search| tests for membership and looks up, without modifying the table
- |list| produces all values currently in the hash table, by order of arrival
- |iterator| provides an |Iterator<T>| to range over entries dynamically
  (it will also find entries added after the |iterator| call, unlike |list|)
- |fill| can add multiple elements to the table
- |clear| empties the table so that it can be re-used
- |size| tells the number of entries currrently stored
- |capacity| gives the current size of the storage used
Source
atlas-scripts/hash.at (227 lines)
Definitions
47
Loads
nothing
Loaded by
W_orbit.at cross_W_orbit.at W_classes.at

Definitions in source order

HashInfo type

L23
set_type HashInfo<T> = ((T,int->int) hash_code, (T,T->bool) eq)!

Fields: hash_code, eq

Sometimes it is useful to store non-key infomation in a hash table, which does
not participate in hashing and testing for equality (and which will therefore
be dropped when trying to add an entry for which the key information is
already known in the table), but which can be retrieved using |index|, |list|
and |iterator|. This can be implemented simply by creating a |HashInfo<T>|
for a (tuple) type that contains a hashable subtype |S|. The function |lift|
prouced this from a |HashInfo<S>| and a (projection) map |T->S|
L25

lift

L34any_type S, Tlift ((S->T)f, HashInfo<T> (hash_code,eq)) = HashInfo<S>

also defined in tits.at, center.at, nilpotent_orbits.at, disconnected.at

triv_hash_info

L39triv_hash_info = HashInfo<int>
One can even do this with a subtype |S=int|, which needs no active hashing
make |int| into a "hashable" type

Hash type

L43
set_type Hash<T> =
  ( (   -> int) size
  , (   -> int) capacity
  , (   ->    ) clear
  , (   -> [T]) list
  , (int->T   ) index
  , (T  ->bool,int) acquire { sequence number, and whether it was new }
  , (T  ->Maybe<int> ) search
  )!

Fields: size, capacity, clear, list, index, acquire, search

The specification of the |Hash| interface, a type constructor.
with additional functions
(Hash<T>->([T] -> ))   fill
(Hash<T>->(T  ->bool)) could_add
(Hash<T>->(T  ->int))  match
(Hash<T>->(T  ->int))  lookup
(Hash<T>->(   ->Iterator<T>) iterator
L53
And here is the implementation, in the form of the |make_hash| constructor
L61

make_hash

L63any_type Tmake_hash (HashInfo<T> (hash_code,eq)) = Hash<T>

fill

L111any_type Tfill (Hash<T> table) = ([T] list)void

also defined in K_Nilpotent.at

could_add

L113any_type Tcould_add (Hash<T> table) = (T x) bool

match

L114any_type Tmatch (Hash<T> table) = (T x) int

iterator

L115any_type Titerator (Hash<T> table)

lookup

L120any_type Tlookup(Hash<T> table) = (T x) int

also defined in basic.at, hodge_K_type_formula.at, structure_constants.at

exhaust

L124any_type Texhaust ([(T->T)] actions, Hash<T> hash) = [T]
efficient orbit generation; client seeds |hash| with initial element(s) first
of abstraction of type |T|
L133

eval_at_mod

L136eval_at_mod(int n, int m) = (vec->int)
fast polynomial evaluation modulo power of 2, similar to polynomial |eval|

hash_code 3 overloads

L142hash_code (vec v, int mod) = int
meant to hash a [vec] to int in [0,d_mod)
L145hash_code (mat M, int mod) = int
meant to hash a [mat] to int in [0,mod)
L148hash_code (ratvec v, int mod) = int
meant to hash a [rat_vec] to int in [0,mod)

also in this file at line 157, line 161, line 168, line 178, line 183, line 188, line 209; also defined in W_classes.at

make_vec_hash

L151make_vec_hash () = Hash<vec>

make_mat_hash

L152make_mat_hash () = Hash<mat>

make_ratvec_hash

L153make_ratvec_hash () = Hash<ratvec>

hash_code 2 overloads

L157hash_code (KType p, int mod) = int
meant to hash KTypes for single group G
L161hash_code (Param p, int mod) = int
meant to hash Params for single group G

also in this file at line 142, line 145, line 148, line 168, line 178, line 183, line 188, line 209; also defined in W_classes.at

to_vecs

L166to_vecs (KTypePol P) = [vec]
meant to hash a [KTypePol]

hash_code

L168hash_code (KTypePol P, int mod) = int

also in this file at line 142, line 145, line 148, line 157, line 161, line 178, line 183, line 188, line 209; also defined in W_classes.at

make_KType_hash

L170make_KType_hash () = Hash<KType>

make_Param_hash

L172make_Param_hash () = Hash<Param>

make_KTypePol_hash

L174make_KTypePol_hash () = Hash<KTypePol>

hash_code 3 overloads

L178hash_code (RootDatum rd, int mod) = int
L183hash_code (InnerClass ic, int mod) = int
L188hash_code (RealForm G, int mod) = int

also in this file at line 142, line 145, line 148, line 157, line 161, line 168, line 209; also defined in W_classes.at

make_RootDatum_hash

L192make_RootDatum_hash () = Hash<RootDatum>

make_InnerClass_hash

L194make_InnerClass_hash () = Hash<InnerClass>

make_RealForm_hash

L196make_RealForm_hash () = Hash<RealForm>

also in this file at line 226

KGBratvec type

L200
set_type KGBratvec = (KGBElt x, ratvec lambda)

Fields: x, lambda

=

L202= (KGBratvec A, KGBratvec B) = bool

also defined in basic.at, combinatorics.at, modules.at, parabolics.at, synthetic.at, tits.at, K_highest_weights.at, nilpotent_orbits.at, cyclotomic.at, polynomial.at, W_reps_type_BC.at, hodgeParamLaurentPol.at, hodgeParamPol.at, laurentPolynomial.at, extended.at, disconnected.at, cyclotomic_Lie_algebra.at, cyclotomicMat.at, bracket.at

!=

L205!= (KGBratvec A, KGBratvec B) = bool

also defined in basic.at, combinatorics.at, synthetic.at, tits.at, cyclotomic.at, polynomial.at, cyclotomicMat.at

hash_code

L209hash_code(KGBratvec p, int mod) = int

also in this file at line 142, line 145, line 148, line 157, line 161, line 168, line 178, line 183, line 188; also defined in W_classes.at

make_xlambda_hash

L212make_xlambda_hash () = Hash<KGBratvec>

vec_hash type

L215
set_type vec_hash        = Hash<vec>

ratvec_hash type

L216
set_type ratvec_hash 	 = Hash<ratvec>

mat_hash type

L217
set_type mat_hash 	 = Hash<mat>

RootDatum_hash type

L218
set_type RootDatum_hash  = Hash<RootDatum>

InnerClass_hash type

L219
set_type InnerClass_hash = Hash<InnerClass>

RealForm_hash type

L220
set_type RealForm_hash   = Hash<RealForm>

xlambda_hash type

L221
set_type xlambda_hash	 = Hash<KGBratvec>

KType_hash type

L222
set_type KType_hash	 = Hash<KType>

KTypePol_hash type

L223
set_type KTypePol_hash 	 = Hash<KTypePol>

Param_hash type

L224
set_type Param_hash 	 = Hash<Param>

make_RealForm_hash

L226make_RealForm_hash ([RealForm] list, (RealForm,int->int).) = RealForm_hash

also in this file at line 196

Generated from atlas-scripts at commit 648506c (2026-10-13).