{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, TypeOperators, ScopedTypeVariables, OverlappingInstances #-}

import Control.Monad.Instances
import Control.Compose
import Coalgebra

-- F X = 2 x X^A, for some fixed alphabet A
type F a = (,) Bool `O` ((->) a)

-- Fixpoint, ie languages
type Language a = Nu (F a)

-- auxiliary function
-- recall that the first component of psi l is true if the language accepts the empty word
is_member :: [a] -> Language a -> Bool
is_member [] l = b where O (b, _) = psi l
is_member (a:r) l = is_member r (trans a) where O (_, trans) = psi l


-- Our alphabet
data A = A | B
	deriving Show

-- Our example automaton, we will look at its language given by sem
data X = One | Two | Three
trans :: X -> A -> X
trans One A = Two
trans One B = Three
trans Two A = Three
trans Two B = One
trans Three _ = Three

fin :: X -> Bool
fin One = True;
fin Two = True;
fin _ = False;

instance Coalgebra (F A) X where
	psi x = O (fin x, trans x)


-- Test a word against it
show_member word = putStrLn $ show (word, is_member word (semantics One :: Language A))

main = do
	let words = [[A], [A,B], [A,B,B], [A,B,B,A], [A,B,A,B,A]]
	sequence $ map show_member words