This is an old revision of the document!
This version is preliminary and subject to change until this line is removed
For this lab, you will need to implement the following functions and data structures in Haskell:
-- Type Signature isPrime :: Integer -> Bool
IsPrime takes integer n and returns true if n is prime, false otherwise.
You can test to see if a number is prime by testing for divisibility by integers greater than one and less than or equal to the square root of the number being tested.
Hints:
-- Type Signature primes :: [Integer]
Create an infinite list of all primes and name it primes.
Useful Functions
filter :: (a -> Bool) -> [a] -> [a] isPrime :: Integer -> Bool
-- Type Signature isPrimeFast :: Integer -> bool
Takes an integer n and returns true if n is prime. Only test prime factors from the primesFast.
-- Type Signature primesFast :: [Integer]
Create an infinite list of all primes and name it primesFast. Must be constructed with isPrimeFast.
-- Type Signature lcs_length :: [a] -> [a] -> Integer
Computes the length of the longest common subsequence of two lists s1 and s1. Strings in Haskell are lists of characters.
You must construct an array of the answers for sub-problems made from prefixes of s1 and s2 then synthesize the result from these intermediate points. You will not get credit if you do a computation twice. (In other words, don't do it recursively – use the table form instead.)
Warning: Many people erroneously implement the longest common substring. The longest common substring of Artist and Artsy is Art. The longest common subsequence of Artist and Artsy is Arts. You are implementing longest common subsequence.