some algebra shit

catamorphism.hs

module Catamorphism where

import Prelude hiding (sum)

data Mu f = InF { outF :: f (Mu f) }

catamorphism :: Functor f => (f a -> a) ->  Mu f -> a
catamorphism f = f . fmap (catamorphism f) . outF

--------------------------------------------------

data ListF a b = Nil | Cons a b

instance Functor (ListF a) where
    fmap f Nil = Nil
    fmap f (Cons a b) = Cons a (f b)

--------------------------------------------------

sum' :: ListF Int Int -> Int
sum' Nil = 0
sum' (Cons x xs) = x + xs 

sum :: Mu (ListF Int) -> Int
sum = catamorphism sum'