Better handling of singular transformations

[byorgey]

The impetus for this ticket is the unfortunate code

scale :: (Transformable t, Fractional (Scalar (V t)), Eq (Scalar (V t)))
      => Scalar (V t) -> t -> t
scale 0 = error "scale by zero! Halp!" -- XXX what should be done here?

(currently found here: https://github.com/diagrams/diagrams-core/blob/master/src/Diagrams/Core/Transform.hs#L286).

What should be done, indeed?

One idea (from @mgsloan, in a comment here), is to add a tzero method to Transformable, like

class Transformable t where
  ...
  tzero :: t

where tzero is defined to be the result of applying a singular transformation.

It also occurs to me we might be able to move this even closer to the source by having a special representation for singular transformations. Then tzero is implicit in the fact that Transformable instances have to decide what to do about singular transformations.

One important thing to note is that not all singular transformations are equal. (To be clear, by "singular" I mean "linear transformation whose corresponding matrix is non-invertible".) For example, scale 0 and scaleX 0 are both singular, but they are not the same and it may be useful to distinguish them. For example, scaleX 0 can usefully be applied to any Path R2 (resulting in the "projection" of the path onto the y-axis). But scale 0 and scaleX 0 have the same result on Diagrams (that is, currently, bottom; but ideally, mempty).

[mgsloan]

I think that having a special representation for singular transformations would be best. Not sure what this would look like given the current representation of Transformation.

It's a bit tricky, because you end up wanting to use linear equations as the output of the inverse of your linear transformation.. (e.g. for scaleX 0, you end up with a bunch of horizontal lines when asking for the). The domain of the inverse is weird too, since it ought to be restricted to the codomain of the forward transformation..

Writing this stuff in a way that doesn't cut corners, and is mostly statically checked, while maintaining usability, could be quite a challenge.. Interesting problem, though!

[byorgey]

Well, I guess I was thinking more along the lines that a singular transformation simply doesn't have an inverse. Whether this would be enforced statically or dynamically is still an interesting question.

[mgsloan]

The main things that would break are the Transformable instances for Query / Envelope / Trace.

Random idea:

data (:-:) u v = (u :-* (u, v)) :-: (v :-* (v, u))

-- Used to be
data (:-:) u v = (u :-* v) :-: (v :-* u)

What're those extra tupled values? They let you know what actual value the input was mapped to, in order to be within the domain. So, apply (inv $ scalingY 2 <> scalingX 0) (1 & 2) would result in ((0, 2), (0, 1)). This lets you know about the singularness, while giving decent default behavior for the "actual" result.

[byorgey]

Hmm... maybe I'm just being dense but I don't think I quite understand. What do the output tuples represent, exactly? And can you give some simpler examples, e.g. what would be the result of apply (scalingX 0) (1 & 2)?

[mgsloan]

apply (scalingX 0) (1 & 2) would be ((0, 2), (0, 2)). Since it's singular in the same way as the previous example, the "domain" vector is the same.

You're not being dense, I'm just being terse and vague. I haven't actually worked out whether these linear maps would function properly, but there are instances for tuples. Intuitively it seems like it has good chances of working.

The idea is that you should be able to query the inverse of a singular matrix if you have a default way of removing the singularity. In this case that's projecting on to the span of the matrix. So, instead it's a "pseudo-inverse", maybe even this one:

Moore Penrose pseudoinverse

[mgsloan]

Also, need to figure out what this means for the otherwise broken Transformable instances..

• Query would be a weird one, because the inclusion predicate would suddenly be true outside the subspace.. But that's the advantage of defining the results in this way - it can be determined when the matrix is singular - so query could be made to be mempty for any query outside the defined subspace. Maybe have two functions for running queries - one that projects to the nearest value in the subspace, and one that defaults to mempty?

• It seems like Envelope would also have issues. E.g. when using scaleX 0, querying the envelope at 1 & 0 would result in a vector of 0 & 0... Maybe in that case the answer should just always be 0!

• Trace ends up being pretty strange.

  When the query ray is fully inside the codomain, you can transform it properly into the domain, and run the trace.

  When the query point is outside the codomain, you'd need to do a line <-> hyperplane intersection (hyperplane of the codomain). Then you also have a point in the domain, which can be used to run the trace in the pre-transformation coordinate space. The result would be discarded, but it would pay attention to whether the result is PosInf or not. The distance from the line to the hyperplane would be used for the trace result.

  (EDIT) Hmm, this doesn't seem quite right - when constructing the local coordinate trace, there's no sensible choice for a query vector. Maybe the sensible choice is to rely on the inclusion Query? Unfortunately, this forces you to chose between having a Trace and having a custom Query..

[byorgey]

I am not following this at all. But it doesn't help that I am sick. I will come back and think about it more carefully once my head doesn't feel like it's full of cotton. =)

[Mathnerd314]

I'm wondering if Deform solves the use cases for scaling by 0. If so, we can just document that scale and friends are only defined on non-zero values.

[bergey]

Debugging the performance of deform is on my list. I agree that we should document somewhere that deform parallelX0 is the type-correct alternative to scaleX 0, &c.

[byorgey]

Drat, I always get confused and think the "close" button means "close this comment box".