An example for chronomorphism

Question

I don't understand how can I create some example with chronomorphism. I know about hylomorphism (cata, ana) also I know about histo and futu.

But I don't realize some example for chronomorphism (maybe some behavior as in Tardis monad).

Also related link https://github.com/ekmett/recursion-schemes/issues/42

This isn't related with Histomorphisms, Zygomorphisms and Futumorphisms specialised to lists because doesn't has some example with chronomorphism.

Answer 1

Probably the biggest use of chronomorphisms is collapsing a named syntax tree. In particular, you can refer to names that haven't been processed yet as well as names that have already been processed.

Another thing you can do with chronomorphisms is rewrite dynamorphisms! You can read more about dynamorphisms here. One of the examples they cite is the Catalan numbers. I've translated it to Haskell below.

import Data.Functor.Foldable
import Control.Arrow
import Control.Comonad.Cofree

dyna :: (Functor f) => (f (Cofree f a) -> a) -> (c -> f c) -> c -> a
dyna a c = extract . h where h = (uncurry (:<)) . (a &&& id) . fmap h . c

natural :: Int -> ListF Int Int
natural 0 = Nil
natural n = Cons n (n - 1)

takeCofree :: Int -> Cofree (ListF Int) a -> [a]
takeCofree 0 _ = []
takeCofree _ (a :< Nil) = [a]
takeCofree n (a :< Cons _ c) = a : takeCofree (n - 1) c

catalan :: Int -> Int
catalan = dyna coa natural where
    coa :: ListF Int (Cofree (ListF Int) Int) -> Int
    coa Nil = 1
    coa (Cons x table) = sum $ zipWith (*) xs (reverse xs)
        where xs = takeCofree x table

You might also find this useful. It has an example that uses a futumorphism to build a tree and a catamorphism to tear it down (though this is occluded). Of course, this map is in fact another specialization of the chronomorphism.