27 lines
839 B
Haskell
27 lines
839 B
Haskell
{-# 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))
|