ToDo 76
rhx 56 10-Jan-2007: This should be close to IndexedFreeLinearCombinationType of the Algebra library, but we do not require a multiplication

*: (A, %) -> %

and thus do not use Linear in the name.

Type Constructor

Usage

macro A == Integer;        -- coefficient type
macro J == MachineInteger; -- index type
TotallyOrderedType;
} == add { ... }

Description

A category of weak polynomials.

Informally a domain that realizes IndexedFreeAdditiveCombinationType can be seen as a polynomial domain A[J] that lacks multiplication and implements subtraction only if A does.

The type IndexedFreeAdditiveCombinationType is the type of structures whose elements are finite products of elements from A. It can be see as the monoid

 (173)

The semigroup structure of A lifts to X (see +). Also subtraction is lifted if it exists in A.

Parameters

A:

An additive monoid that allows a zero test.

J:

An ordered (finite or infinite) index set.

Remarks

We do not require AbelianMonoid as the type of A since we do not necessarily assume that the addition is commutative and since we want to be as minimal as possible.

A: with {
zero?: % -> Boolean;
+: (%, %) -> %;
},
J: TotallyOrderedType
): Category == with {
default {
}
}

Defines:
IndexedFreeAdditiveCombinationType, used in chunks 489 and 496.

Uses TotallyOrderedType 571.

0: % Zero element.

zero?: % -> Boolean Zero test.

bracket: (A, J) -> % Construction of a monomial element.

+: (%, %) -> % Lifted addition.

leadingMonomial: % -> Cross(A, J) Returns the monomial with biggest index.

leadingCoefficient: % -> A Returns the coefficient of the monomial with biggest index.

reductum: % -> % Removes the monomial with biggest index.

maxSupport: % -> J Returns the biggest index of the support of the element.

generator: % -> Generator Cross(A, J) Generates coefficient-index pairs starting with the biggest index.

#: % -> MachineInteger Returns the number of elements in the support.

map: (A -> A) -> % -> % Applies a function to all coefficients.

map: (Cross(A,J) -> Cross(A,J)) -> % -> % Applies a function to all monomials.

if A has with {-: (%, %) -> %; -: % -> %} then {

-: (%, %) -> % Lifted subtration.

-: % -> % Lifted negation.

}

if A has with {0: %} then {

apply: (%, J) -> A Returns the coefficient corresponding to the given index.

}

if A has PrimitiveType then PrimitiveType;

if A has TotallyOrderedType then TotallyOrderedType;

if A has OutputType and J has OutputType then OutputType;

0: %

Description

Zero element.

0: %;

zero?: % -> Boolean

Description

Zero test.

469exports: IndexedFreeAdditiveCombinationType 468+   (465)  468  470
zero?: % -> Boolean;

bracket: (A, J) -> %

Description

Construction of a monomial element.

The call [a,j] returns f so that for all i J:

 (174)
if a0 and 0 if a = 0.
470exports: IndexedFreeAdditiveCombinationType 468+   (465)  469  471
bracket: (A, J) -> %;

+: (%, %) -> %

Description

The monoid structure of A lifts to X = A(J). Let a1 : J A and a2 : J A with supp(a1) = I1 and supp(a2) = I2. Then a = a1 + a2 is defined as the function a : J A with

 (175)
471exports: IndexedFreeAdditiveCombinationType 468+   (465)  470  472
+: (%, %) -> %;

Description

Returns the monomial with biggest index.

Since each element f has finite support S, the function returns the pair (f(j),j) such that j = maxS where the maximum is taken with respect to the given compare function of the given index set J.

Remarks

The result of leadingMonomial(0) is undefined and may result in a runtime exception.

472exports: IndexedFreeAdditiveCombinationType 468+   (465)  471  473a

Description

Returns the coefficient of the monomial with biggest index.

Since each element f has finite support S, the function returns f(j) for j = maxS where the maximum is taken with respect to the given compare function of the given index set J.

Remarks

The result of leadingCoefficient(0) is undefined and may result in a runtime exception.

473aexports: IndexedFreeAdditiveCombinationType 468+   (465)  472  474
assert(not zero? x);
a;
}

reductum: % -> %

Description

Removes the monomial with biggest index.

Since each element f has finite support S, the function returns the element g with supp(g) = S and f(j) = g(j) on the common support of f and g.

The maximum is taken with respect to the given compare function of the given index set J.

Remarks

The result of reductum(0) is undefined and may result in a runtime exception.

474exports: IndexedFreeAdditiveCombinationType 468+   (465)  473a  475a
reductum: % -> %;

maxSupport: % -> J

Description

Returns the biggest index of the support of the element.

Since each element f has finite support S, the function returns j = maxS where the maximum is taken with respect to the given compare function of the given index set J.

Remarks

The result of maxSupport(0) is undefined and may result in a runtime exception.

475aexports: IndexedFreeAdditiveCombinationType 468+   (465)  474  476
maxSupport: % -> J;
475bdefaults: IndexedFreeAdditiveCombinationType 473b+   (465)  473b  479c
maxSupport(x: %): J == {
assert(not zero? x);
j;
}

generator: % -> Generator Cross(A, J)

Description

Generates coefficient-index pairs starting with the biggest index.

Remarks

The call generator(0) returns a generator that generates no element.

476exports: IndexedFreeAdditiveCombinationType 468+   (465)  475a  477
generator: % -> Generator Cross(A, J);

Uses Generator 617.

#: % -> MachineInteger

Description

Returns the number of elements in the support.

Remarks

The call #(0) returns 0.

477exports: IndexedFreeAdditiveCombinationType 468+   (465)  476  478
#: % -> MachineInteger;

