===============================================================================
HFA, Haskell Finite Automata
Author: Joseph Fredette
Date Created: July 30th, 2007
===============================================================================
HFA is a set of data types, type classes, and functions for working with Finite Automata. It's goal is to provide an easy to use playing field for automata, formal languages, and the like. HFA aims to use the fastest clear methods possible, that is, it will give a little on efficiency if it means clearer, easier to understand code. HFA hopefully will be of use to those wishing to learn about practical uses of Finite automata, or who know about finite automata, and are just looking to play with them.

===============================================================================
::TODO (first)::
Finish DFA-Minimizer

::TODO (in no real order)::

Write NFA module. :)
--
Provide some DFA operations like: Union, Intersection, Difference, Complement, etc
(Remember, they are not necessarily closed in all cases, so we'll need NFA's first)
--
Finish (read: start) writing the DFA minimizer algorithm
--
write some QuickCheck tests, I know- your supposed to do it first, but hell, I don't know whats going on inside my head before I start writing code. :/
--
Rewrite the DFA pretty printer to be-- prettier. With better support for longer named Symbols/States. Use Text.PrettyPrint?

---------------------------------------------------
It currently includes capbilities for working with:

DFA's


----------------------------------
Plans for HFA include support for:

NFA's
PDA's
Linear Bounded Automata
Tape Driven Turing Machines
Saving/Loading of Predefined Machines
Exporting .dot graphviz files for machines
QuickCheck Tested, Mother approved.

-----------------------
Provided in this class:

Automata, a type class for providing functions that any automata should have
State,Symbol, and associated type Synonyms, for use in definition of automata
to/from functions for Symbols and States, which convert to/from lists to the appropriate
	datatype

===============================================================================


> {-# OPTIONS -fglasgow-exts #-}
> {-# OPTIONS -fallow-undecidable-instances #-}
> module HFABase where

=======================================
We'll define some data types useful to all finite automata here, Things like State, Alphabets, etc.
=======================================

First, we define state as being an arbitrary object with equality, We then define a canonical state as being a State on Int. 

> data Ord a => State a = St a deriving (Show, Ord, Eq)
> type States a = [State a]

We have synonyms to these types for start states and final states

> type StartState a = State a

> type FinalState a = State a
> type FinalStates a = [FinalState a]

Now we'll define an a definition of an Alphabet for symbols to act on, it's pretty simple, we just want a list of some kind of type with equality.

> data Ord a => Symbol a = Sym a 
>			 | Lambda -- for Lambda Transitions, not implemented yet
>			 deriving (Show, Ord, Eq)
> type Alphabet a = [Symbol a]
> type Symbols a = [Symbol a]

Now lets define a type class for all automata that forces an "eval" function, which takes in as input a string of symbols and returns whether or not that string is accepted by the Automata

We can't, within the definition of the class, force trace to imply eval, since we don't know what the final states are in this context, however, we will use that idea to implement Automata on DFA


> class (Ord b, Ord c) => Automata a b c | a -> b, a -> c where
>	-- determines whether the string of symbols is accepted
>	eval :: a -> Symbols b -> Bool
>	-- traces the states passed through by a given string of 
>	-- symbols
>	trace :: a -> Symbols b -> (TraceOut c b)
>	-- match turns eval into a simpler structure which takes a list which
>	-- fits the type of Symbols, but is just a simple list, useful for Regex
>	-- DFA's/NFA's, etc. which need to match against strings, (typically) so
>	-- doing a "match dfa "Somestringtomatchhere"" will just work
>	match :: a -> [b] -> Bool

>	---------------
>	-- MRD trace --
>	---------------
>	eval automaton input = 
>		case (trace automaton input) of
>			Accept _ _ -> True
>			_ -> False
>	match dfa inputList = eval dfa $ toSymbols inputList

Finally, these are just some helper functions for States/Symbols

> fromSymbols :: Ord a => Symbols a -> [a]
> fromSymbols = (map toS) where toS (Sym x) = x
> toSymbols :: Ord a => [a] -> Symbols a
> toSymbols = (map Sym)

> fromStates :: Ord a => States a -> [a]
> fromStates = (map toS) where toS (St x) = x
> toStates :: Ord a => [a] -> States a
> toStates = (map St)

Some other datatypes

We write Trace out this way so it will look nice next to the DFA constructor, but so we still can have things organized the way I like. 

> data TraceOut a b = Accept (Symbols b) (States a)
>	            | Reject (Symbols b) (States a)
>	            | IllegalSymbol (Symbol b)
>	            | IllegalState (State a)
>		    deriving (Show, Eq)

> data OneOf a b c = L a
>		   | M b
>		   | R c
>		   deriving (Show, Eq)


-- Notes: 

We can generalize to a "Representable" class, which simply defines an isomorphism from one type to another, the classes like ListRepresentable would then just be an derived class from Representable

<X>Representable is then defined as

Representable a (X a) => <X>Representable where
	toX   = a -> (X a)
	fromX = (X a) -> a

maybe this is not possible, but it sure is interesting

=======================================
=======================================