λx.1 Consulting

Katas, Category Theory, and Interviews

Viewing interview questions through the lens of category theory.

Published

reflection · category theory · kata · abstraction

In the age of AI, I have yet to see an interviewer ask about classical programming problems that are essentially LeetCode questions. At least, I have not heard of such cases from the friends I have talked to. I have also always considered someone’s ability to solve LeetCode questions to be a bad proxy for actual programming and engineering skills, but that is a different topic altogether. Nonetheless, today I will talk about katas, which are at least tangential to classical interview questions and can be a fun exercise to solve.

This will be a series that culminates in ParaForge, because I want to show how I think in terms of category theory when modeling solutions, problem spaces, and architectures.

Doing that with katas and building a programmatic “thing”—I have yet to identify what it really is—will be good preparation.

So, let us start with a simple kata for the first blog post.

Reframing Maximum Subarray Sum with Algebraic Structure

The overarching question is simple:

Can ordinary programming katas be reformulated in categorical or algebraic terms in a way that actually changes how I think about the algorithm?

For the first few examples, I am deliberately not trying to build a general solver for specifically defined problem statements. That might happen along the way of this series of blog posts. For now, the goal is much simpler: take algorithms I already understand and rewrite the reasoning behind them in terms of compositional structure.

The maximum subarray sum problem is a good first example because the normal solution is already familiar, but the algebraic version exposes something that is easy to miss when thinking only in terms of loops and pointers.

The problem

Given a list of numbers, find the maximum possible sum of a contiguous subarray.

For example:

[2, -4, 3, -1, 5, -6]

The best contiguous subarray is:

[3, -1, 5]

and its sum is:

7

The standard linear-time solution is Kadane’s algorithm. It tracks the best sum ending at the current position and the best sum seen globally.

That works perfectly well.

I would assume it is natural to instantly think of a for-loop or fold when presented with the problem and do the obvious thing I consider Kadane’s algorithm to be.

But what exactly does it take to solve this problem?

Is there something more fundamental hiding in its solution, applicable to other problems?

Is there another O(n) solution that naturally lends itself to being parallelized because it is formulated in this fundamental framework?

Of course, these are all rhetorical questions.

Suppose I cut the list in half

I already established that I like to view things from a CT point of view.

Much of CT is concerned with composition, and a straightforward way to approach this problem with composition in mind is to imagine splitting the input somewhere:

[2, -4, 3] | [-1, 5, -6]

Now forget the original algorithm for a moment.

If the left side and the right side were processed independently, what information would each side need to retain so that I could combine the two results and still recover the correct global answer?

A natural first guess is to keep the values a left-to-right scan might track for each segment x:

(total(x), bestSum(x), current(x))

Here total is the sum of the segment, bestSum is its best non-empty subarray sum, and current is the best non-empty sum ending at its right edge. In other words, current is the segment’s best suffix.

This is enough to answer the question within a segment, but not enough to combine it with a neighbour. For example, [-1, 5, -6] and [5, -6, -1] both have total = -2, bestSum = 5, and current = -1. Their best prefixes, however, are 4 and 5 respectively. After [2, -4, 3], whose best suffix is 3, the crossing candidates therefore sum to 7 and 8. The triple cannot tell these cases apart.

The missing information is at the boundary: the globally optimal subarray might start inside the left segment and continue into the right segment.

For a subarray crossing the boundary, I need:

  • the best suffix of the left segment
  • the best prefix of the right segment

Their sum is the best possible subarray that crosses the split.

The best subarray crossing the split The list is split into 2, minus 4, 3 on the left and minus 1, 5, minus 6 on the right. The highlighted best left suffix is 3; the highlighted best right prefix is minus 1 and 5, summing to 4. Together they form the crossing candidate 3 plus 4 equals 7. LEFT RIGHT 2 -4 -6 3 -1 5 suffix = 3 prefix = 4 3 + (-1 + 5) = 7
The highlighted cells make the crossing candidate [3, -1, 5], with sum 7. Here it is also the global best; in general, we must compare it with the best subarray entirely on either side.

So total, bestSum, and current already give us the total, best subarray, and best suffix. To combine segments correctly, we also need their best prefix.

What does a segment need to remember?

For every non-empty segment x, define a summary:

Summary(x) = (total, bestPrefix, bestSuffix, bestSubarray)

More explicitly:

  • total: the sum of the entire segment
  • bestPrefix: the maximum sum of a non-empty prefix
  • bestSuffix: the maximum sum of a non-empty suffix
  • bestSubarray: the maximum sum of any non-empty contiguous subarray inside the segment

To be clear: this is a fixed-size summary.

It does not matter whether the segment contains one number or one million numbers. Once the summary has been computed, the original segment can be discarded.

Being able to combine these summaries is exactly what makes the representation compositional.

Start with individual elements

As a refresher, here is the list we are considering again:

[2, -4, 3, -1, 5, -6]

