Avoiding IDs in editable lists of things

[maxf]

Remember the CounterList example? [1] In order to have more than one instance of a Counter, the model added identifiers for each counter: counters : List ( ID, Counter.Model ).

The reason why an ID is necessary is that in order to delete a counter from the list, you pass its ID in the Remove id event and filter the corresponding counter out of the model.

But otherwise the ID isn’t needed, and is a potential cause for putting our model in an impossible state in the future. And it forces us to introduce the nextID field, which is a bit awkward.

If you try not to have an ID, it won’t work because you can’t remove a specific counter from the list without an ID, since Elm only uses structural equality.

Is the conclusion that having IDs is inevitable for this sort of modifiable lists?

[1] https://github.com/pdamoc/elm-architecture-tutorial/blob/dev/examples/4/CounterList.elm

[pdamoc]

You need a way to identify the counter in order to make sure that you are referring to the same thing both in update and in view. You need a way to route the messages that update the counter.

Now, you can avoid using those IDs if you want and rest on positional information by using something like indexedMap but I think that would be more brittle.

[Sidney]

Why not use an Array or Dict?

[itsgreggreg]

There is no need to track IDs if referencing the counters is limited in scope to the model that manages them. But if you ever want to pass a reference to a counter around your application, using anything other than a counter unique ID is going to remove the guarantee that you’re referencing what you think you’re referencing.

An example without IDs: https://ellie-app.com/br3KKkdkqa1/1

[maxf]

Yes, that’s the same suggestion as @pdamoc to use indexedMap, and I agree it seems brittle and doesn’t really make the code more readable than using an ID.

[maxf]

I’m not sure how that would work either way. Could you perhaps elaborate?

[rupert]

Zipper lists (or trees) can be used to do this without IDs:

Where I need to handle mouse overs on a list of elements, I wrote:

Events.onMouseOver <| MouseOverNode zipper

Where zipper is the zipper list positioned at the item having the mouse over handler attached to it. Then when the event happens, the zipper is passed to the update already positioned, and the new state can be calculated from that - you could alter the item, delete it, move it and so on.

I do wonder about the memory overhead of doing this… but it seemed to perform well enough when I tried it.

[Sidney]

Sorry, I should have clarified. This doesn’t really relate to “Avoiding ID’s in editable lists”, but I was looking at how the CouterList used the list of counters, and I thought a Dict would make accessing random elements more efficient. Or perhaps I’m missing something? I haven’t read through the full tutorial repo, but now I realize that Dict was likely being avoided to reduce compexity…

This is what it the CounterList module might look like using a Dict instead of a List:

https://gist.github.com/SidneyNemzer/e06c80da67c1bc92bd5460640f27ff15#file-counterlist-elm

[dta]

This does address one of the concerns in the OP, though, in that it helps make impossible states less possible by ensuring that there is only ever at most one counter with a given ID.

[maxf]

True, it does avoid ID duplication. But I’m not sure that deduping IDs by replacing the previous element with the same ID is a satisfactory tradeoff to preventing the model from being impossible! But I guess that’s another discussion…

[Sidney]

The Dict does help to prevent “impossible state”, since it prevents item duplication. As you’ve pointed out, it really only affects the model – It’s still possible for a Msg to come in with an invalid ID.

In other words, “impossible updates” are still possible. Personally, I haven’t found a way to really fix this. Generally, when I’m forced to handle an “impossible update” (we need to update a list item, but the item doesn’t exist?), I’ll just do nothing in the impossible case.

Conceivably, it could be treated as an error and sent to a logging service for a developer to investigate. And hope that it wasn’t caused by a mistake in your view code, displaying an invalid option for the current state.

I’m curious how others have handled these kind of “impossible updates” in their Elm applications.

[rupert]

It’s still possible for a Msg to come in with an invalid ID.

In other words, “impossible updates” are still possible. Personally, I haven’t found a way to really fix this.

The zipper list approach solves this, as each message must be associated with exactly one item in the list.

In other situations, I have used a Dict approach with ids. If the id is not found in the Dict, then just let that particular update be a no-op, not perfect but not too messy either.

[Sidney]

The zipper list approach solves this, as each message must be associated with exactly one item in the list.

True, it does prevent impossible state in updates. However, I try to keep as little state as possible in Msg’s to avoid a desync between what the Msg’s in the view are holding and the actual state. Although if the view is re-calculated after any model change I suppose it can’t desync?

Also, I’m not excited about the memory implications of storing a copy of state for multiple Msg’s on the page.

[rupert]

Yes, I also wonder about the memory implications - however, I think there should be ‘structure sharing’ going on.

Suppose I have some items in a zipper list, Zipper LargeObject, then each version of that list over a set of N items will consist of the item currently in focus and the pre and post lists of the other items. It will have memory N * size (LargeObject + some small overhead for the list structures themselves). However, the set of all N possible zippers will not be N times that, as each of the large objects will not be copied. So the size of all possible zippers would be N * size (LargeObject) + N^2 * size (overhead).

So it depends how big the objects are, and how many of them you have. I guess my objects are not typically that huge, but you can only fit so much stuff on one screen so N is never huge either.

In practice I found it worked well enough so far that I have not been concerned about performance, but I’ve never really been working with lists longer than 50 either. It would be interesting to try some memory profiling on it - I find the profiler in Chrome pretty baffling compared with jProfiler from my Java days.

[MarkHamburg]

Passing new versions of the zipper in the messages (which is what I take it you are doing) is vulnerable to the async messages problem where a replacement model can be out of date by the time it is processsed.

Mark

[rupert]

It is a good point about the async messages problem.

The UIs I built this way turned out to be ok with ‘last action wins’ even if I did not particularly design them with that intention.

An example might be a list of items one of which changes to a highlighted state when the mouse goes over, and reverts when it leaves. The async messages problem might cause one of those events to have its update state discarded by another, if the mouse moves too fast. This could result in multiple items being in the highlighted state. So it needs a bit of care when doing this.

[rupert]

Also my thinking above about the memory size being ~ N^2 * size (overhead) is wrong.

If we have lists like:

l1 = [1,2,3,4]
l2 = 0 :: l1

Then l2 does not add allocate 5 new cons cells, it allocates 1 new cell with a reference to l1. The zipper lists will similarly structure share the cons cells of their lists, so I think the overhead per item will be a small constant. The whole structure will be O(N), same as a Dict/List/Array approach.

[system]

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.