Optimize cases where children are getting added, moved, removed, etc in virtual DOM

[jedimahdi]

Keyed Node

Motivation

Currently in diff of virtual dom when children are changing patches that being produced is not optimize and doing so much extra work.

Solution

To solve this problem we can use a keyed node. Each child in a keyed node associated with a key. So instead of doing a pairwise diff, we can diff based on matching keys!

Usage

view :: Html Message
view = keyedNode "ul" {} []

view :: Html Message
view = Keyed.ul {} []

[the-dr-lazy]

Let's look at another idea for KeyedElement API.

Basic Example

view :: Html Message
view =
  ul_ $ users <#> (\user -> li { key: user.id } [ ... ])

The API should be familiar for React developers. But here we are type-safe. If you set key in one child, you will become obligated to set it in all other children.

Implementation Details

1. We should carry key as a custom Fact in children nodes of a KeyedElement.

li { key: "KEY" } []

2. There should be a way to make sure all of children of a KeyedElement has same type of key. So we should represent type of the key in the VirtualDomTree type.

li {}             [] :: VirtualDomTree Nothing       slots message
li { key: "KEY" } [] :: VirtualDomTree (Just String) slots message

3. Then we can make node function ad-hoc polymorphic. So PureScript can decide to generate Element or KeyedElement. In this way we will not need something like Elm's Html.Keyed module. Thanks god that we are not cursed by the Go lang. :)

class IsKeyedNode (key :: Maybe) where
  node :: forall r key' slots message
        . String
      -> { | r }
      -> Array (VirtualDomTree key slots message)
      -> VirtualDomTree key' slots message

instance isNotKeyedNode :: IsKeyedNode Nothing where
  node = ...

instance isKeyedNode :: IsKeyedNode (Just a) where
  node = ...

[jedimahdi]

I think this is better than what I was trying to say. But I don't quite get how that Maybe kind in VirtualDomTree type works. what will be type of view function?

view :: VirtualDomTree Nothing       slots message
or
view :: VirtualDomTree (Just String) slots message

[the-dr-lazy]

But I don't quite get how that Maybe kind in VirtualDomTree type works.

It'll do two kind of jobs:

1. It makes sure that all children are homogeneous on that phantom type.

x = li { key: "KEY" } [] :: VirtualDomTree (Just String) slots message
y = li { key: 0     } [] :: VirtualDomTree (Just Int   ) slots message

children :: Array (VirtualDomTree (Just String) slots message)
children = [ x, y ]
--              ^ y doesn't match with the type of our homogeneous Array.

2. It signals to the parent that should use KeyedElement ad-hoc polymorphic function instead of Element.

what will be type of view function?

The Html is a type synonym over VirtualDomTree.

https://github.com/the-dr-lazy/purescript-monarch/blob/6bb90e6877bd71cdd24ea6bca7654b753b62d0a1/src/Monarch/Html.purs#L36

So because top-level view usually doesn't contain any key, we can simplify it by Html type synonym again.

type Html = VirtualDomTree Nothing ()

But if the view contains key or slot(s) then the Html type synonym is not applicable so the developer should use VirtualDomTree.

[the-dr-lazy]

@jedimahdi would you like to submit a PR for this feature request?

[jedimahdi]

Yeah, I'll try to write this feature.