## 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:
==eq?
<, >, <=, >=<, >, <=, >=
modmodulo
divquotient
notnot
!!list-ref
filterfilter
allandmap
anyormap
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).
```
4. 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.