Weak Graph

[Jussi Kalliokoski]

On Fri, 6 Nov 2015 at 17:31 Jason Orendorff <jason.orendorff at gmail.com>
wrote:

> On Wed, Nov 4, 2015 at 10:09 AM, Jussi Kalliokoski
> <jussi.kalliokoski at gmail.com> wrote:
> > I'm trying to come up with a solution to the problem of rendering lists
> [...]
> > My idea for a solution is that the lists are immutable, contain a
> reference
> > to their parent and a changeset / diff compared to their parent. [...]
>
> Good problem, interesting idea.
>
> > The biggest problem is that this will leak memory like crazy; every
> revision
> > of the list will be preserved.
>
> OK. Perhaps obviously, the only way around this is to mutate the list,
> breaking the chain at a point where nobody cares about the rest of it
> anymore.
>
> The approach you've outlined is to have the GC tell you when to do the
> mutation, but why is that a good idea? You can do it deterministically
> in getLineage().
>

I'm not sure I follow.


> Maybe the concepts here would be clearer if we limited the graph to a
> single linked list.


Perhaps graph as a concept is too wide for expressing this, but it surely
is not a linked list either. It may look like one in some cases though,
when there's only one lineage and no branching. However that is not the use
case here as when application state gets transformed to a view
representation it may have various transformations applied to it, such as
sorting, mapping or filtering.


> Then it looks a lot like a stream, in the
> functional reactive programming sense. Let the user (in this case, the
> renderer) buffer the diffs as needed; it knows when to reset the list.
> And no need for fancy data structures: it could just be an Array.
>

That misses the point, to say the least. The idea of React is that you can
represent the UI as a declarative function of a snapshot of the state, so
the view doesn't have to care about async. With FRP you
subscribe/unsubscribe to asynchronous streams which, not unlike the idea
here, can be transformed just like normal data structures and forked (to
fork an immutable data structure is to just pass the reference). The
difference is that streams are an inherently async structure, while what
I'm trying to do is not. The idea being not only that the easy case of
insert without transforms is O(1), but almost every use case can be further
better optimized by knowing the previous state of the data structure.

Consider this: You have a large list of items as an array, unsorted, as
your state. The view is a paged listing of the items sorted by different
criteria. So basically:

```JS
list
  .sort(ascendingBy("something"))
  .slice(FIRST_INDEX_ON_PAGE, LAST_INDEX_ON_PAGE)
  .map(item => <Item item={item} />)
```
Now something gets added to the middle of the list. Let's look at what we
can do with this information at each stage, if we know the previous list
and the diff to that:
* We can perform the sort in linear time because we just have to find where
the added item belongs in the list.
* The slice now has a different diff (only the insert position is
different), and
 - if the added item is in view, we can make the insertion index relative
to our view and add a remove for the last item in the list.
 - if the added item is before the view, we return an insert for the item
coming to view and a remove for the item leaving the view.
 - if the added item is after the view, the diff is empty, so we can stop
here.
* We can map just the diffs at the last stage.

You can implement this with streams, but that will just be an unnecessary
abstraction level offering no simplification whatsoever while making the
concept needlessly async. Another significant difference between this and
FRP is that streams require imperative subscribe / unsubscribe, which is
basically just sophisticated reference counting, while having the same
issues (user after free -> update after unmount, leaks). What I have in
mind can also be implemented using reference counting, and in fact will be
to in my initial version, but having a WeakGraph data structure would make
this nasty artifact and source of easy bugs (use after free -> use after
unsubscribe, leaks) go away, just like WeakMap and WeakSet are designed to
do for certain other cases.

- Jussi


>
> -j
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20151108/609f245c/attachment.html>