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 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 a series of articles that connects programming, math and a problem I have had for years now.
Problem statement
Each computer I have tends to grow its Downloads folder to 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:
- Goes file by file in the source directory
- Opens the file in an appropriate program if asked to
- Lets me choose a destination folder from the set of (sub)directories of a destination directory
- Moves the file to the chosen subdirectory which I'll call target directory from now on
- Returns to step 1 until there are no more files in the source directory
There are few specific requirements for this tool:
- Console-based – no drag and drop if possible
- Keyboard-based – minimize the number of keystrokes to achieve the task
- Easy to start, even easier to stop – no one has the strength and time to do the sorting in one seating, 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 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.
input_until_validis a helper function that asks for input until a validator passesask_for_choicesis a helper function gets a list ofChoice(name, description)tuples and asks until a valid choice is presentedclean_loopis 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:skip– can't decide now. Useful for sound or movies among others.move– perform move action:- another
ask_for_choicesasks to determine which target to move the directory to
- another
open– open the file using the system'sopencommand. This choice is different from other ones as it stays at the current file until another command is entered.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's 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 a mistake. An mp instead of mt places 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 the book Discrete Mathematics 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:
- The operation is associative, so that (a · b) · c = a · (b · c)
- There's an identity element e
- For every element a, there's an inverse element a^-1 such that a · a^-1 = e
- 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 algebraical 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 always can 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
However, 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's 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.
However, 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 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 set S so 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 resultWhen 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.
Reflections
What started as a simple undo feature led to a redesign of the entire move mechanism. The group structure didn't just give us undo – it gave us deferred execution, batch application, and a clean separation between intent and action.
The key insight was that compose with eager reduction serves as a single, universal write operation. Every change to the pending state – whether it's a new move, an undo, or a composition of two histories – passes through the same function. There are no special cases because the algebra doesn't need them.
The reduction algorithm – tracing states and collapsing cycles – is the engine that makes all of this work. It's what lets us concatenate two lists of moves and trust that the result is correct, minimal, and ready to execute.
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 see how a mathematical structure can shape a program's architecture, and how constraints (like the group axioms) can simplify design by eliminating the need for ad-hoc bookkeeping.
