Least and greatest fixed-points in Haskell

MuNu.hs

newtype Mu f = Mu (forall r . (f r -> r) -> r)

foldMu :: (f a -> a) -> Mu f -> a
foldMu alg (Mu f) = f alg

unfoldMu :: Functor f => (a -> f a) -> a -> Mu f
unfoldMu coalg a = Mu $ \ alg -> refold alg coalg a

refoldMu :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
refoldMu f g = foldMu f . unfoldMu g

mu :: Functor f => f (Mu f) -> Mu f
mu = unfoldMu (fmap getMu)

getMu :: Functor f => Mu f -> f (Mu f)
getMu = foldMu (fmap mu)

nuToMu :: Functor f => Nu f -> Mu f
nuToMu = unfoldMu getNu


data Nu f = forall r . Nu (r -> f r) r

unfoldNu :: (a -> f a) -> a -> Nu f
unfoldNu = Nu

foldNu :: Functor f => (f a -> a) -> Nu f -> a
foldNu alg (Nu coalg a) = refold alg coalg a

refoldNu :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
refoldNu f g = foldNu f . unfoldNu g

nu :: Functor f => f (Nu f) -> Nu f
nu = unfoldNu (fmap getNu)

getNu :: Functor f => Nu f -> f (Nu f)
getNu = foldNu (fmap nu)

muToNu :: Functor f => Mu f -> Nu f
muToNu = unfoldNu getMu


refold :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
refold f g = go where go = f . fmap go . g