Turn R2 into D2 (Generalize R2 to any numeric type)

[byorgey]

Imported from diagrams/diagrams-core#20, since it actually affects the diagrams-lib repo. See the discussion there for more information. The basic idea is to create a new type

newtype D2 a = D2 { unD2 :: (a,a) }

and to define

type R2 = D2 Double
type Q2 = D2 Rational -- while we're at it

and to then generalize type signatures mentioning R2 to be generic over any D2 a where a is a type with the required properties. For example, we would generalize

(===) :: (Juxtaposable a, V a ~ R2, Semigroup a) => a -> a -> a

to

(===) :: (Juxtaposable a, V a ~ D2 b, Floating b, Semigroup a) => a -> a -> a

or something similar.

This process should be mostly mechanical, except that some care will be needed in coming up with the right (minimal) constraints. For example, I don't actually know whether Floating is required for (===), or if something like Fractional (or something else entirely) will do.

This will pave the way for doing various fun things with 2D diagrams over generalized numeric types, such as

• doing optimal layout with automatic differentiation
• positioning diagrams via constraints instead of absolutely, and solving the constraints later
• reifying diagrams in order to compile them to javascript or some other language

Of course, the same should also be done for 3D diagrams but that can wait a bit.

[cartazio]

if no one's attacking this, i'll do it

[jbracker]

I just did first parts of the reification of R2 to D2 in my fork.

I am at the point where I have to (or should) touch P2 and T2 and generalize them to (P2 a) and (T2 a) so they can work together with (D2 a).

So there is the following design decision to be made: Shall I introduce something like (PD2 a) and (TD2 a) and set P2 = PD2 Double and T2 = TD2 Double to keep old code using those types working or shall I just break things there?
I think the main point is picking a good name for the more general type, because writing Transformation or Point everywhere, will be annoying... Personally I would prefer to write (P2 a) and (T2 a) but that will for sure break old code.

[byorgey]

In an ideal world I think I agree that writing P2 a and T2 a, etc. would be the Right Thing. But this will break a lot of code, especially P2 and R2 which get used a lot. On the other hand the fix would be rather easy...

Generally speaking we have generally prioritized doing things the right way over backwards compatibility. So I think I would be in favor of doing something like

1. Generalize R2, P2, and T2 to take a parameter (thus breaking old code).
2. Introduce synonyms R2D, P2D, and T2D for R2 Double, etc. Thus broken code can be fixed just by adding D to the end of some types.

Anyone else have thoughts on this?

[ekmett]

+1 on generalizing so we can have nice things like automatic differentiation. ;) That said, I don't exactly have a huge installed diagrams code-base, so this is a painless call for me. =)

[byorgey]

Oh, sure, we're definitely going to generalize. At this point we're just bikeshedding about names. ;-)

[jbracker]

Talking about bikeshedding about names:

You also suggested to generalize R2 to D2 a and leaving type R2 = D2 Double and type Q2 = D2 Rational. So general question would be:

• Go for the name scheme you mentioned in your response - or -
• Keep that and use the naming scheme for all the rest.

If we break code anyway, I am for the general naming scheme, because it would be easier to memorize. Although we should maybe use D2 a or V2 a instead of R2 a, because R2 a would imply reals/doubles for me.

[mgsloan]

Hmm, I see jbracker's email, but not the comment above. Anyway, there were issues with generalizing unitX / unitY, related to being able to enumerate the axis of a vectorspace.

I'm not currently on a computer with ghci, but it seems like the following might be a reasonable definition:

unitX :: (Decomposition v ~ (a :& a), Num a) => v
unitX = 1 & 0

This is good because when generalizing stuff inside "Diagrams.TwoD", it really ought to be for two dimensional stuff.

Regarding naming, I'm in support of leaving R2, P2, and T2 alone, because they're contractions for frequently encountered types. These aren't so bad: Point (D2 Float), Transformation (D2 Float). I think it's safe to assume that if the user wants to frequently use something other than Double, they can define their own type synonyms.

