blog

Relatively little has been written on Elgot algebras in Haskell. While this example is a little simple-minded (computing Collatz sequences for numbers), it is to my knowledge the only example of Elgot algebras with code¹. Moreover, it shows off several of Haskell's strengths.

The Collatz sequence of a given number can be computed in Haskell as follows:

collatz :: Int -> [Int]
collatz 1 = [1]
collatz n
    | n mod 2 == 0 = n:(collatz (div n 2))
    | otherwise = n:(collatz (3 * n + 1))

But we can do better! Let's see what our code looks like with an Elgot algebra:

import Data.Functor.Foldable
-- | Values provided by https://oeis.org/A006877
coalgebra :: Int -> Either [Int] (ListF Int Int)
coalgebra 1 = Left [1]
coalgebra 2 = Left [2, 1]
coalgebra 3 = Left [3, 10, 5, 16, 8, 4, 2, 1]
coalgebra n
    | n mod 2 == 0 = Right $ Cons n (div n 2)
    | otherwise = Right $ Cons n (3 * n + 1)
collatz :: Int -> [Int]
collatz = elgot embed coalgebra

It's a good deal more verbose. But it's also more efficient, at least for small values.

As it happens, we can extend the improved performance using Template Haskell, with the added benefit that we won't tangle ourselves up by trying to write things by hand. We will now need two modules now, but otherwise it's relatively straightforward.

module CollatzTH (collatzTH) where
collatzTH :: Int -> [Int]
collatzTH 1 = [1]
collatzTH n
    | n mod 2 == 0 = n:(collatzTH (div n 2))
    | otherwise = n:(collatzTH (3 * n + 1))

Our second module will import the first:

{-# LANGUAGE TemplateHaskell #-}
module Collatz (collatz) where
import           CollatzTH
import           Data.Functor.Foldable
import           Language.Haskell.TH.Syntax
-- | Values provided by https://oeis.org/A006877
coalgebra :: Int -> Either [Int] (ListF Int Int)
coalgebra 1 = Left [1]
coalgebra 2 = Left $( lift (collatzTH 2) )
coalgebra 3 = Left $( lift (collatzTH 3) )
coalgebra 6 = Left $( lift (collatzTH 6) )
coalgebra 7 = Left $( lift (collatzTH 7) )
coalgebra 9 = Left $( lift (collatzTH 9) )
coalgebra 18 = Left $( lift (collatzTH 18) )
coalgebra n
    | n mod 2 == 0 = Right $ Cons n (div n 2)
    | otherwise = Right $ Cons n (3 * n + 1)
collatz :: Int -> [Int]
collatz = elgot embed coalgebra

Here, one of the advantages of Elgot algebras comes to the fore: we can effectively mix a "supercompiler" with normal recursion. While the Collatz sequence example does not generalize easily, it's not hard to imagine this being useful.