You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
47 lines
1.2 KiB
47 lines
1.2 KiB
{-# 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
|