[mgsloan]

It might be a good general strategy for this conversion to just delete the types, and see what the most polymorphic type for the current definition is. I suspect something like the above would be inferred.

One thing to consider for the type of unitX / unitY is if they should be constrained to be vectors. It might make sense to add the superfluous constraint VectorSpace v, to prevent unitX / unitY from creating points (as it's possibly a user error).

[jbracker]

I deleted the post, because minutes later I realised that there is a pretty simple solution:

unitX :: (Num a) => D2 a
unitX = 1 & 0

[byorgey]

Oh, you're right, R was for "Real". So generalizing to R2 a doesn't make sense. It should probably be V2.

[byorgey]

Also, @jbracker , go ahead and open a pull request from your repo -- I won't merge it until you are done, but it's a nice way to let others see and give feedback on your work in progress. As you push more commits they will automatically be incorporated into the pull request.

[jbracker]

Currently trying to generalize the code in Diagrams/TwoD/Transform.hs (see my fork). But I am kind of stuck. I get a bunch of errors that tell me that it can not deduce a ~ Double. I am not sure where the types are nailed down to Double, but I have two suspects:

Either the problem occures because the different Angle (CircleFrac, Rad, Deg) instances are all refined over Double. To solve that I tried to generalize them which lead to:

newtype CircleFrac a = CircleFrac { getCircleFrac :: a }

But with that the Angle class would get a bit wierd and more complicated:

class (Num a) => Angle m a where
  toCircleFrac   :: m a -> CircleFrac a
  fromCircleFrac :: CircleFrac a -> m a

instance (Num a) => Angle CircleFrac a where
  toCircleFrac   = id
  fromCircleFrac = id

instance (Floating a) => Angle Rad a where
  toCircleFrac   = CircleFrac . (/tau) . getRad
  fromCircleFrac = Rad . (*tau) . getCircleFrac

instance (Fractional a) => Angle Deg a where
  toCircleFrac   = CircleFrac . (/360) . getDeg
  fromCircleFrac = Deg . (*360) . getCircleFrac

And the definition of fullCircle and convertAngle do not work properly anymore:

fullCircle :: (Angle m a) => a
fullCircle = fromCircleFrac 1 -- ERROR: Could not deduce (a ~ m2 a1)

convertAngle :: (Angle m1 a, Angle m2 b) => a -> b
convertAngle = fromCircleFrac . toCircleFrac -- ERROR: Could not deduce (b ~ m0 a0)
-- ERROR: Could not deduce (a ~ m1 a0)

My other suspect is the ScaleInv code at the bottom of Transform.hs. It is still R2 based. When I tried to generalize that I ran into problems with the Transformable (ScaleInv t) instance. I could not manage to make everything fit together anymore...

[jbracker]

Ok, my mistake: fullCircle and convertAngle can be defined like this:

fullCircle :: Angle m a => m a
fullCircle = fromCircleFrac 1

convertAngle :: (Angle ma a, Angle mb a) => ma a -> mb a
convertAngle = fromCircleFrac . toCircleFrac

Still can't think of another way to represent angles pleasantly.

With this definition I can rewrite the signatures like this:

rotateAbout :: ( Floating a, HasBasis a, HasTrie (Basis a), a ~ Scalar a, Transformable t, V t ~ D2 a, Angle m a) => P2 a -> m a -> t -> t

This requires to use the coordinate type as type to represent a angle. I am not sure if that is an issue (because a ~ Scalar a and Num a anyway) or not yet, but it works. The only way to work around that would be wierd number conversion using the functions from RealFloat (decodeFloat, encodeFloat), but that did not seem more desirable then this approach to me.

[byorgey]

Sorry I haven't had a chance to look at this in a while. I hope to have a bit more time now.

Yikes, this Angle thing seems unfortunate. Can you help me understand what exactly the issue was that led you to generalize the Angle class in this way?

Sorry this is turning out to be quite a bit more fiddly than I thought.

[jbracker]

A good example for why I had to generalize it is the Diagrams.TwoD.Transform.rotation function:

In its original form it looked like this:

rotation :: Angle a => a -> T2
rotation ang = fromLinear r (linv r)
  where
    r = rot theta <-> rot (-theta)
    Rad theta = convertAngle ang
    rot th (coords -> x :& y) = (cos th * x - sin th * y) & (sin th * x + cos th * y)

Now it looks like this:

rotation :: ( AdditiveGroup a
            , Floating a
            , HasBasis a
            , HasTrie (Basis a)
            , a ~ Scalar a
            , Angle m a
            ) => m a -> T2 a
rotation ang = fromLinear r (linv r)
  where
    r = rot theta <-> rot (-theta)
    Rad theta = convertAngle ang
    rot th (coords -> x :& y) = (cos th * x - sin th * y) & (sin th * x + cos th * y)

In the initial form the coords transformed used Double coordinates and the angle are also represented as Double values. But when generalizing the vector components to some general a you get a problem when doing arithmetic between that a and the Double from the angle. I could do some weird RealFloat conversion with decodeFloat and encodeFloat, but that seemed messy to me. So I tried to generalize the angles. Their data structure was straightforward, I just replaced the Double with a new type variable to plug in the needed type:

newtype CircleFrac a = CircleFrac { getCircleFrac :: a }
  deriving (Read, Show, Eq, Ord, Enum, Floating, Fractional, Num, Real, RealFloat, RealFrac)

But the type class was a tricky. Originally it looked like this:

class Num a => Angle a where
  toCircleFrac :: a -> CircleFrac
  fromCircleFrac :: CircleFrac -> a

But as the angle representations are now parametrized with a type you get a problem. My first approach was:

class Num a => Angle a where
  toCircleFrac :: a -> CircleFrac a
  fromCircleFrac :: CircleFrac a -> a

Which obviously will not type check either way (instance Angle (Deg a) or Angle Double), because in one case we have a :: * -> * and in the other we have a :: *. This lead me to the current form:

class (Num a, Num (m a)) => Angle m a where
  toCircleFrac :: m a -> CircleFrac a
  fromCircleFrac :: CircleFrac a -> m a

[jbracker]

What is currently in my fork should have all types generalized and compile. I will tag it.

I am currently working on generalizing the if-then-else using the Data.Boolean package to enable the deep embedding. There is an issue arising from this.

For Data.Boolean to work you have to associate a boolean type to each type you want to use in an if-then-else.
But that means, if I have a simple custom data type like data D = A | B then I have to give a BooleanOf D in order to use the IfB class. The problem is depending on the backend we use the BooleanOf D has to change. In
most backends it will simply be Bool, but in Sunroof it needs to be JSBool to create a proper deep embedding.

I have thought about a couple of solutions for this problem:

• The first solution is creating extra modules so the definitions only comes into scope when needed. But one could not just import one of these models by default, because then you could not change it afterwards. So the user would always be obliged to add an extra import into his code depending what backend he is using (this could also be done while importing the backend). The real problem about this approach is that it would introduce cyclic dependencies, as the module relies on the data type and the code around the data type relies on the BooleanOf definition and I know GHC does not like that at all.
• Second solution: This problem only occurs if the data type does not have a type parameter, because if we have D2 a we can just give proper definitions for the different parameters: BooleanOf (D2 Double) = Bool and BooleanOf (D2 JSNumber) = JSBool. So adding a phantom type to 'simple' data types might also be a solution to the problem.
  Although I think that this approach is very unfriendly and unintuitive for the user when looking at the type level it would be convenient to use at the value level and seems to be the most viable approach.
• The third solution would involve not using type families to model this relationship. But this leads to ambiguous code.

So I will generalize further using the second approach.

Also as there is no protest I will rename D2 a into V2 a at some point and leave P2 a and T2 a with their new type parameters.

[byorgey]

Hi @jbracker , it was great to meet you and hack on this a bit yesterday! Thanks for your hard work on this, it seems there is still a ways to go but I am confident we can make it all work.

The first solution sounds the best to me, and I do not understand why it introduces cyclic dependencies. I would have thought that

• The BooleanOf type family itself is declared somewhere central, presumably diagrams-core; so it can be referenced anywhere.
• One of the main features of type families is that they are open, that is, new definitional clauses can be added anywhere. So diagrams-cairo could define type instance BooleanOf Foo = Bool and diagrams-sunroof could define type instance BooleanOf Foo = JSBool; you get whichever definitions are in the backend that you import. However, any types which reference BooleanOf will depend only on its declaration, not on its definition, so no cyclic dependencies are needed.

Is there something I'm misunderstanding?

[jbracker]

Hi @byorgey, I and enjoyed that micro-hack too.

• BooleanOf is defined somewhere central.
• You are absolutely right. The first solution should work perfectly. I will try getting it to work like that. But then a default back end will not work anymore since that would lead to conflicts if another back end is chosen.

[byorgey]

Hmm, I don't understand your comment about "a default back end will not work anymore"... can you explain further what you mean? There is no "default backend"; to use any backend the user must import it anyway. And if they only want to define diagrams and not render them, then it seems it should not matter whether BooleanOf is defined?

[jbracker]

In all the examples I tried and looked at it always seemed as if there was one. Never mind. You are right, when just defining them, it should not make a difference.

For future reference and just in case someone here is not reading the mailing list, there is another problem going on:
https://groups.google.com/d/msg/diagrams-discuss/AjYoWxkTUcU/u3aOsU1oxuEJ

[jbracker]

Some further Problems have occured:

• The scale function from diagrams-core has the constraint Eq. That stops the full generalization of Diagrams.TwoD.Polygons.polyPolarVs and dependent functions, because they all still need Eq a in their constraints.
• Diagrams.Trail.Trail needs to use generalized booleans, because of the generalization of Diagrams.TwoD.Arc.arcT. This basically is related to the issue of generalizing returned values that can not directly be represented by the deep embedding (see link in previous post). In this case that issue can be solved by deeply embedding the boolean into the Trail type. But yet I am not sure how much impact that will have in other places.

[mgsloan]

I've always thought that the partialness of scale was a bit odd. The Eq constraint is just used to check against "0".

One option that I think has been discussed is to add Monoid as a superclass to Transformable. The problem with this is that not all transformable things necessarily have a mappend..

I think the most sensible solution is to add "tzero", or something like that, it to the Transformable typeclass

[byorgey]

I don't ever recall discussing adding Monoid as a superclass of Transformable (or at least, I have the same obvious issue with it that you do). In general I dislike (ab)using Monoid to just mean HasMempty.

Off the top of my head, though, I really like your idea of adding tzero to Transformable. I'll make a ticket for it and give it some more thought. I want to figure out a solution to the scale-by-zero thing too (independently of issues with deep embeddings). (As an additional note, however, this wouldn't get rid of the Eq constraint which is what Jan is complaining about. I don't see any way around that; scale by 0 has to act specially.)

[noinia]

Any news on this? I was hoping to use diagrams-lib a starting point for a geometry library. But having generalized number types is an absolute requirement.

I briefly looked at the generalized-R2 branch and generalized-types tags. But it seems a lot of code has changed in the mean time (which also makes me think that it may be a good idea to do this type of change gradually instead of a wholeshot change).

[byorgey]

Unfortunately it doesn't look like this is going to happen anytime soon. @jbracker did some fantastic work, but

1. The changes ended up being quite invasive, far more than I had imagined. Many type signatures throughout the library became much more complicated (to the point that even I was no longer sure what the right types were supposed to be, or why certain constraints were necessary).
2. Even if we were to decide the extra complication was worth it, there was still a large amount of work that remained to be done updating the backends, user manual, diagrams-contrib package, etc. and I simply ran out of steam. The original motivation for the generalization (doing a deep embedding in order to be able to compile to e.g. javascript) independently didn't look like it was going to work out, and beyond that no one had any concrete use cases, just some vague ideas that it might make some cool things possible (like automatic differentiation) but no real evidence to show that it would really work. (I asked on the mailing list for people to play around with the generalized-R2 branch to see what was possible, but no one took me up on it.)

You're right that at this point development has diverged to the point that we would basically have to do a lot of the work over again (which I'd still be open to, if someone figured out a way to do the generalization in a clever way that didn't introduce a ton of complication). You say we ought to do this gradually instead of wholeshot, but I really don't see how that would be possible. The R2 type occurs so pervasively that if you change its API, you have to change almost everything.

[noinia]

Wr.t. to being invasive and the wholeshot comment: If I look at the generalized-R2 branch than it seems that this actually tries to do three things:

1. Generalize the underlying math to arbitrary number types,
2. Generalize all the code that actually produce parts of a diagram to use arbitrary number types, and
3. Wire in MemoTrie in various places.

I'm not sure what the reasons for 3) are, as I was not familiar with memotries until reading Ralf's paper yesterday. However, it seems to me that this is something that can be considered separately. As for the other two: I think it would already be very usefull to have part 1) in place, since: (a) this would allow other people/packages to already use the impressive amount of transformations on geometric objects, (b) it can be implemented without affecting too much of the code, (c) that part of the code does not become that much more complicated, and (d) it is a prequisite for actually getting to 2), (also in the sense that for any new code people will build on top of what is already there, so delaying making things more general will only increase the amount of work that needs to be done when actually doing it).

