Support for modifying named subdiagrams

[byorgey]

Currently there is no functionality to let you modify a named subdiagram. The problem is that name maps are represented as just a finite map from names to subdiagrams---in particular the information about where a subdiagram sits within the tree corresponding to its parent diagram is not stored. One idea is to store along with each subdiagram the path from the root to the subdiagram. Modifying a given subdiagram is then just a matter of following the path into the tree, replacing the subdiagram, and rebuilding the spine of the tree (along upwards monoidal annotations) along the path. It seems like this should work in principle though there may be some trickiness involved that I haven't thought of.

[JohnLato]

I've been thinking about this, and I think it can be implemented without storing the subdiagram path, or indeed changing the QDiagram type at all.

My idea is to just descend the tree, at each branch checking if the requested Name exists in each sub-tree. If so, continue descending, and if not, leave that branch alone. Continue descending until the correct Name annotation is reached (i.e. the correct Act node is at the root of the subtree), apply the modifications, then re-build the spine. I think this can be implemented very simply by writing a general bottom-up traversal of a DUALTree and then a name-specific transformation function.

Since we'd have to descend the tree anyway (in order to rebuild the spine), this is nearly as efficient as following a path. There is a cost of checking alternate paths at branches, but I think that's probably better than having to update the path annotations, especially as this will likely be a relatively rare operation. I'll try to code it over the next couple days.

[byorgey]

Aha, indeed, that sounds like an excellent idea. This also neatly gets around the issue of multiple subdiagrams with the same name --- no need to store a set of paths or whatever, just filter at each node according to whether the given name exists in a subdiagram.

[JohnLato]

It turns out my idea isn't quite so great, for two reasons. I was mistaken about how named subdiagrams are currently stored. The current structure is basically Concat [LeafU submap, subdiagram]. One problem is that my current scheme would implicitly rely on this structure, which feels a bit off. The more serious problem is that submaps can refer to arbitrary subdiagrams, even subdiagrams that don't appear in the tree at all. So, here are a few possible solutions:

• place subdiagrams under a named node, e.g. Annot name subdiagram. Maybe there's a smart way to make this a Down annotation, but I don't see it now. A traversal could get to roughly the correct location by following submaps as I originally proposed.
• store a relative path to a subdiagram in the submap. Traverse the tree until the root of the up annotation is found, then follow the relative path (which would commonly be Up, Desc 2)
• create a semigroup for paths to names and make this part of the up annotations.

I feel like Option 3 would result in more duplicated information within a diagram and a more fundamental change, but would probably be the cleanest to implement. Option 2 is conceptually straightforward, but implementing it properly would require a small bit of effort to create the proper framework. Another option may be to create a new prim to refer to a named subdiagram, but that feels like a radical change.

I'll continue to experiment on this; I'd appreciate any ideas or comments.

[byorgey]

Ah, hrm, I guess you're right. The details of how this all works are not really loaded into my head right now. Option 3 does indeed sound cleanest. I don't really mind a bit of duplicated information. I can't say I am very keen on Options 1 or 2.

I also don't understand what you mean by creating a new prim to refer to a named subdiagram. Do you mean to replace named subdiagrams by a placeholder prim, and then look it up when it's time to render it? That wouldn't work since multiple different subdiagrams can have the same name (by design!). If you meant something else then you'll have to explain.

[JohnLato]

That was exactly what I meant by a new prim. That seems tricky to work around without running all the naming stuff in a Q monad.

I'll see if I can get an implementation along the lines of Option 3. I'm a little busy with personal stuff at the moment so it won't happen right away, but it would be nice to have working with the next release.

[byorgey]

OK, no rush. As you have seen I am deep in the midst of implementing some big features (with not too much time to work on it either) so the next release is not imminent.

[cchalmers]

I'm having a go at this. I didn't actually read this before but I ended up doing option 3. Creating a semigroup for the paths wasn't too bad, and getting there from a name seems to work. The problem now is what to do once you're there.

Should the diagram you're traversing over be the "original" diagram when it was named? In which case we'd have to store the original diagram and well as accumulate any down annotations applied since then. Or should the diagram include all the down annotation applied since it was named? I'm currently doing the latter but I think I'll end up doing both since they both have uses.

Once you've done that and edited the diagram what should happen to the up annotations? If we want them to be included we'd have to store all the left and right (separately) up annotations the diagram has seen since it's been named, and append these either side to the edited diagram.

Right now I'm looking at

data DUALSub d u a l = DUALSub
  { leftUps       :: u
  , downs         :: d
  , rightUps      :: u
  , pathToSub     :: Tape
  , originalDUAL  :: DUALTree d u a l
  }

where data Tape = T [Int] Int contains the path to the sub, along with the number of a annotations it expects to see. And every time a diagram appends with another, this needs to be updated.

Sorry if this doesn't make much sense, I just thought I should get my current thoughts down. Any suggestions would be great. I'll try to mash together what I've done in a PR soon so it makes more sense.

[byorgey]

Re: the "original" diagram vs. getting accumulated down annotations, the Subdiagram type already encapsulates the notion of a diagram paired with some accumulated down annotations, and there are functions for extracting the original diagram or extracting the diagram with applied down annots (rawSub and getSub, respectively). So in some sense the machinery for doing either is already there. However, it does seem strange/problematic to edit the version of a subdiagram with all the down annotations applied. What if you add more down annotations? Where do they go? They can't go at the root of the entire diagram since then they would affect everything else. But if you put them right above the diagram being edited they are in the wrong order with the down annotations from the context. So I think it only makes sense to edit the "original" diagram.

Not sure I understand your question about up annotations, I'll keep thinking about it.

[cchalmers]

Adding more down annotations to the selected diagram can make sense, but you have to push down all the d annotations in its path. Diagrams either of the target receive the down annotations up to that point. Maybe this code snipped will explain it better (I'm using Data.Seqence for the Concat, iss is the path to the target diagram)

  go d []         = f d . DUALTree u2
  -- Search for the next Concat and get element i from it.
  go d iss@(i:is) = \case
    Down d' t -> go (d `mappend` d') iss t
    Annot a t -> annot a <$> go d iss t
    -- Everything on the left and right of the target receives the d
    -- annotation accumulated so far. The target has its d annotation
    -- pushed further down.
    Concat ts
      | (sL, sR') <- Seq.splitAt i ts
      , t :< sR   <- viewl sR' ->
          go d is t <&> \(DUALTree u' t') -> DUALTree u' $ list $
            if | null sL   -> [t', dw sR]
               | null sR   -> [dw sL, t']
               | otherwise -> [dw sL, t', dw sR]
          where dw = Down d . Concat

Things get a little icky but I'm pretty sure it works out.

Regarding up annotations, maybe an example will help. Says you have two squares next to each other. You traverse over the left one and half it's size. What should the envelope of the new diagram be? If you it "as if the left square was originally half the size" we'd have to store the envelope without the left square so we can add new up annotation without the original left square.