LazinessFor 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|
|<, >, <=, >=||<, >, <=, >=|
|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
isPrime :: Integer -> Bool, which determines whether a given integer is prime.
primes :: [Integer], the list of all primes.
isPrimeso that it only tests divisibility by prime factors. Just turn in the revised version.
Problem 2: Longest Common Subsequence
buildList :: Int -> (Int -> a) -> [a], where
((buildList n f) !! i) == (f i)(for all i in [0 .. n-1]).
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]).
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 SearchIn 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 (
State: values of this type represent game configurations.
initialState :: Player -> Staterepresents 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 -> Intreturns 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.
- Define a datatype
GameTreeto 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.
- Define the tree of all legal board configurations (those
obtainable by repeated application of
prune :: Int -> GameTree -> GameTree, which prunes a tree to a given height.
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.