CSC 272
Homework 4
Assigned Feb 22, due Mar 9

This assignment is to be done in Haskell -- probably GHC. You are encouraged to do this in teams of two, both students working together on all parts of the assignment; if you do this, turn in one homework with both names on it.

As in Scheme, every function should have a contract. In many cases, Haskell can actually figure out the contract from the code, but I'd prefer that you write it explicitly before starting on writing the code.

We don't have a convenient unit-test facility for Haskell (that I know of), but you still need to write test cases for every function. Unless you find a good testing facility, do this by writing (in a text file) what specific examples you plan to try, and what the right answers to them should be. As usual, this too should be done before you start writing code.

Primes

1. Write an isPrime function that takes in an integer and returns a Boolean, telling (correctly) whether the number is prime.
2. Define a variable primes which is a list of all the prime numbers.
3. The naive way to do this involves checking whether a number is divisible by any smaller integer (greater than 1). To make things more efficient, write your definition so it only checks whether a number is divisible by smaller prime numbers, and only up to the square root of the number itself. (Doing either one of these optimizations without the other is partial credit.)

The shorter and more elegant your code is, the better.

Fibonacci numbers

1. Write a function fib which takes in an Integer n and returns the nth Fibonacci number.
2. The naive way to do this, calling fib recursively on n-1 and n-2, takes exponential time. On my computer, the naive version took 4 seconds for fib 30, 17 seconds for fib 33, and I haven't had the patience to wait for fib 35, much less fib 40. A more efficient version runs in linear time; it computes fib 10000 with no perceptible delay except the time to print out 27 rows of digits. Do an efficient version.
   I know of at least two different ways to do this. One requires re-thinking the recursion. The other involves "memoization": it still uses the "obvious" recursion, but stores the results in a table so it never computes the same Fibonacci number more than once. The latter will teach you more about Haskell.

Longest common subsequence

1. Write buildList :: Int -> (Int -> a) -> [a], where ((buildList n f) !! i) == (f i) for all i in [0..n-1]. In other words, it builds a list of the first n values of f. Hint: I did this in one reasonably-short line of code, not counting the contract.
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] and j in [0..m-1]. In other words, it builds an nxm two-dimensional table (a list of lists) containing all the values of (f i j) for i<n and j<m.
3. Write lcsLength :: String -> String -> Int, which quickly computes the length of the longest common subsequence of two strings s1 and s2.
   Hint: Solve the more general problem which, given i and j, finds lcsLength (take i s1) (take j s2). This problem can be solved easily by first answering the questions
   • (s1 !! i) == (s2 !! j),
   • lcsLength (take (i-1) s1) (take j s2),
   • lcsLength (take i s1) (take (j-1) s2), and
   • lcsLength (take (i-1) s1) (take (j-1) s2).
4. Again, you can do this in a naive, inefficient way, or you can use memoization to make it enormously more efficient. For any given s1 and s2, you can build a table with the results for all possible i and j. This table can be defined by buildTable on a function which computes answers via the above recursion, but rather than calling itself recursively, it looks up recursive results in the table.
5. It's sort of unsatisfying that lcsLength only returns the length of the longest common subsequence, rather than the subsequence itself. The answer to "the longest common subsequence" may be non-unique -- there may be two or more different common subsequences of the same length, as for example between the strings "abc" and "cba" -- but it would be nice to get one of them. Write an lcs function that takes two strings, and returns (one of) their longest common subsequence(s). For full credit, it should use the memoization technique for efficiency.

Infinite game trees

See Problem 3 of Dr. Krishnamurthi's Haskell assignment.
Note: Dr. K. provides an infrastructure program, Game.hs, and a "stub" student program, Laziness.hs. The latter won't compile because it's intentionally incomplete; you have to fill it in. The former should compile, but if you get compiler error messages, look at about line 8 of the file and replace Control.Exception with Control.OldException.

You can put the first three problems in one big file, say HW4.hs, or in three separate files Primes.hs, Fibonacci.hs, and LCS.hs. I recommend building your solution to the game-tree problem on the given Laziness.hs.

In either case, I want to see test cases and expected right answers for every function, just as if you were programming in Scheme or Java. Since we don't have an equivalent of check-expect for Haskell, just put this stuff in a text file.