On Sat, Mar 16, 2013 at 11:25:18AM +0100, Heinrich Ody wrote:
Hi,
I'm trying to learn Haskell by writing a library for automata functions. So far I finished some functions that I use to calculate the union and intersection of 2 automata for the case of finite words.
I wonder if somebody is willing to give comments on the code? For example how I could write a function to be nicer, better to understand etc. Please note that I don't know monads yet.
Thanks for your time! Below is my code (I left out some functions to make it shorter) Greetings, Heinrich
------------------ Code import Text.Show.Functions import qualified Data.List as List import Data.Maybe import Prelude hiding (init)
-- b is the type for the alphabet. -- Meaning of the parameters are (States, Alphabet, InitStates, Trans.Function, FinalStates) data NFA l = NFA [State] [l] [State] [(State, l, State)] [State]
You store a list of tuples [(State, l, State)] for the transition map and then convert it to a function with setTransition. Why not just store a function of type State -> l -> [State] in the first place instead of a list of tuples? Actually, l -> State -> [State] would probably be even more useful. Then to get a function of type l -> [State] -> [State] you can use 'concatMap'. However, you can end up with duplicate States this way. So in fact I would actually recommend using (Set State) in place of [State] (Set is from Data.Set).
data State = I Integer | S [State] deriving Eq
Hmm, I don't understand what the S constructor is for. Why can a State be a list of States? Hmm, I see from below that this is to support the 'stateTimes' operation. In that case I think it would be better to have something like newtype State a = S a and then stateTimes :: [State a] -> [State b] -> [State (a,b)] which makes State less complicated, and has the added benefit that the type of stateTimes is more informative. This also means you will have to make the state type a parameter of NFA, i.e. data NFA l s = NFA [State s] ... but that seems nice to me too. All your algorithms should only depend on e.g. an Eq or Ord constraint on s.
-- naivly test whether a given word is accepted -- for this we forward propagate the current state sets on our input word -- we assume the automaton is complete isAccepted :: Eq l => NFA l -> [l] -> Maybe Bool isAccepted (NFA states alphabet init delta final) word = if (List.nub word) `subset` alphabet then let f xs sigma = setTransition delta xs sigma in Just (((/= []) . (List.intersect final) . (List.foldl f init)) word) else Nothing
Use foldl' instead of foldl. Also, the uses of List.nub and List.intersect strongly suggest that you really should be using Data.Set instead of lists. -Brent
-- makes an automaton complete s.t. for each pair in (States x Alphabet) a the transition function returns a state. -- For this a sink state is added to States which is the result of all previously unassigned pairs in (States x Alphabet). -- This function keeps DFA deterministc. It adds the sinkstate, but it will be unreachable. makeComplete :: Eq l => NFA l -> NFA l makeComplete (NFA states alphabet init delta final) = NFA (e:states) alphabet init (unassigned `List.union` delta) final where -- e is a new state, whose integer value does not occur in states e = I ((minState states) -1) r = ([e] `List.union` states) `times` alphabet unassigned = [(s,l,e) | (s,l) <- r, (s,l) `List.notElem` (map proj3' delta)]
Given my proposed changes above, the type of makeComplete should probably be something like makeComplete :: Eq l => NFA l s -> NFA l (Maybe s) i.e. you can use Nothing to indicate the new "sink" state. -Brent