User-Defined Datastructures

User–defined Datastructures

We can implement our own new datastructures by introducing expressions with "new heads", i.e. head symbols that do not have a pre–defined meaning in Mathematica. Using these head symbols, the new objects can be fully intergrated into to standard pattern matching mechanism in Mathematica.

Clear[EL];
EL[List[l__]] := EL[l];
EL[elx__]*EL[ely__] := EL[{elx} + {ely}];
Power[EL[l__], -1] := EL[-List[l]];

Attributes[Times]

One possibility would be to "unprotect" the symbol Times and then to add the new definitions. This has, however, several disadvantages (possible influence of the new definitions to built–in behavior of Mathematica, efficiency of built–in operations).

Clear[EL];
Unprotect[Times, Power];
EL[List[l__]] := EL[l];
EL[elx__]*EL[ely__] := EL[{elx} + {ely}];
Power[EL[l__], -1] := 
        EL[-List[l]];
Protect[Times, Power];

It is a much better solution to associate the new definitions with "EL" (the head of the operands) rather than to associate them with "Times" and "Power" (the names of the operations).

Unprotect[Times, Power];
Clear[Times, Power];
Protect[Times, Power];

Clear[EL];
EL[List[l__]] := EL[l];
EL /: EL[elx__]*EL[ely__] := EL[{elx} + {ely}];
EL /: Power[EL[l__], -1] := EL[-List[l]];

?EL

?? Times

e1 = EL[{1, 0, 2}]

Head[e1]

e2 = EL[{0, 0, 3}]

e1 e2

(1/e1)

(e1/e2)

FullForm[Unevaluated[(e1/e2)]]

Downvalues, Upvalues

In the example, we saw an important principle of Mathematica's evaluation mechanism, namely the association of definitions with a symbol. By default, a definition such as

Clear[f];
f[el_EL] := (1/el)

will always be associated with the head of the left–hand side. We call the defintion a "downvalue" of f.

?f

When evaluating f[e1] Mathematica searches for a downvalue of f, whose left–hand side matches, and, in case such a downvalue is found, the corresponding right–hand side is evaluated.

f[e1]

As we saw in the example, we can associate a definition alternatively with one of the symbols that occur as head of one of the arguments in the left–hand side. We then call it an "upvalue" for this symbol. Using ^:= or ^=, we can define upvalues associated to all head symbols occuring in the left–hand side. The two variants differ again in the evaluation of the right–hand side, just like := and =.

f[el_EL] ^:= el el

defines an upvalue for EL.

?f

?EL

f[e1]

Note, that, when evaluating f[e1] Mathematica searches for an upvalue matching e1 before it searches among the downvalues of f (-> efficiency!!!).

Clear[f]
f[el_MyType1, r_MyType2] ^:= el r

?MyType1

?MyType2

As already mentioned above, a defintion can be associated to any symbol appearing as head symbol in the left–hand side.

Clear[MyType1, MyType2]
MyType2 /: f[el_MyType1, r_MyType2] := el r

?MyType1

?MyType2

Exercise: Periodic Decimal Numbers

Implement a new datastructure representing rational numbers as finite or periodically infinite decimal numbers and implement some reasonable arithmetic operations available for these objects. Arithmetic operations should comprise at least +, - (both unary and binary), *, /, and (□^(-1)).

Solution: see separate notebook.