Implementing an undo/redo support in an Elm application

[Ivan Dubrov]

Hello!

In my Electron application I want to have a global undo/redo functionality.

The way I see undo/redo is there are two parts: "when" and "what". "When" do you create a new "undo point" and "what" exactly do you capture.

In a "mutable" world (I use terms very loosely) the typical way to implement undo/redo is a "command stack". Every time you execute an "undoable" action, you basically, create a "diff" (or command) that tells you how to mutate your model and how to revert these changes. So, in terms of "when" and "what" you have the following:

"when": when user performs an action which is somehow marked as "undoable"

"what": the action user performs produces a "command", a recipe to mutate your model, a "diff"

I would claim that such "when" definition is very natural from the point of user: I want to see "undo points" mapped to the actions I perform and not to the actions internal to the system

However, "what" in such mutable world is a nightmare. You have to be careful that you are inverting commands properly, which is not too hard for something like simple text editor, but totally not fun when your action changes data structure significantly. Also, if you change model without capturing such a "diff" you might end up in a situation you can no longer "undo" an action as inverted "diff" (or command "undo" implementation) does not apply anymore (or even worse, you end up corrupting you data).

Now, enter the world of immutable state and pure functions producing new state. The "what" part is now much simpler: you capture the value of the whole world state and that's it (let's forget about separate undo stacks for different documents in your app or non-undoable view state like splitter positions, etc)!

"when" is now a little bit problematic. It seems like typical approach (Redux, elm-undo-list) is simply to capture state every time where is an action. However, if your application is complex enough, the undo stack is at the top and the actions sink down to the components (at least this is how I understand they way one would design Elm application). Some of the actions might be no-op actions which in the end do not change anything. Or they might change some visual representation which is not worth being captured as an individual "undoable change".

It seems like there are couple of options I have in my Elm app:

1) You compare your new state to the old one and if it is same, don't create new "undo point". However, I see two issues with that: 1) sometimes action is essentially a no-op action, but the state changes anyway (like if I use Dict.get ... Maybe.withDefault to initialize state lazily). One might argue it's a bad practice, though 2) performance might be not that great if you have really huge data structures (totally speculative claim)

2) You somehow "sniff" your actions on the top level to figure out if you should capture "undo point" after an action. However, your higher-level component which keeps undo stack will end up knowing too much about lower level components.

3) Somehow explicitly indicate when you want a new "undo point" to be created

After giving it some though, I think that I actually want the last one, which is similar to the "mutable world" "when" (and that's why I mentioned it first):.

The problem here, though, is how to deliver message to capture the state from the bottom of the system (where your actions are actually processed)? One option is to pass some sort of "context" down the hierarchy of components to make them report "capture" event to the top component. However, this would require too much boilerplate code (in my opinion). I really don't want to care about the undo stack except in cases when I really need to interact with it (with "undo"/"redo" and "capture").

Then I tried using Effects which would post message to a mailbox which app would listen to and dispatch to the top-level component. It kind of works, but I had to implement Effects.message (see https://github.com/evancz/elm-effects/issues/28 and all linked discussions) using native modules so I don't have to have these "NoOp" actions everywhere where I post "capture" event.

If you read to this point, you might be wondering, why am I writing this at all?

Well, it kind of bothers me that I might be going in the wrong direction. Maybe, I am simply not seeing the simple solution or not getting the Elm architecture right?

Any comments? Suggestions? Any similar or different experience? tl;dr?

P.S. Here is the code I currently have:

1) Undo/redo list management: https://github.com/idubrov/strumerge/blob/external/elm-discuss/src/Main.elm

2) History "messages" which initiate undo/redo/capture actions: https://github.com/idubrov/strumerge/blob/external/elm-discuss/src/History.elm

3) Two actions which "capture" state by sending message to the "history" mailbox via "EffectsExt.message History.capture": https://github.com/idubrov/strumerge/blob/external/elm-discuss/src/TreePanel.elm

4) Effects.message implementation: https://github.com/idubrov/strumerge/blob/external/elm-discuss/src/EffectsExt.elm and https://github.com/idubrov/strumerge/blob/external/elm-discuss/src/Native/EffectsExt.js

[Max Goldstein]

At the risk of stating the obvious or neglecting some important detail, have a look at this library. It handles the "what" of undo pretty well. If you're using The Elm Architecture, you keep copies of your model in that data structure, and if you undo anything, then you have an old model which completely determines the view.

However, the "when" of adding to this data structure and paging through it are probably a bit trickier.

[Ivan Dubrov]

That's what I actually use as a data structure for undo/redo. However, I have to use it in some weird way as I need a way to update state without actually recording it in the "present" of UndoList (for actions which should not create a new "undo point").

[Daniel Bachler]

Yeah I think that is an interesting problem. I haven't gotten around to implementing Undo/Redo for my own app yet but I wonder if it's not nicer to eschew Effects/Tasks/Messages for undo/redo and instead model everything as data.

What I mean is that if you think about it, with many apps both the actions the user performs and the data in the model fall into two categories: (to borrow some terminology from the OO world:) the "Document" and the "View". If you delete an item in your app, that changes the "document". If you zoom out, that only changes your current "view". But of course, the current zoom level has to be stored somewhere, meaning it is part of the model.

As far as I understand the library Max mentioned, the helper functions it provides don't easily let you split your data this  way - but maybe that is possible and I just didn't get it. The basic ideas of the library are certainly great.

To roughly sketch how I thought about implementing Undo/redo for my app:

Split my model in two: Have a List of "Documentmodels" that represent the Undo history of my app's document and that Undo/Redo operates on; and a ViewModel that stores the stuff that can be changes by the user but that can't be undone (like change the zoom setting). Split the Actions in two as well - the Undoable actions part handles creating a new undo step and carries the DocumentModel-altering action; the Nonundoable actions are directly routed through their update function without touching the undo stack.

An action that performs an undoable action can of course also modify the ViewModel, but not vice versa.

What might be a pain is combining this with Elms composition of components, because splitting the data and actions in two would somehow have to be done for each component as well. For my app that is not such a problem because this doesn't happen a lot, but for apps with many components it could be very annoying.