Ralf Hemmecke wrote:
>
> > XHashTable?
>
> Ah, before I forget. XHashTable in my opinion is not going to replace
> HashTable, but rather Table. (Not at the moment, of course, but that
> would be my plan.)
>
> Currently, XHashTable would probably already be useful as a replacement
> for AssociationList, i.e. something like that.
>
> Table(Key : SetCategory, Entry : Type):Exports == Implementation where
> Exports ==> Join(TableAggregate(Key, Entry), finiteAggregate)
>
> Implementation ==> InnerTable(Key, Entry,
> if hashable(Key)$Lisp then HashTable(Key, Entry, "UEQUAL")
> else XHashTable(Key, Entry))
>
> What do you think?
We need to implement hash functions first -- what we have now
covers bunch of basic domains and most aggregates. But the
remaining cases are more tricky. For example Set is represented
by a list, but order does not matter. So we need commutative
hash function. Assuming that 'h' is build from two argument
function f as for example: h(a, b) = f(a, b),
h(a, b, c) = f(f(a, b), c) we see that f(a, b) = f(b, a) and
f(f(a, b), c) = h(a, b, c) = h(b, c, a) = f(f(b, c), a) = f(a, f(b, c))
that is f is associative. So such f must be a abelian semigroup
operation. My feeling is that zero divisors only degrade
such function, so we probably want group operation. Moreover,
it seems that products behave no better than cyclic group,
so we probably want to use additive group of integers mod N for
some N. This is natural choice, but I wrote the paragraph above
to illustrate that there seem to be almost no alternative.
ATM I see no easy way to implement good hash function for
general fractions. To respect equality we need h(ab, ac) to
be the same as h(b, c). We could try to choose a multiplicative
homomorphizm f from R to Z mod N and define h(b, c) as
f(b)(f(c))^(-1). However, this has problem with 0: if f(c)
is 0 then the definition does not work. We could try to
use some alternative definition in such case, but the
real problem is that f(ac) may be 0 even if f(c) is nonzero.
So when f(c) = 0 we need to decide if there are d and e
such that d/e = b/c and f(d) is nonzero. Deciding this may
be possible, but clearly require a lot of knowledge about
base ring.
I have spent some time thinking about hashing expressions
(more precisely Expression(Integer)). I have a scheme
that "almost" works, but there is remaining difficulty.
ATM I do not know if this difficulty is something which
could be resolved in easy way or if it is deeper.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
