Post-update invariant repair: good idea or bad?

[jacob]

A few times, I’ve found myself with a model that needs some invariants to hold, and I’ve stumbled on a pattern that seems to make that work better, but I can’t decide if it’s a good pattern or a bad one. I’d be interested in your feedback.

I think it’s easiest to explain the problem by example. Imagine you’ve got this model:

type alias Model =
    { items : List Item
    , sortOrder : SortOrder
    }
type SortOrder = ById | ByPrice

and messages like:

type Msg 
     = ReplaceItems (List Item)
     | AddItems (List Item)
     | SetSortOrder SortOrder

In your view, you’d like to display items from your model in sorted order according to the configured ordering.

You could easily sort the list inside your view function, but that seems like a bad idea since sorting a big items list on every render could get expensive.

Probably a better approach would be to have your update function maintain the invariant that items is always sorted according to sortOrder. It’s not obvious how you could make a representation that couldn’t represent items that weren’t sorted according to the given order, so the “make impossible states impossible” approach doesn’t seem viable. Using the model we have, the code to do this directly looks like:

update : Msg -> Model -> Model -- (no commands for simplicity)
update msg model =
     case msg of
         ReplaceItems items ->
             { model | items = sortBy model.sortOrder items }
         AddItems items ->
             { model | items = sortBy model.sortOrder (List.concat items model.items) }
         SetSortOrder sortOrder ->
             { items = sortBy sortOrder model.items
             , sortOrder = sortOrder
             }

This code is problematic to maintain: You have to remember to maintain the invariant everywhere that could change items or sortOrder! It would be easy to add a new case someday and forget that you needed to do this, which would end up introducing a bug. (And if you’ve forgotten the invariant – or if it’s your coworker, who never knew about it in the first place, who writes the new code – it might be hard to figure out what’s going wrong.)

I’ve been in situations like this a couple times, and both times I’ve ended up with the same solution: allow the main update function to break the invariant, and then pass the result of update through a post-processing function that repairs it. In this example it would look like:

updateBreakingInvariants : Msg -> Model -> Model
updateBreakingInvariants msg model =
     case msg of
         ReplaceItems items ->
             { model | items = items }
         AddItems items ->
             { model | items = List.concat items model.items }
         SetSortOrder sortOrder ->
             { model | sortOrder = sortOrder }

repairInvariants : Model -> Model
repairInvariants model =
    { model | items = sortBy model.sortOrder model.items }

update : Msg -> Model -> Model
update msg model =
    updateBreakingInvariants msg model 
        |> repairInvariants

This has the advantage that you only have to state the invariant one time, and you don’t have to remember it every time you add or edit your update cases. The downside is that you pay the cost of repairing your invariant whether the update broke it or not.

I’ve used this pattern a couple times in different contexts, but I’m not sure whether it’s a great idea or a terrible one. People who have run into similar problems, have you found better solutions to the problem? Does this have some obvious issue I haven’t noticed? Comments welcome!

[antew]

I think that pattern is fine, we used it for a while for our analytics as well but up at the top of the app, the update function for our analytics would get the message, the old model, and the new model and could send off commands.

The only caveat is that with sorting the items on each Msg it will prevent using Html.lazy with it because it is a new reference each time, you’d have to check if the list is already sorted and return the existing model to let lazy rendering work.

One thing I might change is storing the data in a Dict and then keeping a separate list that had the Ids of the items in a sorted order, then the view function uses that sorted list and the Dict lookup.

[charliek]

@jacob

It’s not obvious how you could make a representation that couldn’t represent items that weren’t sorted according to the given order

I wrote a blog post that more or less accomplishes what you’re looking for in the first example. tl;dr - Even if an invariant can’t be modeled in a make impossible states impossible kind of way that invariant can still be guarded within the encapsulation of a module and an opaque type.

[choonkeat]

@jacob

You could easily sort the list inside your view function, but that seems like a bad idea since sorting a big items list on every render could get expensive.

for the cited example, using Html.lazy should suffice?

[gampleman]

