More problems with beside + mempty

[fryguybob]

(Imported from http://code.google.com/p/diagrams/issues/detail?id=82. Original issue from byor...@gmail.com on May 24, 2012, 08:10:44 PM UTC)

Consider these example definitions:

b = hcat' with { sep = 0.2 } [circle 1, mempty, mempty, mempty, circle 1]
d = b <> square 1

b = mempty ||| circle 1
d = b <> square 1

In both cases the output is not what I would expect. Either diagrams or my expectations need to be fixed, and the results thoroughly documented in either case.

[byorgey]

To add a bit more information, here is what is currently produced:

The problem with the second is that mempty ought to be an identity for (|||). The problem with the first is that I would expect 0.6 units of space between the circles but it looks like only 0.2. That is, I expect

hcat' with { sep = x } [a,b,c] === a ||| strutX x ||| b ||| strutX x ||| c.

I think it should be easy to make mempty an identity for beside. It probably just involves adding some special checks. I am not as sure about the issue with hcat.

[byorgey]

Making mempty an identity for beside is addressed by this pull request against diagrams-core: https://github.com/diagrams/diagrams-core/pull/24

I looked into the other issue a bit and fixing it seems trickier. The key thing to look at is the implementation of cat'. Currently, when given catMethod = Cat, it works by positioning each new diagram with respect to the accumulated diagrams using juxtapose, and then simply translating it by sep before composing with atop. But when the diagram to be composed has an empty envelope, composing it has no effect on the envelope of the accumulated diagram, so the fact that the new diagram was translated by sep makes no difference to later diagrams in the list.

One possibility (slightly ugly, perhaps, but maybe not so bad) is to keep another accumulator storing the current "offset", which is the amount to translate each new diagram before composing. Normally, this offset will be equal to sep. However, the envelope of each new diagram is tested for emptiness; if it is empty then the offset is incremented by sep. Upon encountering a diagram with a non-empty envelope, the offset is reset back to sep.

Oh... I just realized that cat' actually uses a balanced instead of linear fold, which complicates matters further. Intuitively it seems like the above scheme can still be made to work, if the increment-and-reset thing can be made into a semigroup. Something like

data IncReset a = Inc a | Reset a
instance Semigroup a => Semigroup (IncReset a) where
  _ <> Reset a = Reset a
  Reset a <> Inc b = Reset (a <> b)
  Inc a <> Inc b = Inc (a <> b)

Hrm, I'm pretty sure that's associative but I'm not sure it's quite what is needed. I'll keep thinking about it.

[byorgey]

I think I now have this figured out. What is really needed is

data Spacing a = Inc a
               | a :||: a

instance Semigroup a => Semigroup (Spacing a) where
  Inc a <> Inc b           = Inc (a <> b) 
  Inc a <> (b :||: c)      = (a <> b) :||: c
  (a :||: b) <> Inc c      = a :||: (b <> c)
  (a :||: _) <> (_ :||: b) = a :||: b

The idea is that :||: stands for a non-empty envelope, and we track the necessary space on either side of it. Inc represents some "free-floating" space which is not yet anchord to some non-empty envelope.

Pair each diagram with a value of type Spacing (Sum Double): (Inc sep) for empty envelopes and 0 :||: sep for non-empty. When combining two diagrams, determine the amount of translation necessary by

spacing x y = rhs x + lhs y
  where 
    rhs (Inc a)    = a 
    rhs (_ :||: a) = a
    lhs (Inc _)    = 0
    lhs (a :||: _) = a

and pair the resulting combined diagram with the combination of their Spacing values.

Intuitively I'm quite sure this is correct, though it might be interesting to prove formally that this gives something equivalent to cat v . intercalate (strut (sep *^ normalized v)).

[byorgey]

See https://github.com/diagrams/monoid-extras/pull/2 .

[phischu]

Hi, I come here because I expected the original behaviour but found that you seem to have hardcoded mempty to be a left identity of beside. The documentation says otherwise. Please (preferably) restore the original behaviour of (mempty ||||) changing the origin to the left edge or update the documentation. Great work, thanks a lot!

[byorgey]

Hi @phischu , I'm not going to change back the behavior of mempty/beside, as I deliberately chose the new behavior since it is more elegant/consistent. If you need to change the origin to the left edge of a diagram you can use alignL.

However, if the documentation is incorrect that is of course a bug which should be fixed ASAP! Can you be more specific---where exactly is the documentation which needs to be corrected?

[phischu]

The documentation for Diagrams.Combinators.beside, Diagrams.TwoD.Combinators.(===) and Diagrams.TwoD.Combinators.(|||) state that mempty is a right identity but not a left identity. As far as I understand this is incorrect because mempty is both, a left and a right identity for beside and friends.

[byorgey]

You are absolutely right, thanks! I've created https://github.com/diagrams/diagrams-lib/issues/83 to track this. I (or someone else) will probably fix it this weekend at Hac Phi.

[bergey]

For my own understanding, I modified cat' as byorgey described above. I haven't thought through the semantics, or tested beyond that it builds.