To my notes on overlapping instances
>> [..]
>> In my case, it was not so bad. The results were different in a weaker
>> sense. It was like this:
>> card z5 --> Fin 5
>> "integers modulo 5 has finite cardinality 5"
>> Omitting certain import caused card z5 --> UnknownValue.
>> This was due to that the generic instance for
>> Euclidean a => Residue a
>> does not *know* how to compute certain cardinality, and so, puts it
>> UnknownValue.
Marcin 'Qrczak' Kowalczyk <[EMAIL PROTECTED]> writes on 6 Feb 2000
> I don't know your class hierarchy (I've tried to study it some time ago
> but it was too complex) [..]
This was certain library for computer algebra.
http://www.botik.ru/pub/local/Mechveliani/basAlgPropos/
contains the main part of it. I fear any simpler class-instance system
would not do the business.
But this is not so essential for the recent topic of the overlapping
instances. It is clear from the example of my previous letter that
some operation may be computed in different ways in general and in
several special situations. This leads to overlapping instances.
> but maybe the place where the cardinality is
> computed is wrong, too high, should be in a separate class, or whatever.
>
> If it does not know, it should not specify it.
It may know how to compute an operation in a more efficient way in
the special case, and in a less efficient way in the generic case.
One could imagine one more case, of the most in-efficient way - which
corresponds to UnknownValue.
But the first two cases are sufficient to require the overlapping
instances.
> If it does not know, it should not specify it.
There are often several operations in a class. Each operation may
have its own most generic situation in which it is known how to
compute. This does not look like a sufficient reason to split this
class into several classes, each with a single operation.
A good example for overlapping instances: the matrix determinant:
det mt, mt :: [[a]] n by n matrix.
I know the following good ways to compute it.
(C) CommutativeRing a => [[a]] -> a
- the most generic one.
sum [mt(1,i)*(-1)^i*det(mt'(i)) | i <- [1..n]]
Expansion by the row.
det is called recursively on the smaller matrices.
Cost in the worst case = O(n!) operations in `a'
(E) Euclidean a - subclass of CommutativeRing
Modified Gauss method, with the repeated division with remainder.
(F) Field a - subclass of EuclideanRing
Regular Gauss method. Cost = O(n^3) operations in `a'.
(FFP) a = FiniteField k => UnivariatePolynomial k (k[x])
`a' is an instance of Euclidean ring.
The best way here is the interpolation: take values in
a(1)..a(l), compute det mt(i) for mt(i) :: [[k]] via Gauss
method for Field k, restore det mt by interpolation.
Cost - is much less than for the method (E).
If det is designed as a polymorphic function, then one needs the
overlaps for the functions, or duplicate definitions, or what do you
call them.
For it is certainly not good to call the same mathematical map det
with different names. Determinant is Determinant.
If it is a class operation, then one needs overlapping instances.
Probably, these two choices lead to similar compiler technique.
> Probably the system of Haskell classes is not well suited for instances
> like "if it is ever X, it's certainly Z as well and the implementation
> of Z depends on the implementation of X, but generally X is not needed
> for Z". Standard Haskell does not allow such things and not without
> a reason.
So far, I never observed or realized such reason.
The above trouble with forgetting of import is not enough.
Forgetting to import something may cause, say, slower computation at
the run time.
(Again, my initial example with Fin 5 vs UnknownValue
had appeared only because the programmer considered both results as
correct, only the former as the better. This was the choice of the
programmer).
It only requires more caution with the import.
Or maybe, some additional tool for the module interfaces.
Though, I may mistake.
This approach "if it is ever X ..." looks like a sound one for me.
> There are ambiguities if something was defined as "if it's X then
> it's Z, if it's Y then it's Z, it's X, it's Y" - but *how* it
> should be Z - basing on X or Y?
If the user puts so, then one proclaims that it is the same for the
result which way to choose.
The result is invariant - at the intersection of the cases X,Y.
The difference may be in the computation cost.
For example, a programmer often writes i+j+k+l :: Integer
and does not care of many different ways in which this may evaluate.
Still the language does not insist on setting the parentheses here.
And it is good. The compiler still sets these parentheses, but often
the programmer may not care of how they are set.
For the case with "if it's X ...",
the way has to be chosen according to the
(1) type context,
(2) type expression specialization,
(3) priorities set.
If the user omits the priorities, the compiler sets the defaults.
What the recent implementations have, is (2).
Sadly, this does not do in full the above example with det.
And I think, I could set the priorities for the above cases
(C)...(FFP) for det.
> I feel such hierarchies unclear and would avoid them. [..]
It would be interesting to observe the examples showing this
unclearness.
Is not the example with det real-life and informative enough?
What kind of ambiguity it may cause?
Maybe, it leads to something unsound. I doubt.
>> I do not agree.
>> The feature is very natural:
>> "if type is supplied with extended attributes
>> (properties,instances) apply this clever specific method,
>> otherwise, apply the generic one
>> ".
> I do not agree. If a generic implementation does not work for this
> case, either it is not a special case of the generic case, or the
> generic implementation is wrong itself.
> A generic implementation should work correctly for all special
> cases - that's why it is placed in a generic place and called
> generic.
A strange objection. The situation is that the generic
implementation does work in the generic case and the special one
works in the special case.
> If an artificial implementation which don't always work must be
> placed in a generic place because it is tied to implementations
> of other things, it should be separated, or possibly the other
> things should not be implemented in a generic way as well.
Sounds rather dim.
For example, what and how should be separated in the example of the
instances (C)...(FFP) to compute det ?
(we may consider it like the operation of class, say, WithDet)
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
