CPSC 201 -- Introduction to Computer Science

Solutions to Assignment 4
-------------------------
Written by Paul Hudak
February 10, 2008

> module Assignment4 where
> import List

Problem 1
---------

Here is the monomorphic definition of DFA:

data DFA = 
  DFA [Int]               -- the set of states is a list of Ints
      [Char]              -- the alphabet is a list of Chars
      Int                 -- the start state in an Int
      [Int]               -- the final states are Ints
      Int -> Char -> Int  -- the transition function

And here is a polymorphic version, which we will use in our program:

> data DFA s a = 
>   DFA [s]          -- the set of states
>       [a]          -- the alphabet
>       s            -- the start state
>       [s]          -- the set of final states
>       (s->a->s)    -- the transition function

Now for the DFA simulator:

> runDFA :: Eq s => DFA s a -> [a] -> Bool
> runDFA (DFA _ _ st fss fun) xs =
>   foldl fun st xs `elem` fss

Test:

> d :: DFA Int String
> d = DFA [0,1,2,3,4,5,6,7,8]
>         ["Many","All","Some","Funny","Green","Wet",
>          "Boys","Girls","Aardvarks","Run","Sit","Study"]
>         0 [7] dfaFun

> dfaFun :: Int -> String -> Int
> dfaFun 0 "Many"      = 1
> dfaFun 0 "All"       = 1
> dfaFun 0 "Some"      = 1
> dfaFun 1 "Funny"     = 2
> dfaFun 1 "Green"     = 3
> dfaFun 1 "Wet"       = 4
> dfaFun 2 "Green"     = 5
> dfaFun 2 "Wet"       = 5
> dfaFun 2 "Boys"      = 6
> dfaFun 2 "Girls"     = 6
> dfaFun 2 "Aardvarks" = 6
> dfaFun 3 "Funny"     = 5
> dfaFun 3 "Wet"       = 5
> dfaFun 3 "Boys"      = 6
> dfaFun 3 "Girls"     = 6
> dfaFun 3 "Aardvarks" = 6
> dfaFun 4 "Green"     = 5
> dfaFun 4 "Funny"     = 5
> dfaFun 4 "Boys"      = 6
> dfaFun 4 "Girls"     = 6
> dfaFun 4 "Aardvarks" = 6
> dfaFun 5 "Boys"      = 6
> dfaFun 5 "Girls"     = 6
> dfaFun 5 "Aardvarks" = 6
> dfaFun 6 "Run"       = 7
> dfaFun 6 "Sit"       = 7
> dfaFun 6 "Study"     = 7
> dfaFun _ _           = 8

> s1 = ["All","Green","Wet","Aardvarks","Study"]
> s2 = ["Some","Wet","Boys","Run"]
> s3 = ["All","Green","Wet","Funny","Aardvarks","Study"]
> s4 = ["All","Girls","Study"]
> s5 = ["All","Green","Wet","Ardvarks","Study"]

> dTest = map (runDFA d) [s1,s2,s3,s4,s5]

The above returns [True,True,False,False,False]


Problem 2
---------

The Lindenmayer grammer in Chapter 23 does not distinguish terminals
from non-terminals, and thus we just group them together as one
alphabet.  Also note that all productions are context-free, meaning 
that each production maps one symbol to a sequence of symbols, and 
there is only one production for each symbol.  We choose to represent 
the set of productions as a list of symbol/list-of-symbol pairs.

> data Grammar a = Grammar [a]         -- alphabet
>                          a           -- start symbol
>                          [(a,[a])]   -- productions
>   deriving Show

To generate a succession of "sentential forms", we need to expand each
symbol "in parallel" at each step -- we use "concatMap" to do that.  The
repetition of this process at each step is achieved using "iterate".
Note also that a list of productions is essentially an "association 
list," and thus the library function "lookup" works quite well.

> generate :: Eq a => Grammar a -> [[a]]
> generate (Grammar _ st ps) = iterate (concatMap f) [st]
>   where f a = maybe [a] id (lookup a ps)

Note how the use of higher-order functions makes this definition
concise yet efficient.

Test
----

A Lindenmayer grammer for red alga (from the Omnibus):

> lind = Grammar "abcdefgh|()/\\"
>                'a'
>                [ ('a',"b|c"),
>                  ('b',"b"),
>                  ('c',"b|d"),
>                  ('d',"e\\d"),
>                  ('e',"f"),
>                  ('f',"g"),
>                  ('g',"h(a)"),
>                  ('h',"h"),
>                  ('|',"|"),
>                  ('(',"("),
>                  (')',")"),
>                  ('/',"\\"),
>                  ('\\',"/")
>                ]

> t1 = generate lind

To make it look nicer:

> t n = sequence_ (map putStrLn (take n t1))

As an example, the 10th element in this sequence is:

b|b|h(b|b|e\d)\h(b|b|d)/h(b|c)\h(a)/g\f/e\d