tomasmikula / hasheq Goto Github PK

Currently, only immutable.HashSet is tested for correctness. We need to add laws and tests for the remaining data structures before we can use them with any confidence.

The laws in immutable.SetRepr and the fiile immutable.HashMapTest can serve as a template.

• immutable.HashMap
• mutable.HashSet
• mutable.HashMap

There are currently many compilation warnings. They should be easy to eliminate. Then we should enable scalac flag -Xfatal-warnings.

HashSet[A] is a generalized Boolean algebra (i.e. a potentially topless Boolean algebra).

TotalHashMap[K, V] is a generalized Boolean algebra whenever V is a generalized Boolean algebra.

We should provide HashEq instances for common Scala types. hasheq.std.int can serve as a template.

• Unit
• Boolean
• String
• Char
• Long
• tuples
• List
• Vector

The original code contains many optimizations, often compromising elegance. Without benchmarks, it is hard to make changes with confidence that they don't negatively affect performance.

A total map is a map that is defined everywhere.

For this data structure, we only consider a special kind of total maps: the ones that are non-zero at at most a finite number of points. TotalHashMap can then be implemented using an ordinary HashMap for keys with non-zero values, and assume zero everywhere else.

EDIT: by "zero" I mean any constant value, not necessarily related to any algebraic notion of zero. So a better phrasing would be that we consider total maps that are constant except for at most a finite number of points.

Perhaps laws should be moved to a separate module, to decrease the JAR size of the core, and eliminate core's dependency on ScalaCheck.

immutable.HashSet[A] is generalized as immutable.HashSetoid[A, Eq], which is parameterized by the equivalence relation used. The rest of the data structures should follow the same pattern.

• immutable.HashMap
• mutable.HashSet
• mutable.HashMap