💬 NLP

Comonadic Morphophonology: A Compositional Framework for Context-Dependent Morphological Rules in Finnish

This paper introduces a novel comonadic framework using the Writer comonad to model Finnish morphophonology as composable local functions, achieving a 67-fold reduction in rule complexity compared to traditional finite-state approaches while enabling efficient bidirectional morphology with high accuracy.

Original authors: Yongseok Jang

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yongseok Jang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "State Explosion"

Imagine you are trying to teach a robot how to speak Finnish. Finnish is a tricky language where words change their shape depending on what comes next to them.

Consonant Gradation: If you add a suffix to a word like kaappi (cupboard), the double 'p' turns into a single 'p' (kaapi).
Vowel Harmony: If the word has "back" vowels (like a, o, u), the ending must also use back vowels. If it has "front" vowels (like ä, ö, y), the ending must change to match.

The traditional way to teach a computer this is to build a massive map (a Finite-State Transducer or FST). Think of this map as a giant maze. Every time you add a new rule (like "delete a letter" or "change a vowel"), you have to build a new maze that combines the old one with the new one.

The Analogy: Imagine you have a map of a city. You want to add a rule: "If you see a red house, paint it blue." Then you want to add another rule: "If you see a blue house, paint it green."
In the old system, to combine these, you have to redraw the entire city map for every single possible combination of rules. If you have 10 rules, the map becomes so huge and complex that the computer chokes. This is called "state explosion."

The New Solution: The "Comonadic" Approach

The author, Yongseok Jang, proposes a completely different way to think about these rules. Instead of building a giant, pre-drawn maze, he treats every rule as a local worker who only looks at their immediate neighborhood.

1. The "Zipper" (The Moving Window)

Imagine a word is a train of cars. The computer doesn't look at the whole train at once. Instead, it uses a Zipper (a data structure).

The Zipper focuses on one specific car (the current letter).
It can see the cars immediately to the left and right.
The rule says: "Look at the car you are standing on and the one to your left. Based on that, decide what your car should become."

