We use cookies to provide the best site experience FunctionalWorks

## Hylomorphism Explained

Marty Stumpf

7 Apr 2022

7 April 2022 • Functional Programming
• Typed Functional Programming

This is the ninth of a series of articles that illustrates functional programming (FP) concepts. As you go through these articles with code examples in Haskell (a very popular FP language), you gain the grounding for picking up any FP language quickly. Why should you care about FP? See this post.

In some earlier posts we learned about the recursion schemes `fold` and `unfold`. In this post, we learn about hylomorphism (also known as `refold`): the composition of `unfold` then `fold`.

## General Form of Hylomorphism

Recall the function signature of `foldr` in Haskell:

``````*Main> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
``````

That is, `foldr` takes 3 inputs:

1. The folding function: A function that takes two arguments, one of type `a` and one of type `b`, and returns a result of type `b`.
2. The base case: An input of type `b`.
3. The input to be folded: An input of `foldable` type `a`. For example, a list of something.

Recall that `unfoldr` in Haskell unfolds to a `list` - a `foldable` type! That is, the result of an `unfoldr` can be the third input of a `foldr`! This is exactly the case for hylomorphism: `fold` with the third input being the result of an `unfoldr`.

Let's take a look at some examples.

### Factorial with Hylomorphism

The factorial function is a classic example. Using `unfold`, one can generate a list of integers starting from `1`, up to `n`. The generated list is then input to a `fold` such that the integers of the list are multiplied to give the factorial of n.

In Haskell, we can write the factorial function with hylomorphism using `foldr` and `unfoldr`:

``````import Data.List (unfoldr) -- Import unfoldr.
fact n =
foldr
(*) -- Function input
1   -- Base case
(unfoldr  -- List input
(\n -> if n==0 then Nothing else Just (n, n-1))
n)

-- Print out example results of the fact fn.
main = do
print (fact 5)
``````

Running runhaskell fact.hs in a terminal should return `120`, the factorial of 5.

The above nicely illustrates hylomorphism in action. Writing it with pattern matching is shorter and more standard though:

``````--Factorial function, short/standard version.

fact 0 = 1 -- when the input is 0, returns 1
-- when the input is any other Int @n@, returns @n * fact (n-1)@
fact n = n * fact (n - 1)

main = do
print (fact 5)
``````

### Unfolding Using Hylomorphism

In an earlier post, we learned about `Monoid` and wrote `unfoldm`: an `unfold` function that works for the `Monoid` type class. Recall `unfoldm`:

``````unfoldm :: Monoid m => (t -> Maybe (m, t)) -> t -> m
unfoldm f a =
case f a of
Just (first, second) ->
first `mappend` (unfoldm f second)
Nothing -> mempty
``````

This can be written in the form of a hylomorphism. `unfoldm` calls itself when `f a` is `Just` something. `unfoldm` is a fold that applies `mappend` repeatedly until the result of `f a` is `Nothing`. Therefore, we have a `fold` applies to the result of an `unfold`.

``````unfoldmHylo :: Monoid m => (t -> Maybe (m, t)) -> t -> m
unfoldmHylo f a =
foldr (<>) mempty (unfoldr f a)
``````

This says exactly what we mean in a succinct way: unfold the list and reconstruct the structure as a `Monoid` using the `(<>)` method. When it's time to stop, `mappend` `mempty` to the structure.

## Closing Remarks

This concludes our last post in this series! I hope this series shows you the fun of functional programming, and guides you to think like a functional programmer.

We think a lot about types, higher order functions and the most common recursion schemes. You may have noticed that you can compose recursion schemes as you see fit, as long as the types are right.

In our next series, we'll empower you even more by deep diving a few very powerful type classes that every functional programmer should know, including `functors`, `applicatives`, `monoid`, `alternatives` and `monads`. Stay tuned!

Marty Stumpf

Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

See other articles by Marty

Related jobs

CareersCompaniesSitemapFunctional WorksBlockchain WorksJavaScript WorksAI WorksGolang WorksJava WorksPython WorksRemote Works hello@works-hub.com Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ 108 E 16th Street, New York, NY 10003