For a segment containing a single number, there is no ambiguity.

For [2]:

Summary([2]) = (2, 2, 2, 2)

For [-4]:

Summary([-4]) = (-4, -4, -4, -4)

And similarly:

Summary([3])  = (3, 3, 3, 3)
Summary([-1]) = (-1, -1, -1, -1)
Summary([5])  = (5, 5, 5, 5)
Summary([-6]) = (-6, -6, -6, -6)

Now we need a way to combine two summaries.

Combining two neighbouring segments

Take [2] | [-4]. Their summaries are (2, 2, 2, 2) and (-4, -4, -4, -4); we want the summary of [2, -4].

The total is 2 + (-4) = -2. For the best prefix, we compare [2] (sum 2) with [2, -4] (sum -2). For the best suffix, we compare [-4] (sum -4) with [2, -4] (sum -2). The best subarray can be [2], [-4], or the whole [2, -4]:

total        = 2 + (-4)                = -2
bestPrefix   = max(2, -2)             =  2
bestSuffix   = max(-4, -2)            = -2
bestSubarray = max(2, -4, -2)         =  2

Summary([2, -4]) = (-2, 2, -2, 2)

At this point, the actual list [2, -4] is no longer required. The summary contains everything needed to combine this segment with another one.

Add the next element

Now combine [2, -4] | [3], using the summaries (-2, 2, -2, 2) and (3, 3, 3, 3).

The best prefix either stays on the left or takes the entire left segment followed by the right prefix. The best suffix either stays on the right or takes the left suffix followed by the entire right segment. The best subarray stays on the left, stays on the right, or crosses the boundary. That gives us one calculation for each field:

total        = -2 + 3                 = 1
bestPrefix   = max(2, -2 + 3)         = 2
bestSuffix   = max(3, -2 + 3)         = 3
bestSubarray = max(2, 3, -2 + 3)      = 3

Summary([2, -4, 3]) = (1, 2, 3, 3)

The crossing candidate is the left’s best suffix plus the right’s best prefix: -2 + 3 = 1. Again, the actual segment can now disappear.

Continue the process

Applying the same combination to the remaining elements gives the successive summaries:

Summary([2, -4, 3, -1])
  = (0, 2, 2, 3)

Summary([2, -4, 3, -1, 5])
  = (5, 5, 7, 7)

Summary([2, -4, 3, -1, 5, -6])
  = (-1, 5, 1, 7)

The fourth component is the answer, 7, corresponding to [3, -1, 5].

The actual combine rule

Suppose we have summaries:

L = (Lt, Lp, Ls, Lb)
R = (Rt, Rp, Rs, Rb)

Then the combined summary is:

total = Lt + Rt

bestPrefix = max(
  Lp,
  Lt + Rp
)

bestSuffix = max(
  Rs,
  Rt + Ls
)

bestSubarray = max(
  Lb,
  Rb,
  Ls + Rp
)

This operation combines summaries of two adjacent segments into a summary of the concatenated segment.

If I call the operation <> (often called append), then this holds for non-empty segments:

Summary(xs ++ ys) = Summary(xs) <> Summary(ys)

Summarizing a concatenation is equivalent to combining the summaries.

Why this starts looking like a monoid

The input list is naturally built using concatenation.

For example:

[2, -4] ++ [3, -1] ++ [5, -6]

If the summary operation respects concatenation, then I can replace large chunks of the original list with their summaries without changing the final result.

Schematically, for non-empty xs and ys:

Summarizing concatenated segments commutes with combining their summaries From a pair of non-empty lists, either concatenate and then summarize, or summarize each and then combine. Both paths yield Summary(xs ++ ys). (xs, ys) xs ++ ys (Summary(xs), Summary(ys)) Summary(xs ++ ys) concatenate combine (<>) summarize each summarize Summary(xs ++ ys) = Summary(xs) <> Summary(ys) Summarizing concatenated segments commutes with combining their summaries Two equal paths from a pair of non-empty lists: concatenate then summarize, or summarize each then combine. Both yield Summary(xs ++ ys). (xs, ys) xs ++ ys Summary(xs ++ ys) (xs, ys) (Summary(xs), Summary(ys)) Summary(xs ++ ys) concatenate summarize summarize each combine (<>) Summary(xs ++ ys) = Summary(xs) <> Summary(ys) =

As written, the summaries of non-empty segments form a semigroup. We can make a monoid by wrapping them in None | Just(summary), where None represents the empty segment and acts as the identity.

This is the first algebraic shift in perspective:

The algorithm is no longer primarily about moving through indices. It is about finding a summary representation that composes correctly.

We focus on the summary type together with its combine operation!

Where the fold comes from

Once every individual element can be mapped to a summary:

2   -> (2, 2, 2, 2)
-4  -> (-4, -4, -4, -4)
3   -> (3, 3, 3, 3)
...