This is like a cellular automaton (think of the game Conway's Game of Life). Each cell only looks at its neighbors to decide its next state.

2. The "Writer" (The Deletion Problem)

Here is the tricky part: Some rules require deleting a letter.

Example: In kukka (flower), the double 'k' becomes a single 'k' (kuka). One 'k' must disappear.
The Old Problem: If you delete a letter in the middle of a train, the cars behind it have to shift forward. If you do this step-by-step, the "map" breaks, and the rules stop working together correctly.
The New Solution (The Writer Comonad): The author invents a new tool called the Writer Comonad.
- Instead of actually deleting the letter immediately, the worker puts a "Delete Me" sticky note on the letter.
- The worker keeps a list of all the sticky notes they've found.
- The train keeps moving, and the workers keep looking at the original letters (ignoring the sticky notes for now).
- Only at the very end of the process does the computer take the train, look at the list of sticky notes, and remove those letters all at once.

This keeps the rules simple and prevents the "map" from breaking. It's like a construction crew marking which bricks to remove, finishing the whole wall, and then taking the bricks out, rather than trying to rebuild the wall every time a brick is removed.

Why This is a Big Deal

The paper claims three main victories:

Simplicity: Instead of needing 874 different complex "continuation classes" (like 874 different maze paths) to handle Finnish rules, this new system only needs 13 simple functions (workers). It's a 67-to-1 reduction in complexity.
Bidirectional Magic: Because the rules are just simple functions, they work both ways. You can use the same logic to take a word and break it down (Analysis) OR take a root word and build a new one (Generation). It's like having a reversible zipper: you can zip up or zip down with the same mechanism.
Speed and Accuracy: The system was tested on Finnish sentences.
- It correctly identified the part of speech (noun, verb, etc.) for 83.9% of words using only these rules.
- When they added a small helper (a suffix tagger), it jumped to 94.6%.
- It processes words incredibly fast (microseconds), proving that this complex math doesn't slow the computer down.

Summary

The paper introduces a new mathematical framework (using Comonads) to handle language rules.

Old Way: Build a giant, rigid map that explodes in size when you add rules.
New Way: Use small, local workers (Zipper) who pass notes to each other (Writer Comonad) to handle deletions and changes. They work together in a line, and the final result is assembled at the end.

This makes the system smaller, easier to fix, and capable of handling the tricky "delete a letter" rules that usually break computer models.

Technical Summary: Comonadic Morphophonology

Problem Statement
Current approaches to Finnish morphophonology face a dichotomy between formal rigor and compositional efficiency. Traditional Finite-State Transducer (FST) cascades (e.g., Voikko, Omorfi) encode context-dependent rules like consonant gradation and vowel harmony as string-to-string relations. While effective, composing these rules leads to multiplicative state explosion; the state space of a combined automaton grows as the product of its components, making rule representation complex (e.g., Omorfi requires 874 continuation classes to encode behaviors that could be expressed more compactly). Conversely, neural models achieve high accuracy but lack a formal, interpretable account of the underlying morphophonological rules. Furthermore, existing frameworks struggle to handle length-changing operations (such as consonant deletion) within a strictly compositional category-theoretic structure without intermediate materialization or loss of associativity.

Methodology
The paper proposes a framework where morphophonological rules are treated as coKleisli arrows of a comonad, rather than as FSTs. This approach models rules as functions from a focused local context to a single output segment, analogous to local rules in cellular automata.

The Zipper Comonad: The framework utilizes the ListZipper data structure to represent a sequence with a distinguished focus and left/right context. A rule is defined as a function $f: W a \to b$ , where $W$ is the Zipper comonad. The extend operation lifts this local rule to a global transformation, applying it to every position in the string while preserving the context view for each position.
The Writer Comonad for Deletion: A central challenge is handling length-changing rules (e.g., the deletion of k in puku $\to$ $\to$ puu). A naive approach using null characters breaks strict coKleisli associativity because filtering requires materializing intermediate sequences. The authors introduce the Writer comonad ( $DeletionSet \times Zipper$ $D e l e t i o n S e t \times Z i pp er$ ). In this construction:
- Rules return a pair $(D, c)$ , where $D$ is a set of deletion positions and $c$ is the output character.
- Deletions accumulate as a monoid action (set union) during the extend phase.
- A single materialize step at the pipeline end applies all accumulated deletions.
- This preserves strict coKleisli associativity ( $extend \ g \circ extend \ f = extend \ (g \circ extend \ f)$ ) without intermediate re-materialization.
Pipeline Composition: Morphophonological processes (Consonant Gradation, Vowel Harmony, Possessive Suffix Vowel Copying) are composed sequentially using the coKleisli composition operator ( $>=>$ ). The pipeline is defined as:
$pipe = grad >=> harmony >=> poss$
This structure ensures that rules are independent, testable, and order-explicit.
Bidirectional Morphology: The same coKleisli arrows used for analysis (decoding) are reused for generation (encoding) via a MorphGenerator, unifying the logic for both directions.
Multi-Level Abstraction: The framework extends beyond character-level rules to morpheme-level harmony and sentence-level disambiguation (Constraint Grammar-lite). By changing the element type of the Zipper (from char to ReadingSet), the same algebraic structure applies to all levels.

Key Contributions

The Writer Comonad: The paper presents the first application of a Writer comonad (specifically $DeletionSet \times Zipper$ ) in computational morphology to handle length-changing rules compositionally. This resolves the algebraic problem of deletion in coKleisli pipelines.
Rule Representation Reduction: The framework expresses the same morphophonological behaviors encoded by Omorfi's 874 continuation classes using only 13 coKleisli arrows (11 gradation patterns + harmony + possessive), achieving a 67:1 reduction at the rule-representation level.
Formal Unification: It establishes the first framework treating morphophonological rules as first-class compositional objects with formal combination laws, bridging the gap between cellular automata theory (Capobianco and Uustalu, 2010) and natural language processing.
Implementation (MCE): A Rust library (Morphological Computation Engine) implementing this framework, targeting WebAssembly, with verified comonad laws and monoid properties.

Results
The system was evaluated on the UD Finnish-TDT development set (1,364 sentences, ~25,000 tokens):

Accuracy: The system achieved 83.92% UPOS accuracy using only rule-based disambiguation (62 active CG rules). When augmented with a lightweight external suffix tagger, accuracy rose to 94.66%, narrowing the gap to the neural baseline (TNPP) from 12.99 percentage points to 2.25.
Performance: The pipeline processes approximately 84,973 tokens per second on an Apple M-series CPU. The full morphophonological pipeline averages 2.66 µs per word, demonstrating that coKleisli composition introduces negligible overhead compared to monolithic FST implementations.
Correctness: All 11 consonant gradation patterns were correctly formalized. Seven patterns exhibited full bidirectional roundtrip correctness; the four non-roundtrip cases involved deletion, confirming deletion as the sole source of irreversibility in the current model.
Developer Ergonomics: Adding a new rule requires defining a single coKleisli arrow (~5 lines of Rust), whereas FST systems often require modifying hundreds of LEXICON entries to account for interaction combinations.

Significance and Claims
The paper claims to provide a composition algebra for morphophonological rules that FST cascades handle only through state-space multiplication. By utilizing the Writer comonad, the framework restores strict coKleisli compositionality for length-changing rules, a problem previously unresolved without multiplicative state explosion.

The authors position this work not as a replacement for lexical resources (the system still relies on a Voikko-derived FST for lexical lookup) but as a modular, orthogonal layer for rule application. They argue that this approach offers superior modularity, debuggability (per-rule testing), and formal guarantees compared to FST intersection. The paper modestly notes that while it handles agglutinative phenomena like gradation and harmony, it does not yet cover templatic morphology (root-and-pattern) or reduplication, which require segment insertion or copying beyond the current scope. The framework is presented as a practical morphological engine that validates the utility of comonadic structures in NLP.