1 minute read

In the world of Haskell — and functional programming more broadly — you’ll often hear terms like functor, monoid, and homomorphism.

At first glance, these sound abstract or academic. But in practice, concepts like homomorphic types offer simple and powerful ways to reason about real-world code. In this post, we’ll demystify what homomorphisms are — especially in the context of Haskell types — and show how they enable elegant, composable software.

What is a Homomorphism?

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures.

In programming terms, a function f is homomorphic if it preserves the structure of the data it’s transforming.

More concretely:

f (a <> b) = f a <>' f b

Where <> and <>' are binary operations (like concatenation or addition) in their respective domains.

If this holds, we say that f is a homomorphism between those structures.

A Simple Example: Lists to Strings

Consider this Haskell function:

toString :: [Char] -> String
toString = id  -- In Haskell, String is just [Char]

Here, the structure-preserving operation is ++, list concatenation:

toString (a ++ b) == toString a ++ toString b

This is trivially true — it’s the identity function! But it reveals the basic idea: you can transform data without breaking the relationships within it.

Real Example: JSON Serialization

Let’s say we have a type:

data User = User { name :: String, age :: Int }

If we serialize it to JSON:

instance ToJSON User where
  toJSON (User n a) = object ["name" .= n, "age" .= a]

This transformation is a homomorphism from the algebraic structure of our User data to the object structure of JSON. It preserves meaning while changing form.

If we batch serialize a list of users:

map toJSON (users1 ++ users2) == map toJSON users1 ++ map toJSON users2

Again — structure is preserved. This homomorphic property enables:

  • Incremental processing
  • Parallel execution
  • Predictable transformations

Homomorphic Types in Practice

Homomorphic behavior shows up all over Haskell:

1. Functors

fmap id = id
fmap (g . h) = fmap g . fmap h

Mapping over a structure (e.g., a list or Maybe) preserves the structure while transforming contents.

2. Monoids

Any type with an associative binary operation and identity (like lists or numbers under addition) can support homomorphic functions:

sum (xs ++ ys) == sum xs + sum ys

3. Folds

Folding a data structure often forms a homomorphism from the data into a summary:

fold (a <> b) = fold a <> fold b

This property allows divide-and-conquer, parallelization, and modular reasoning.

Why It Matters

Homomorphic types aren’t just theoretical toys. They matter because they enable:

  • Composable programs: You can combine smaller parts without breaking global semantics
  • Parallelism: If structure is preserved, parts can be evaluated independently
  • Testing and reasoning: Homomorphic functions obey algebraic laws — easier to test
  • Refactorability: Code becomes easier to transform without changing behavior

A Cool Example: Word Count in Parallel

wordCount :: String -> Int
wordCount = length . words

This function is not homomorphic by default. Why?

wordCount (a ++ b) ≠ wordCount a + wordCount b

If a ends in a space and b begins with a word, this might hold — but not always. So to make this truly homomorphic, we’d need to:

  • Track whether the string ends in a word or space
  • Compose metadata for each segment

This leads to the classic monoid-based parallel word count pattern — encoding structure into metadata.

If You’re Curious…

  • Explore how foldMap uses monoids to build homomorphic folds
  • Try implementing a homomorphic serializer for you

Comments

You May Also Enjoy