I think what @charliek is suggesting is very good advice. Use modules to enforce invariants. This gives you a clear place to make sure the invariants are enforced without needing to worry about someone forgetting. For example:

module SortedList 
  exposing 
     (SortedList {- no exposed constructors -}
     , fromList
     , toList
     , concat {- whatever else you need -}
     )

type SortedList a
     = SortedList (List a)

fromList : (a -> comparable) -> List a -> SortedList a
fromList f =
   SortedList << List.sortBy f
     
toList : SortedList a -> List a
toList  (SortedList list) = 
    list

concat : (a -> comparable) -> SortedList a -> SortedList a -> SortedList a
concat f a b = 
  fromList f (List.concat (toList a) (toList b))

with such a module, I think most of the concerns go away.

[joakin]

Like @choonkeat, I think that if the sort order is a view only concern I would use something like Html.lazy2 viewList list sortOrder.

If it is necessary for other things on the logic of the application then I also agree a module with an opaque type that maintains the constraints internally, would be the best idea.

[MarkHamburg]

Html.Lazy will also have issues if your view depends on more than just the sort order and the list contents in that changes to those other parameters will also trigger sorting.

We’ve had similar issues in that we have a complex layout algorithm that depends on the data and the window size and there can be tens of thousands of data items in a single layout so we don’t want to run the algorithm too often. Actually drawing the results also depends on the scroll position in order to avoid rendering items that are too far out of view. Clearly recomputing the layout on every scroll event would fall in the “too often” category. (We can see the effects of such recomputation on frame rate when changing the window size.)

We’re still on 0.18 because it allows us to use lazy computation to limit the change rate on the layout results to when the parameters affecting layout change.(*) In the example that started this thread, this would amount to maintaining the collection of items and a lazy sorted version of the collection. This would be useful if the rate at which updates arrived were likely to be greater than the rate at which the sorted list was needed — e.g., maybe you tunnel into an item and can’t see the list.

Turning back to approaches that work with 0.19, one way to enforce this at a type system level is to have a private type with looser invariants and a public type with tighter invariants. An update converts to the looser type, does the update work, and then converts back to the tighter type by enforcing the invariants. You can even make the conversion back take the old and new values in order to reuse data. It’s basically a lens with a get function that converts from public to private and a set function that injects a modified private into the old public value.

Mark

(*) Actually, we’re even more tied to 0.18 at this point because after maintaining the lazy version of our compute management logic, we shifted to an approach in which we use native code to build a memoizing function for the computation that compares the parameters against its last parameters and if there is a match returns its last result. This resulted in much simpler code because the decision as to whether to recompute was hidden behind and tied to the memoization.

[Herteby]

Yeah Lazy/memoized computations is probably one of the things I miss most coming from Vue.js
This “manual” management feels a bit like going back to AngularJs or something, not very “reactive”

One thing I’m experimenting with is to wrap the whole update function with a “watcher” system.
On every update, each watcher checks if a certain field in the model was changed, and if so, updates another field in the model and/or sends a command. It’s kinda neat in that it makes it impossible to update the watched field without the “watcher” triggering. It feels a little wasteful to do equality comparisons on every update, but hopefully shouldn’t be something to worry about.

[MarkHamburg]

Wastefulness depends on how expensive the equality comparisons are.

There is also an issue of how safe those comparisons are since equality comparisons can trigger runtime crashes. For example, the ( a-> comparable ) functions in some of the examples above would be crashing values to compare for equality.

With those caveats, it’s a good architectural approach. This paper is an interesting read on having simpler updates for messages followed by invariant restoration and side-effect computation: https://www.usenix.org/system/files/conference/atc15/atc15-paper-stutsman.pdf

Mark

[Herteby]

Actually, since Elm uses reference equality as the first step in comparisons, it should always be super fast when a field hasn’t been updated. It’s only when you make a change that it actually needs to traverse any data structures and such. So I think it should be fine.

Which values are there that can cause a crash? I think functions, and maybe those that are labeled as <internal> in Debug.log? Json.Decode.Value maybe? None of those are things you normally store in the model anyway.