Ana-Cata (Hylo) Factorial

AnaCataFactorial.hs

{-#LANGUAGE DeriveFunctor#-}

module Main where

fix :: ((a -> b) -> a -> b) -> a -> b
fix f = f (fix f)

data Fix f = In { out :: f (Fix f) }

ana :: Functor f => (a -> f a) -> (a -> Fix f) -> a -> Fix f
ana psi f = In . fmap f . psi

anaRec :: Functor f => (a -> f a) -> a -> Fix f
anaRec psi = fix (ana psi)

cata :: Functor f => (f a -> a) -> (Fix f -> a) -> Fix f -> a
cata psi f = psi . fmap f . out

cataRec :: Functor f => (f a -> a) -> Fix f -> a
cataRec psi = fix (cata psi)

data ListF a b = Empty | Cons a b deriving Functor

type ListR a = Fix (ListF a)

genList :: Int -> ListR Int
genList = anaRec psi
  where psi 0 = Empty
        psi n = Cons n (n - 1)

cataList :: ListR Int -> Int
cataList = cataRec psi
  where psi Empty = 1
        psi (Cons n x) = n * x

fac :: Int -> Int
fac = cataList . genList

main :: IO ()
main = print (fac 10)