We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel ๐Ÿš€.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Login to see the application

Engineers who find a new job through Functional Works average a 15% increase in salary ๐Ÿš€

You will be redirected back to this page right after signin

Blog hero image

Hylomorphism Explained

Marty Stumpf 23 November, 2021 | 3 min read

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)

Join our newsletter
Join over 111,000 others and get access to exclusive content, job opportunities and more!

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!

Author's avatar
Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

Related Issues

open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 3
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 2
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 1
  • Intermediate
  • HTML

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Functional Works average a 15% increase in salary.

Start with GitHubStart with Stack OverflowStart with Email