------------------------------------------------------------------------
-- DISTRIBUTION OF SCORES FOR CIS 252 QUIZ 6
-- range:  scores
--  0- 1:  
--  2- 3:   
--  4- 5:  
--  6- 7:  
--  8- 9:  
-- 10-11:  10 11 11 
-- 12-13:  
-- 14-15:  
-- 16-17:  16
-- 18-19:  19 19 
-- 20-21:  20 20 21
-- 22-23:  22 22 23 23 23 23
-- 24-25:  25 25 25 25 25 25 25 

-- average = 20.9  median = 23
-- 
-- NOTE: Many people opted out of this quiz.  The above consists of
-- the scores (and average and median) of the people who took it.
------------------------------------------------------------------------

import Turing
import Char  -- comment this line out if your version of Hugs complains 

------------------------------------------------------------------------
-- Question 1 (9 points)
-- Consider the following Turing Machine: 

myTM :: Prog 
myTM = [( ("A",'1'),  ('1',Rght,"A") ),
         ( ("A",'0'),  ('0',Rght,"A") ),
         ( ("A",' '),  (' ',Lft,"B")  ),
         ( ("B",'1'),  ('1',Lft,"B")  ),
         ( ("B",'0'),  ('1',Rght,"C") ),
         ( ("B",' '),  (' ',Rght,"D") ),
         ( ("C",'1'),  ('0',Rght,"C") ),
         ( ("D",'1'),  ('1',Rght,"D") )
        ]

-- Assume that the initial tape contains the string "1010111" 
-- and that the tape head  starts on the leftmost symbol of the string. 
-- PROBLEM: What is the final string on the tape?   

-- ANSWER: Here is the run.
-- *Main> showRun myTM "1010111" 
-- A	 [1]010111
-- A	 1[0]10111
-- A	 10[1]0111
-- A	 101[0]111
-- A	 1010[1]11
-- A	 10101[1]1
-- A	 101011[1]
-- A	 1010111[ ]
-- B	 101011[1] 
-- B	 10101[1]1 
-- B	 1010[1]11 
-- B	 101[0]111 
-- C	 1011[1]11 
-- C	 10110[1]1 
-- C	 101100[1] 
-- C	 1011000[ ]
-- *Main> 

------------------------------------------------------------------------
-- Question 2  (8 points). 
-- Write a Turing machine that takes a (nonempty) string containing
-- a's and b's and rearranges these characters on the tape so that
-- all the a's come before all the b's, with no spaces between any
-- a's and b's.  (The final position of the tape head is up to you.)
--
-- EXAMPLE: If the original tape was "abbaab", the final tape should
-- be "aaabbb".
-- 
-- Give your answer either as a state-transition (bubble) diagram or
-- as a table, whichever you prefer.  Whatever the format, make sure
-- your answer includes all necessary information.  SUGGESTION: Work
-- out a couple examples by hand before writing your Turing machine.
-- 
-- HINT: If you find a ba on the tape (i.e, a b immediately followed
-- by an a), then rewrite the ba to ab (but there may be more work
-- to do).  If you scan the type and fail to find a ba, you are
-- done.

-- AN ANSWER: 

prob2 :: Prog
prob2 = [ ( ("findb",'a'), ('a',Rght,"findb") ),  -- first look for a 'b'
          ( ("findb",'b'), ('b',Rght,"finda") ),

          ( ("finda",'b'), ('b',Rght,"finda") ),  -- then look for an 'a' 
          ( ("finda",'a'), ('b',Lft,"switch") ),  -- change the 'a' to 'b'

          ( ("switch",'b'), ('a',Lft,"rewind") ), -- change the preceeding 
                                                  --   'b' to 'a'

          ( ("rewind",'a'), ('a',Lft,"rewind") ), -- go back to the left end
          ( ("rewind",'b'), ('b',Lft,"rewind") ), --  of the tape and start
          ( ("rewind",' '), (' ',Rght,"findb") )  --  again
        ]

------------------------------------------------------------------------
-- QUESTION 3 (8 points).  Do one of the following problems.  If you
-- do both, only the first one will be graded.
-- 
-- (a) Give a Haskell definition of

squares :: [Integer]

-- which consists of the infinite list of the squares of the
-- positive integers, e..g., [1,4,9,16,..., since 1= 1^2, 4=2^2,
-- 9=3^2, 16=4^2,...

-- SOME POSSIBLE ANSWERS
squares   = [ x*x | x <- [1..] ]
squares'  = map (^2) [1..]
squares'' = zipWith (*) [1..] [1..]


-- (b) Give a Haskell definition of 

printVert :: String -> IO ()

-- such that (printVert str) results in the characters of str being
-- printed on a line by itself (so the string is printed
-- vertically). (Recall that '\n' is the new-line character.)
-- EXAMPLE, (printVert "wren") prints: w r e n

-- SOME POSSIBLE ANSWERS:

printVert "" = return ()
printVert (c:cs) = do putStrLn [c]
                      printVert cs

printVert' "" = return ()
printVert' (c:cs) = do putChar c
                       putChar '\n'
                       printVert' cs

printVert'' str = putStr (fixup str)
    where fixup "" = ""
          fixup (c:cs) = c:'\n':fixup cs

printVert''' str = putStr (concatMap (\c->[c,'\n']) str)