Uses MachineInteger 67.

map: (A -> A) -> % -> %

Description

Applies a function to all coefficients.

478exports: IndexedFreeAdditiveCombinationType 468+   (465)  477  479a
map: (A -> A) -> % -> %;

map: (Cross(A,J) -> Cross(A,J)) -> % -> %

Description

Applies a function to all monomials.

Remarks

This function assumes that the given function that is applied to coefficient and index does not destroy the order, i. e., we assume that in map(f,x) the function f : A × J A × J is monotone in its second argurment; if (a1,j1) = f(a1,j1) and (a2,j2) = f(a2,j2) and j1 < j2 then j1< j2.

479aexports: IndexedFreeAdditiveCombinationType 468+   (465)  478  479b
map: (Cross(A,J) -> Cross(A,J)) -> % -> %;

Some functionality can only be implemented (and we do it as category defaults) if the coefficient domain A provides enought functionality.

479bexports: IndexedFreeAdditiveCombinationType 468+   (465)  479a  481c
if A has with {-: (%, %) -> %; -: % -> %} then {
}
479cdefaults: IndexedFreeAdditiveCombinationType 473b+   (465)  475b  481d
if A has with {-: (%, %) -> %; -: % -> %} then {
}

-: (%, %) -> %

Description

Lifted subtration.

The monoid structure of A lifts to X = A(J). Let a1 : J A and a2 : J A with supp(a1) = I1 and supp(a2) = I2. Then a = a1 a2 is defined as the function a : J A with

 (176)
480aexports: IndexedFreeAdditiveCombinationType: minus 480a  (479b)  481a
-: (%, %) -> %;
480bdefaults: IndexedFreeAdditiveCombinationType: minus 480b  (479c)  481b
(x: %) - (y: %): % == x + (-y);

-: % -> %

Description

Lifted negation.

481aexports: IndexedFreeAdditiveCombinationType: minus 480a+   (479b)  480a
-: % -> %;
481bdefaults: IndexedFreeAdditiveCombinationType: minus 480b+   (479c)  480b
-(x: %): % == map(-\$A)(x);
481cexports: IndexedFreeAdditiveCombinationType 468+   (465)  479b  483a
if A has with {0: %} then {
}
481ddefaults: IndexedFreeAdditiveCombinationType 473b+   (465)  479c  483b
if A has with {0: %} then {
}

apply: (%, J) -> A

Description

Returns the coefficient corresponding to the given index.

An element f is a function f : J A. The call apply(f,j) or f.j returns f(j).

Remarks

If jsuppf then f(j) = 0.

apply: (%, J) -> A;
apply(x: %, j: J): A == {
import from I;
while not zero? x repeat {
x := reductum x;
c := compare(i, j);
zero? c => return a;
c < 0   => return 0;
}
0;
}

Uses I 47.
ToDo 77
rhx 57 21-Jan-2007: This condition is questionable since we require a function zero? from A. However, the availibility of a zero test does not imply that the domain provides a general equality test. Therefore we implement equality testing only if A provides it.
483aexports: IndexedFreeAdditiveCombinationType 468+   (465)  481c  484a
if A has PrimitiveType then PrimitiveType;
483bdefaults: IndexedFreeAdditiveCombinationType 473b+   (465)  481d  484b
if A has PrimitiveType then {
}
(x: %) = (y: %): Boolean == {
import from A, J, I;
zero? x => zero? y;
zero? y => false;
xj ~= yj => false;
xa ~= ya => false;
reductum x = reductum y;
}

Uses I 47.
484aexports: IndexedFreeAdditiveCombinationType 468+   (465)  483a  486b
if A has TotallyOrderedType then TotallyOrderedType;

Uses TotallyOrderedType 571.
484bdefaults: IndexedFreeAdditiveCombinationType 473b+   (465)  483b  486c
if A has TotallyOrderedType then {
}

Uses TotallyOrderedType 571.

Let x and y be elements of the current domain then x < y if and only if one of the following conditions holds.

1. x = 0 y0
2. x0 y0 jx < jy
3. x0 y0 jx = jy x(jx) < y(jy)
4. x0 y0 jx = jy x(jx) = y(jy) x< y

where jx = maxsupp(x) and x= reductum(x), and jy and yare defined analogously.

Note that this order has a minimal element, namely 0. This order is not additive in general. Take A = J = and the functions a,b : where a(0) = 1, b(0) = 1 and all other function value are zero. Then we clearly have 0 < a and 0 < b. However, 0 + a < a + b = 0 is false.

Nevertheless, the order is modelled after the lexicographic order starting the comparison with the biggest index. It is sometimes also known as the reverse lexicographical order (which should not be confused with the inverse lexicographical order which is simply < 1 for the lexicographical order <, i. e., if a < b then b < 1a).

485defaults: IndexedFreeAdditiveCombinationType Order 485  (484b)  486a
(x: %) < (y: %): Boolean == {import from I; compare(x, y) < 0}

Uses I 47.

Similarly, compare(x,y) is 0 if x = y, < 0 if x < y and > 0 if x > y.

compare(x: %, y: %): MachineInteger == {
import from A, J, I;
zero? x => if zero? y then 0 else -1;
zero? y => 1;
not zero?(c := compare(xj, yj)) => c;
not zero?(c := compare(xa, ya)) => c;
compare(reductum x, reductum y);
}

Uses I 47 and MachineInteger 67.
if A has OutputType and J has OutputType then OutputType;

Uses OutputType 570.
if A has OutputType and J has OutputType then {
}

Uses OutputType 570.