When part 1) is in place the parts of the library that produce drawings can be upgraded to use generic types incrementally.

As I am not a coach or boss telling other people how to do their job, I did some work myself as well ;). I redid a part of the work required for 1), which can be found in [1]. All commits up to yesterday (Sept 5, 2013) step by step generalize the types and transformations on types. I'm not entirely happy about the stuff with Angles and Turns, since I think I made that too complicated.

The commits of today (Sept 6, 2013) are part of 2): generalizing the code that actually produces parts of the diagrams. I think this is also were most of the complexity was/is when generalizing things. So far I looked only at the Paths module, but I think that the result is also not too horrible. I used ConstraintKinds to create type aliasses for some collection of constraints that often occur simultaneously (Essensially the diagrams-core library already uses something similar in e.g. the OrderedField class). Furthermore, sometimes the GHC is too clever in finding out the required typeclasses for a certain function. For example, looking at the function what we actually use is VectorSpace (V2 b) , but GHC figures out that we then still need Ord b, AdditiveGroup b, and Num b so that we get `VectorSpace (V2 b)' and thus suggests those. With these two things in mind, I think the resulting type signatures still look quite reasonable, and I suspect that this also holds for the other modules .

[1] https://github.com/noinia/diagrams-lib/tree/gentypes

[bergey]

I'd like to revisit this at some point. Is there a list of features that might benefit from the more general types? I'm aware of:

• Automatic Differentiation (though I'm not sure exactly what we'd use it for)
• Constraint Solving (which would be really cool if it works)
• Exact Arithmetic / Dynamic Precision

I also have a (possibly controversial) idea for handling Angles, by way of lenses.

[byorgey]

I don't know of any others, but that's a pretty good list. As for what we would use AD for, think along the lines of e.g. auto-fitting shapes together (by minimizing envelope distance or something like that).

I haven't yet taken a careful look at @noinia 's changes (linked above).

[cchalmers]

This happened with the linear port.