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] instance Show l => Show (NFA l) where show (NFA states alphabet init delta final) = "States: " ++ show states ++ "\n" ++ "Alphabet: " ++ show alphabet ++ "\n" ++ "Init: " ++ show init ++ "\n" ++ "Delta: " ++ show delta ++ "\n" ++ "Final: " ++ show final data State = I Integer | S [State] deriving Eq instance Show State where show (I i) = show i show (S xs) = show xs -- Advance all states in the set by one step, for the given input letter setTransition :: Eq l => [(State, l, State)] -> [State] -> l -> [State] setTransition delta xs l = [s' | (s, l', s') <- delta, s `List.elem` xs, l' == l] -- 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 -- 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)] -- checks if 1st parameter is (non-strict) subset of 2nd parameter -- Assumes that there are no duplicates subset :: Eq l => [l] -> [l] -> Bool subset xs ys = (xs List.\\ ys) == [] -- comparision of lists where index of elements is ignored -- Assumes that there are no duplicates seteq :: Eq l => [l] -> [l] -> Bool seteq xs ys = (xs List.\\ ys) == (ys List.\\ xs) -- cartesian product going from states to states stateTimes :: [State] -> [State] -> [State] stateTimes xs ys = [ S [x,y] | x <- xs, y <- ys] -- Normal cartesian product times :: [a] -> [b] -> [(a,b)] times xs ys = [(x,y) | x <- xs, y <- ys] -- Normal cartesian product for three lists times3 :: [a] -> [b] -> [c] -> [(a,b,c)] times3 xs ys zs = [(x,y,z) | x <- xs, y <- ys, z <- zs] -- removes the last element from the tuple proj3' :: (a,b,c) -> (a,b) proj3' (x,y,z) = (x,y) -- adds the 2nd parameter as last element of the input tupple addToTuple :: (a,b) -> c -> (a,b,c) addToTuple (x,y) z = (x,y,z)