-.-. ... .---- --... ...--

• Home

• Text
• Assignments
• Grads

---

• Syllabus
• Missive
• Honesty

---

• Staff
• Software
• Meet/Contact

Laziness

For this assignment, we will use the Haskell programming language. The Glasgow Haskell Compiler (GHC) is freely available for most platforms and is installed on the CS department network. To start the interactive evaluator, run /course/cs173/bin/ghci.

The following are library functions that you may find helpful:

Haskell Function	Scheme Analog
==	eq?
<, >, <=, >=	<, >, <=, >=
mod	modulo
div	quotient
not	not
!!	list-ref
filter	filter
all	andmap
any	ormap
take	(returns a prefix of a list)
takeWhile	(returns the prefix of a list satisfying a predicate)

Any function whose name begins with a symbolic character is an infix operator. Other binary functions can be used as infix operators by enclosing in backquotes (e.g., x `mod` y). Also, infix operators can be used as ordinary functions by enclosing in parentheses (e.g., (!!) [1, 2, 3] 2).

Please submit a README file explaining how you tested your code. Actual test cases are preferable, but a clear summary of what you did will be sufficient as long as your code actually works as you claim it does.

Problem 1: Prime Numbers

1. Write isPrime :: Integer -> Bool, which determines whether a given integer is prime.
2. Define primes :: [Integer], the list of all primes.
3. Revise isPrime so that it only tests divisibility by prime factors. Just turn in the revised version.

Problem 2: Longest Common Subsequence

1. Write buildList :: Int -> (Int -> a) -> [a], where ((buildList n f) !! i) == (f i) (for all i in [0 .. n-1]).
2. Write buildTable :: Int -> Int -> (Int -> Int -> a) -> [[a]], where (((buildTable n m f) !! i) !! j) == (f i j) (for all i in [0 .. n-1], j in [0 .. m-1]).
3. Write lcs :: String -> String -> String, which computes the longest common subsequence of two strings s1 and s2. Hint: you can easily compute lcs (take i s1) (take j s2) from

   lcs (take (i-1) s1) (take   j   s2),
   lcs (take   i   s1) (take (j-1) s2), and 
   lcs (take (i-1) s1) (take (j-1) s2).
   

and the knowledge of whether (s1 !! (i-1)) == (s2 !! (j-1)).

Problem 3: Minimax Search

In this exercise, you will implement a strategy to play a simple game. The game is called Mancala, but you won't need to worry about the specific rules, since we have implemented that part for you. Your job is to build a tree of possible move sequences and choose the move that appears best.
Download the support code, which provides the following set of data types and functions:

• Player: values of this type represent the players of the game (PlayerA or PlayerB).
• State: values of this type represent game configurations.
• initialState :: Player -> State represents the initial configuration of the game board (the given player goes first).
• getPlayer: State -> Player: given a configuration, returns the player who makes the next move.
• getScore :: Player -> State -> Int returns the score for the given player in the given configuration. (Bigger numbers are desirable for your player.)
• nextStates :: State -> [State] gives the possible configurations after the next move. If the returned list is empty, then the game is over.

1. Define a datatype GameTree to represent the game state after any sequence of moves. Each node should have its current configuration and a list of trees, where each tree corresponds to containing the configurations obtainable following a specific single move.
2. Define the tree of all legal board configurations (those obtainable by repeated application of nextStates to the initialState).
3. Define prune :: Int -> GameTree -> GameTree, which prunes a tree to a given height.
4. Define minimax :: Player -> GameTree -> Int, which consumes a (pruned) tree and evaluates the configuration by looking ahead and applying the minimax algorithm. If a node has no children, it receives its own immediate score. If it corresponds to Player's turn, it receives the maximum of the recursively-computed child scores, otherwise it receives the minimum.