we can combine those summaries repeatedly:

singletonSummary(2)
  <> singletonSummary(-4)
  <> singletonSummary(3)
  <> singletonSummary(-1)
  <> singletonSummary(5)
  <> singletonSummary(-6)
Map elements to singleton summaries, then combine in input order For non-empty input 2, -4, 3, -1, 5, -6: start with the singleton summary of 2. Append the singleton summary of -4 to obtain the summary of [2, -4]; append the singleton summary of 3 to obtain the summary of [2, -4, 3]. Continue mapping and appending -1, 5, and -6 in order to obtain the summary of the whole input. This non-empty fold does not give the four-field summary an empty identity. 2 → singleton(2) -4 → singleton(-4) summary([2, -4]) 3 → singleton(3) summary([2, -4, 3]) summary(input) <> <> … then -1, 5, -6 in order
Each element becomes a singleton summary before it is appended to the accumulated summary. This trace starts with the first element; the optional fold below handles [] = None.

That is a fold.

Conceptually, for a non-empty input:

result = fold1(combine, map(singletonSummary, input))

To fold over any input, including the empty list, lift the summaries into that monoid:

None <> value = value
value <> None = value
Just(left) <> Just(right) = Just(combine(left, right))

result = foldMap(x -> Just(singletonSummary(x)), input)

So [] produces None; a non-empty input produces Just(summary), whose bestSubarray field is the maximum subarray sum. This keeps subarrays non-empty: None is an identity for the fold, not a subarray with sum zero.

The fold becomes almost inevitable after the compositional summary has been discovered.

It is all about composition:

What information must each segment preserve so that two independently computed summaries can be combined without losing the global answer?

Runtime

At first glance, the splitting language makes this feel vaguely divide-and-conquer-ish, which can suggest O(n log n).

But that is not what is happening here.

If implemented literally as a map followed by a fold on a non-empty input:

n mappings
+ (n - 1) combinations

which is still:

O(n)

And there is no need to allocate the intermediate list of summaries at all.

Mapping and folding can be fused:

read element
-> create singleton summary
-> combine into accumulator
-> continue

So, for non-empty input, the implementation can traverse it once while keeping only a fixed-size summary.

Therefore:

Time:  O(n)
Space: O(1)

ignoring the storage of the input itself.

Associativity matters more than the direction of traversal

Because concatenation is associative and the summaries preserve it, combining summaries of non-empty segments is associative.

So this:

(((a <> b) <> c) <> d)

must produce the same result as:

(a <> b) <> (c <> d)

That means the algorithm does not fundamentally depend on processing the list left to right.

A sequential implementation can fold left-to-right.

But the same structure also permits a balanced reduction:

Balanced reduction of four summaries In input order, combine a with b and independently combine c with d. Then combine the two pair results to get (a <> b) <> (c <> d). combine independently then combine (a <> b) (c <> d) (a <> b) <> (c <> d)

The total amount of work is still linear, but the reduction has logarithmic parallel depth if enough processors are available.

That property is much less obvious when looking only at a conventional Kadane implementation.

So where is the category theory?

At this stage, I do not think it is useful to force heavy categorical vocabulary onto the problem.

Instead, let us consider again what we observed.

We have a mapping from non-empty lists to summaries:

Summary : NonEmptyList Int -> SegmentSummary

and it preserves the relevant composition:

Summary(xs ++ ys)
=
Summary(xs) <> Summary(ys)

In algebraic language, this is a semigroup homomorphism between non-empty list concatenation and summary combination. The lifted mapping,

OptionalSummary([]) = None

and

OptionalSummary(xs) = Just(Summary(xs))

for non-empty xs, is a monoid homomorphism from lists under concatenation to the optional summaries under <>.

The category-theoretic viewpoint becomes useful because it encourages us to ask about composition first:

  • What are the objects being composed?
  • What information must survive composition?
  • Can the result of processing one part be combined with the result of processing another part?
  • Does the combination obey useful laws such as associativity?

What we learned from this reformulation

The conventional formulation makes the problem look like this:

Walk over the list while keeping track of the best running candidate.

The compositional formulation instead asks:

What information about a segment is sufficient to combine it with another segment?

Although these are different ways into the problem, the resulting implementation still has the same asymptotic runtime as Kadane’s algorithm, so this is not some general optimization trick.

The reformulation exposes:

  • why the state contains the information it does
  • why the algorithm can be expressed as a fold
  • why the computation can be regrouped arbitrarily
  • why the same logic naturally supports parallel reduction

What we will investigate over the course of this blog journey is:

Given a problem specification, can we systematically discover the summary object and composition law instead of inventing them manually?

For now, I am deliberately not trying to answer that.

The first step is simply to get comfortable seeing ordinary algorithms through this lens.

I plan one or two more reformulations of known katas, just to give a few examples of approaches and formalizations.

Wherever you are, thank you for browsing through and enjoy your life.