[Haskell] Code snippet: constraint a heterogenous list by a deterministic finite automaton

Marcel Manthe m at tel.netbeisser.de
Fri Apr 27 16:06:30 EDT 2007


{-# OPTIONS -fglasgow-exts #-}

data HNil = HNil

data HCons a s b = Delta s b => HCons a s b

data One = One
data Two = Two
data Three = Three
data Four = Four

data A = A
data B = B
data C = C

class Delta st sy


-- you can use HaLeX to generate minimal DFA's from
-- regular expressions. 
-- http://www.di.uminho.pt/~jas/Research/HaLeX/HaLeX.html

-- the minimal deterministic finite automaton for "AB?C"

instance Delta HNil One -- One is the start state

instance Delta One (HCons A Two n)
instance Delta Two (HCons B Three n)
instance Delta Two (HCons C Four n)
instance Delta Three (HCons C Four n)

instance Delta Four HNil -- Four is an end state

-- there are two valid full sequences
x = HCons HNil One $ HCons A Two $ HCons B Three $ HCons C Four HNil
y = HCons HNil One $ HCons A Two $ HCons C Four HNil

-- if you do not terminate and/or start with HNil, you can have
-- partitial matches
z = HCons B Three $ HCons C Four HNil

-- invalid sequences do not type-check
-- b = HCons HNil One $ HCons B Three $ HCons C Four HNil
-- b' = HCons A Two $ HCons B Three HNil




-- 
View this message in context: http://www.nabble.com/Code-snippet%3A-constraint-a-heterogenous-list-by-a-deterministic-finite-automaton-tf3659611.html#a10225654
Sent from the Haskell - Haskell mailing list archive at Nabble.com.



More information about the Haskell mailing list