1

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.

xgrommx
  • 461
  • 3
  • 15
  • perhaps putting the question at haskell-cafe@haskell.org can help – palik Oct 02 '17 at 20:06
  • see also https://stackoverflow.com/a/37002861/2789312 – palik Oct 02 '17 at 20:15
  • 1
    https://gist.github.com/danidiaz/e5debcaf531838eb6e2afd3ef3b34d60 – danidiaz Oct 02 '17 at 20:58
  • 1
    This isn't duplicate. because no example with chrono in https://stackoverflow.com/questions/36851766/histomorphisms-zygomorphisms-and-futumorphisms-specialised-to-lists – xgrommx Oct 02 '17 at 22:27
  • 1
    I'm reopening this question. One can debate the merits of the question on its own, but while it's similar to the linked question it's definitely not a duplicate. – Benjamin Hodgson Oct 03 '17 at 12:54

1 Answers1

0

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.

Sjoerd Visscher
  • 11,840
  • 2
  • 47
  • 59
  • Sorry, but looks like your code doesn't work. Could you please provide working version? – xgrommx Oct 19 '17 at 19:42
  • I don't understand why the histomorphism for Catalan numbers given in that paper is called a bogus solution, even though it gives correct results in Haskell? Why is converting the coinductive argument to the `elems` function to a simple inductive list bogus? Is it only bogus in languages with stronger type systems like Agda? – Johannes Riecken Mar 06 '21 at 14:09