This is an old revision of the document!
This version is preliminary and subject to change until this line is removed
Objective:
Deliverable:
For this lab, you will need to implement the following functions and data structures in Haskell:
Part 1: Primes
isPrime
-- Type Signature isPrime :: Integer -> Bool
IsPrime takes integer n and returns true if n is prime, false otherwise.
primes
-- 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
isPrimeFast
-- Type Signature isPrimeFast :: Integer -> bool
Takes an integer n and returns true if n is prime. Only test prime factors from primesFast.
primesFast
-- Type Signature primesFast :: [Integer]
Create an infinite list of all primes and name it primesFast. Must be constructed with isPrimeFast.
Part 2: Longest Common Sub-sequence
lcs_length
-- 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.
Hints:
