Implementing Undo with Python and Group Theory

mp instead of mt. One keystroke, and a file that belonged in Text is now three thousand files deep in Photos, in the middle of a sorting session I have no intention of restarting.

I could have fixed that in fifteen minutes with a variable holding the last move. Instead I spent a weekend on group theory, and we'll arrive at the conclusion that undo was the smallest thing I got out of it – the same algebra handed me deferred execution, batch application and a clean separation between deciding and doing, none of which I set out to build.

Here's why that was the better trade.

In my 15-year career, even when I shifted more into managerial roles, I've never strayed from keeping my technical skills clean and sharp. That gives me immense benefits. From being able to better understand my business to offering more competitive advantage to our customers, working with code still gives me pleasure.

Particularly, I'm a proponent of coding kata – small coding exercises that help one develop a better understanding of underlying concepts and rules that govern the programming discipline. In the spare time I have, these are concise enough for me to work on and not be distracted by the present-day challenges of running a software development company.

I developed something akin to a twist on the concept of katas. My approach here is to focus on the real problems I have in my work and develop small, beautiful solutions to them. It gives these experiences meaning usually not found in the abstract coding examples found in informatics olympiads or sites such as codewars.

And here's an article that connects programming, math and a problem I have had for years now.

A word on who this is for. I'm assuming you write code for a living, that you're comfortable reading Python, and that you have no particular background in abstract algebra – everything I use, I define along the way. I'm also assuming you're the kind of person who finds "it works" an unsatisfying place to stop. If that's a description you recognize yourself in, read on.

Problem statement

Each computer I have tends to grow its Downloads folder to an immense size in a matter of a year or so, and sorting them by hand is a really cumbersome process. When you have about 3000 files in one directory and your Linux distribution file navigator has a problem just to scroll through them, you are in a bind.

I solved that problem by writing a tool that:

1. Goes file by file in the source directory
2. Opens the file in an appropriate program if asked to
3. Lets me choose a destination folder from the set of (sub)directories of a destination directory
4. Moves the file to the chosen subdirectory which I'll call target directory from now on
5. Returns to step 1 until there are no more files in the source directory

There are a few specific requirements for this tool:

1. Console-based – no drag and drop if possible
2. Keyboard-based – minimize the number of keystrokes to achieve the task
3. Easy to start, even easier to stop – no one has the strength and time to do the sorting in one sitting, so exiting the program and starting it one more time should put me in the same place as when I left.

Code analysis

The starting point for this article is a first working version of the tool. I tested it on my 3000-files Downloads folder and the sorting was a breeze. I've chipped away 100 or 200 files at a time and in a week or two had every file sorted.

The code is here: https://github.com/dragonee/sortof/blob/a8ab8cbd42f62a36af9804d54e35be70090ae734/src/sortof/sortof.py

Let's discuss the code structure quickly.

1. input_until_valid is a helper function that asks for input until a validator passes
2. ask_for_choices is a helper function that gets a list of Choice(name, description) tuples and asks until a valid choice is presented
3. clean_loop is a main program function that iterates through all files and presents a choice for each one of them, presents available options and moves files to destination directories. There are four options:
   1. skip – can't decide now. Useful for sound or movies among others.
   2. move – perform move action:
      • another ask_for_choices asks to determine which target to move the file to
   3. open – open the file using the system's open command. This choice is different from other ones as it stays at the current file until another command is entered.
   4. create – create a new directory. That way you can manipulate the set of available target directories from within the program. That's the only side effect apart from the file being moved into another directory.

A typical usage is the following:

(env) dragonee@airi ~/Kod/sortof (main) $ sortof test out
b.png
[Skip,Move,Open,Create,?] c
mkdir: Images
c.txt
[Skip,Move,Open,Create,?] c
mkdir: Text
.localized
[Skip,Move,Open,Create,?] s
a.txt
[Skip,Move,Open,Create,?] 
[Skip,Move,Open,Create,?] mt
d.jpg
[Skip,Move,Open,Create,?] mi
1 files left in test
(env) dragonee@airi ~/Kod/sortof (main) $

There are some quirks in the code as well that didn't bother me too much to fix them. For example, if there are two target directories starting with the same letter, let's say Docs and Datafiles, the program won't notify that the md command is ambiguous.

As you can see, the mt command is a compound command, which means move to Text directory. That's how I minimized the number of keystrokes required to work with the tool and it's very handy indeed.

A keen reader would also notice that there's no delete option. I tend to keep the Delete directory as one of the target directories and I'm removing it manually as the sorting is done. And surprisingly, that will come in handy in the future.

A problem

Once every few hundred files I make the mistake from the opening. An mp instead of mt requires me to stop my work, find the file in the target directory and move it back to the source directory. That's not optimal.

A solution to this problem would be to implement an undo function. There are two ways to do this:

• a naive solution – remembering the last moved file and hacking a new option to move the file back
• a coding kata solution – implementing an undo function in a way that will teach me (and you) something along the way

As you are reading this article, you might already guess I chose the second option.

Group theory

Recently I've been working through Discrete Mathematics by Kenneth A. Ross and Charles R. B. Wright, and one of the insights I gained from reading it was that the undo function is closely related to the existence of an inverse element in a group.

But what is a group?

It's a mathematical formalism related to many concepts in mathematics, especially to the idea of symmetry.

Formally, a group G is defined by the tuple (S, ·), where S is a set of group elements and · is a binary operation on them that satisfies the following conditions:

1. The operation is associative, so that (a · b) · c = a · (b · c)
2. There's an identity element e
3. For every element a, there's an inverse element a^-1 such that a · a^-1 = e
4. The set S is closed under the operation ·, so that \forall a, b \in S a · b \in S

These axioms might seem abstract at a glance, but they describe a profound algebraic structure. A group describes an operation that you can apply to any of the elements from a set, and you can apply this operation again and again, because no matter what, you are going to stay in the set. There's no risk you'll end up with a result where there's no turning back, because the operation is defined on all elements in this set. As an added bonus, all operations are reversible, so you can always come back to a place you started by applying the inverse elements operations in reverse order.

When it comes to programming, if we can conceptualize something as a group, we are safe to assume that applying a group operation over and over again never leads us to undefined behavior. There are more advantages to it, but that's what I'll leave for the next sections of this article.

Redefining sortof as a group

But in its current shape the sortof program looks nothing like a group. Even before trying to formalize the way it works as a group, we face a problem straight away.

The program is able to move files only from the source directory to target directories. Because I designed the program to favor the source directory as the only one to perform moves from, the algorithm is one-sided and there are no inverse elements to a move command and as such, no undo mechanism is present.

Another problem is that it's not clear what the group acts on. Before I introduce the group action definition, we can intuitively understand that our move commands act on a subset of our filesystem, allowing us to use rename syscall to move files around.

But the way the program is written, we face another problem. With each move performed, the set of files in the source directory gets smaller by one. If we define the set of files currently available in the directory as a structure our group action acts upon, then each time we perform a move, the set changes. As the file moved is no longer in the set, no undo is possible this way.

To address these issues, we need to change the way we're thinking about the problem. The group definition forces us to find such a set S that a file moved away from A won't be invalid.

Defining the set S

The first step is to define the set our group acts on. Instead of tracking "files currently in the source directory" (which shrinks with each move), we define S as the set of all tuples (name, bucket), where name is a filename and bucket is a directory – either the source directory or any of the target directories.

Initially, all files live in the source bucket:

S = {(a.txt, Downloads), (b.png, Downloads), (c.txt, Downloads), ...}

After a move of b.png to Images, the set becomes:

S = {(a.txt, Downloads), (b.png, Images), (c.txt, Downloads), ...}

The set S never shrinks. Files aren't removed – they change buckets. This is the key insight that makes the group structure work: every file always has a position, so every move is reversible.

Defining the group G

An element g ∈ G is a list of moves, where each move is a tuple (name, src_bucket, dst_bucket). For example:

g = [(b.png, Downloads, Images), (c.txt, Downloads, Text)]

The group operations are:

• Identity element: the empty list [] – no moves, nothing changes.
• Multiplication (composition): list concatenation followed by a reduction function that removes cycles.
• Inverse: reverse each move's direction and reverse the order. The inverse of [(a, X, Y)] is [(a, Y, X)].

The reduction function is what makes this work. When we concatenate two lists of moves, we may introduce cycles – sequences where a file returns to a position it previously occupied. For example:

[(b.png, Downloads, Images), (b.png, Images, Downloads)]

Here b.png moves to Images and then back to Downloads. The net effect is nothing – a cycle. The reduction removes these cycles, collapsing the list to the net effect of all moves.

The reduction algorithm

For each filename, we trace the chain of destinations visited, maintaining a stack of states. When a state is revisited, we truncate back to that point, removing the cycle.

Consider this sequence:

[(name, A, B), (name, B, A), (name2, A, B), (name, A, B)]

For name: states visited are [A] → [A, B] → [A, B, A] – cycle detected at A, truncate to [A] – then → [A, B]. Net move: A → B.

For name2: states [A, B]. Net move: A → B.

Result: [(name2, A, B), (name, A, B)].

Here's the implementation:

Move = namedtuple('Move', ['name', 'src', 'dst'])

def reduce(moves):
    per_name = {}
    order = []
    for m in moves:
        if m.name not in per_name:
            per_name[m.name] = []
            order.append(m.name)
        per_name[m.name].append(m)

    result = []
    for name in order:
        chain = per_name[name]
        states = [chain[0].src]
        for m in chain:
            dst = m.dst
            try:
                idx = states.index(dst)
                states = states[:idx + 1]
            except ValueError:
                states.append(dst)

        if states[0] != states[-1]:
            result.append(Move(name, states[0], states[-1]))

    return result

When states[0] == states[-1], the file ended up where it started – an identity move – and we omit it entirely.

Composition always reduces

The multiplication operation is straightforward: concatenate and reduce.

def compose(a, b):
    return reduce(list(a) + list(b))

Because compose always reduces, any value produced by compose is already in reduced form. This is a crucial design decision: rather than reducing lazily at read time, we reduce eagerly at write time. The pending moves list is always reduced, always clean. We never need to ask "what's the actual state?" – the list is the actual state.

The inverse

The inverse reverses each move's source and destination, and reverses the order:

def invert(moves):
    return [Move(m.name, m.dst, m.src) for m in reversed(moves)]

We can verify the group axiom: compose(g, invert(g)) should yield [] for any g:

>>> g = [Move('a', 'X', 'Y'), Move('b', 'X', 'Z')]
>>> compose(g, invert(g))
[]

Each move meets its reverse, forming a cycle, and reduction eliminates them all.

The group action

The group acts on S by transforming each (name, bucket) tuple according to the moves:

def apply_to(moves, state):
    lookup = {m.name: m.dst for m in moves}
    return {(name, lookup.get(name, bucket)) for name, bucket in state}

Names with a move get their bucket replaced. Names without one stay where they are.

Implementing undo

With the group structure in place, undo becomes a single line: compose the pending moves with the inverse of the move to undo.

pending = compose(pending, invert(pending[idx:idx+1]))

This is group multiplication. The inverse move (name, dst, src) is appended, and reduce detects the cycle and cancels both moves for that name. No special-casing, no popping from lists, no bookkeeping. The algebra handles it.

The idx parameter selects which move to undo (1-indexed from the end, so the user can type u for the last move, u2 for the second-to-last, and so on up to u9).

Since pending is always in reduced form, pending[idx] directly gives us the move we want to undo. There's no need to search through a history of raw operations – the reduced list is the current state of affairs.

Deferring side effects

With the group model, we gain a natural separation between deciding what to do and doing it. The program accumulates moves as group elements – pure data, no side effects – and only touches the filesystem when the user explicitly applies:

def perform(moves):
    for m in moves:
        src_path = Path(m.src) / m.name
        dst_path = Path(m.dst) / m.name
        dst_path.parent.mkdir(parents=True, exist_ok=True)
        src_path.rename(dst_path)

perform doesn't need to reduce – its input is already reduced by compose. It also creates destination directories on demand, so even the create command (which adds a new target directory) is fully deferred. No directory is created on disk until the user commits.

This deferred model means:

• Undo is free. Since nothing happened on disk, undoing a move just cancels it algebraically.
• The user keeps control. They can review all pending moves before committing, discard everything with Ctrl-C, or apply in batches.
• Undone files reappear. When a move is undone, the file is re-inserted at the front of the iteration queue, so the user immediately gets a chance to reconsider it.

The integration

Here's how the pieces come together in the main loop. The pending list starts as the identity element [] and grows through composition:

entries = deque(sort_entries(entries, sort_type, reverse=reverse))
pending = []

while entries:
    subpath = entries.popleft()
    # ... show preview, present choices ...

    if response == "move":
        pending = compose(pending, [Move(subpath.name, p, dest / directory)])

    if response == "undo":
        target = pending[idx]
        pending = compose(pending, invert(pending[idx:idx+1]))
        entries.appendleft(target.src / target.name)

    if response == "apply":
        perform(pending)
        pending = []

Every mutation of pending goes through compose. There is exactly one operation – group multiplication – and it handles adding moves, canceling moves, and keeping the state clean. The deque replaces the original for loop, allowing undone files to be pushed back to the front.

On exit, if any moves remain pending, the program offers a final choice:

3 pending move(s):
  1. b.png -> Images
  2. c.txt -> Text
  3. a.txt -> Text
[Apply,Discard,?]

A second Ctrl-C discards silently.

A subtlety in undo numbering

There's one trade-off worth noting. The undo command uses positional indexing into the pending list – u1 undoes the last move, u2 the second-to-last, and so on. But because compose eagerly reduces after every operation, undoing a move doesn't just remove one entry – it can collapse others too.

Consider pending moves:

1. a.txt -> Images
2. b.txt -> Text
3. c.txt -> Docs

After u2 (undo b.txt → Text), pending becomes:

1. a.txt -> Images
2. c.txt -> Docs

What was u3 is now u2. The numbering shifts. In the more interesting case – if undoing a move creates a cycle with another move for the same filename – reduce could collapse additional entries, shrinking the list by more than one.

This is a direct consequence of the eager reduction strategy. Because pending is always in reduced form, the indices reflect the current algebraic state, not the historical order of commands. The same property that makes undo elegant – one operation, no bookkeeping – means the user's mental map of "u2 means that file" can be invalidated by a preceding undo.

For a tool where undo depth rarely exceeds two or three moves, this is acceptable. Printing the updated pending list after each undo would make the new numbering immediately visible. A more involved solution – stable labels instead of positional indices – would eliminate the problem entirely but at the cost of added complexity. That's a usability discussion for another day.

What the group axioms buy us

Let's revisit the four group axioms and see what each one contributed to the final design:

Axiom	What it buys sortof
Inverse element	Undo exists by construction. For every sequence of moves there is a sequence that reverses it exactly – not a feature bolted on after the fact, but a structural guarantee.
Closure	The composition of any two elements produces another element of the same set. No sequence of moves and undos can put us in a state from which we can't recover.
Associativity	(a · b) · c = a · (b · c). We can treat the pending list as a single value we compose with, rather than tracking the precise order in which the user issued commands.
Identity element	[] is a clean representation of "nothing has happened" – the starting state, the result of undoing everything, and a no-op under composition. It eliminates null checks and edge cases throughout the code.

These aren't just abstract properties we satisfied as an exercise. They are guarantees about the program's behavior that hold by construction.

Beyond the tool

There's another property worth noting. The reduced list of moves is plain data – a list of (name, src, dst) tuples. It's serializable. We can write it to a file and resume later. We can send it to another machine to execute. We can store it as an audit log of what changed and where. The computation and its result are fully separated from the side effects, and the result is a portable, inspectable artifact.

