{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}
module Coalgebra where

import Control.Monad.Instances

-- Definitions for (co)algebras, adding fundeps helped in the Automata case...
class Functor f => Algebra f m | m -> f where
    phi :: f m -> m
 
class Functor f => Coalgebra f m | m -> f where
    psi :: m -> f m

-- Fixpoint, ie f (Mu f) = Mu f
-- unfortunatly we need a data constructor
data Nu f = In (f (Nu f))

-- The fixpoint is both a algebra and coalgebra,
-- because there is an arrow id: X -> X = FX, if X is a fixpoint
instance Functor f => Algebra f (Nu f) where
    phi = In
 
instance Functor f => Coalgebra f (Nu f) where
    psi (In x) = x

-- It feels weird that this always works...
semantics :: (Functor f, Coalgebra f x) => x -> (Nu f)
semantics x = phi (fmap semantics (psi x))