combine -- combine hash tables

Synopsis

Usage:

z = combine(x,y,f,g,h) or z=combine(x,y,f,t,g,h)
Inputs:
- x, a hash table
- y, a hash table of the same class as x
- f, a function of two variables to be used for combining a key of x with a key of y to make a new key for z.
- t, a function combining two keys and returning a value, twisting the value returned by g based on which keys were used. This argument may be omitted, in which case the t(p,q) term in the output below is omitted.
- g, a function of two variables to be used for combining a value of x with a value of y to make a new value for z.
- h, a function of two variables to be used for combining two values returned by g when the corresponding keys returned by f turn out to be equal. Its first argument will be the value accumulated so far, and its second argument will be a value just provided by g.
Outputs:
- z, a new hash table, of the same class as x and y, containing the pair f(p,q) => g(t(p,q),g(b,c)) whenever x contains the pair p => b and y contains the pair q => c, except that h is used to combine values when two keys coincide. If f or g evaluates continue, then nothing is contributed to the resulting hash table. If h evaluates continue, then, at that point, the entry stored under the key f(p,q) in the hash table under construction is removed.

Description

The function f is applied to every pair (p,q) where p is a key of x and q is a key of y. The number of times f is evaluated is thus the product of the number of keys in x and the number of keys in y.

The function h should be an associative function, for otherwise the result may depend on internal details about the implementation of hash tables that affect the order in which entries are encountered. If f, t (if present), g, and h are commutative functions as well, then the result z is a commutative function of x and y.

The result is mutable if and only if x or y is.

This function can be used for multiplying polynomials, where it can be used in code something like this:

     combine(x, y, monomialTimes, coeffTimes, coeffPlus)

We illustrate that with a simple-minded implementation of the free ring on the English alphabet, representing words as string and polynomials as hash tables that associate coefficients to words.

i1 : Poly = new Type of HashTable

o1 = Poly

o1 : Type

i2 : p = new Poly from { "" => 1, "x" => 2, "y" => 3, "cat" => 5 }

o2 = Poly{"" => 1   }
          "cat" => 5
          "x" => 2
          "y" => 3

o2 : Poly

i3 : Poly * Poly := (p,q) -> combine(p,q,concatenate,times,plus);

i4 : p*p

o4 = Poly{"" => 1       }
          "cat" => 10
          "catcat" => 25
          "catx" => 10
          "caty" => 15
          "x" => 4
          "xcat" => 10
          "xx" => 4
          "xy" => 6
          "y" => 6
          "ycat" => 15
          "yx" => 6
          "yy" => 9

o4 : Poly

One may also use this function for multiplying divided powers in a similar manner:

     combine(x, y, monomialTimes, divPowCoeff, coeffTimes, coeffPlus)

For example:

i5 : DivPowPoly = new Type of HashTable

o5 = DivPowPoly

o5 : Type

i6 : divPowCoeff = (i,j) -> binomial(i+j,i)

o6 = divPowCoeff

o6 : FunctionClosure

i7 : p = new DivPowPoly from { 0 => 1, 1 => 1 }

o7 = DivPowPoly{0 => 1}
                1 => 1

o7 : DivPowPoly

i8 : DivPowPoly * DivPowPoly := (p,q) -> combine(p,q,plus,divPowCoeff,times,plus);

i9 : p*p

o9 = DivPowPoly{0 => 1}
                1 => 2
                2 => 2

o9 : DivPowPoly

For the programmer

The object combine is a compiled function.

combine -- combine hash tables

Synopsis

Description

See also

For the programmer