This matters beyond a small file-sorting utility. Any program whose core operations can be cast as a group gains the same structural guarantees: reversibility, safe composition, and a clean identity. These properties don't need to be tested case by case – they follow from the algebra. In more complex systems, that amounts to a formal argument about correctness, one that holds regardless of how many operations are composed or in what order.

The group axioms aren't just a mathematical curiosity. They're a design tool – one that, when it fits, can replace ad-hoc bookkeeping with provable properties.

Real world applications

In reality, many problems that need to model composable, reversible transformations have a group – or a group-like structure – hiding inside them, whether the authors recognize it or not.

Database migrations that are lossless in both directions form a group – sequences of up/down migrations compose and reduce to a known state, and rollback is algebraically safe (in practice, destructive migrations like dropping a column break invertibility, so the full group property rarely holds).

Geometry and maps – translations, rotations, reflections, panning, and zooming are invertible transformations that compose associatively, and 3D engines, GIS systems, and map renderers rely on this group structure every time they multiply transformation matrices.

Cryptography is built directly on group theory – elliptic curve groups, modular arithmetic under addition, and other algebraic structures provide the foundation for security guarantees, where operations are easy to compose but hard to invert without a key.

Accounting and ledgers – the net balance at any point is a group-like snapshot (transactions compose, every entry has a correcting inverse, the identity is a zero-value entry), but the ledger itself is an append-only log of side effects where order matters and history is never deleted – a reversal is recorded as a new correcting entry, not by erasing the original.

Puzzle state spaces – the Rubik's cube is the classic example, where each twist is a group element, composition is performing twists in sequence, and solving means factoring a scrambled state into known move sequences.

These examples span different domains, but the pattern is the same: composable, reversible transformations over a well-defined set. Wherever that pattern appears, a group or a group-like structure can formalize the guarantees that programmers otherwise enforce through convention, testing, and hope.

When it's worth it

Not every problem deserves this treatment, and it's worth being precise about when the naive undo stack is the better engineering call.

The group structure pays off when three things hold. First, the operations compose – you're not undoing a single action, but an accumulated sequence of them. Second, the side effects can be deferred, so what you're manipulating is data rather than something already written to disk or sent over a network. Third, and most restrictive: every operation has to be invertible.

That last one is where most real systems break, and it's the moment the missing delete option pays off. A real rm has no inverse – once the bytes are gone, there is no move that brings them back, and the instant you admit one irreversible operation, closure is finished. So instead I keep a Delete directory among the targets and empty it by hand once the sorting is done. Deletion becomes a move like any other, the group stays closed, and the irreversible part happens outside the program entirely.

If your operations aren't invertible, aren't composable, or can't be deferred, write the undo stack. It'll be shorter and it'll be honest.

A few rules of thumb

To sum it up in a few points:

1. If the feature is "undo", look for the inverse before you reach for a stack. A stack is bookkeeping about what happened. An inverse is a property of the operation itself, and properties don't need to be maintained.
2. If your set shrinks as you operate on it, you've picked the wrong set. The whole redesign turned on replacing "files in the source directory" with "every file, and where it currently lives".
3. Reduce at write time, not at read time. A value that is canonical on every write never has to be interpreted on read. The list is the state.
4. One write operation beats four special cases. Adding a move, undoing a move and merging two histories are all the same call to compose.
5. Keep the irreversible operations outside the algebra. One rm in the wrong place and every guarantee above is gone.
6. Data first, side effects last – and as late as the user will let you.

Reflections

What started as a one-keystroke annoyance ended as a redesign of the entire move mechanism. I went in for undo and came out with deferred execution, batch application, and a program in which deciding and doing are two separate things.

Whether this is "better" than a naive undo stack is debatable in terms of lines of code. But as a coding kata, it delivered exactly what I was after: a chance to watch a mathematical structure shape a program's architecture, and to see constraints simplify a design instead of complicating it.

Now go and find the group hiding in something you're building. That's it for today.