[#823] Add extensible metadata field to StkEl
Description
Problem: We want downstream to be able to attach metadata to stack elements, e.g. for debugger. One case where this can end up useful is in making meaningful diffs between two stacks.
Solution: Extend StkEl with a new polymorphic field. Add a typeclass
StkElMeta that describes how to construct new metadata from the
element's value. StkEl constructor is replaced by a monadic "smart
constructor" mkStkEl and a unidirectional pattern synonym. The actual
constructor is not exported to avoid potential weirdness related to
metadata duplication.
Add a test implementing poor man's diffing algorithm using unique tags.
Context (i.e. how this started):
This approaches the problem of stack diffs from a slightly different angle than #823 (closed) suggests. Specifically, instead of trying to build a meaningful diff on the fly, it instead adds unique tags to each stack element, making it possible to detect precisely when elements are moved/added/removed. Special care must be taken when duplicating elements, however, but that's only two commands.
This also adds a simple algorithm that tries to build some sort of diff that takes moves into account. Complexity isn't great (n log n), and perhaps moves aren't as useful. We could do something more involved here, but arguably how involved this needs to be, exactly, is for downstream to choose. I could try my hand at implementing Heckel's algorithm if there's any demand for that, but it'll take a bit of effort, so I chose not to bother for now.
Related issue(s)
Resolves #823 (closed) (technically)
✅ Checklist for your Merge Request
Related changes (conditional)
-
Tests (see short guidelines)
-
If I added new functionality, I added tests covering it. -
If I fixed a bug, I added a regression test to prevent the bug from silently reappearing again.
-
-
Documentation
Stylistic guide (mandatory)
-
My commits comply with the following policy. -
My code complies with the style guide.