To better understand programming using lazy evaluation.
Download and install the GHC compiler and GHCI from https://www.haskell.org/downloads.
Note: the “minimal” install includes the GHC compiler but not the GHCI interactive portion. Make sure to download and install the full or “Haskell Platform” version.
For this lab, you will need to implement the following functions and data structures in Haskell:
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. For convenience, the function
ISqrt, which computes this largest integer less than the square root of n, has been provided for you below in the Hints section.
-- Type Signature primes :: [Int]
Create an infinite list of all primes and name it primes.
Takes an integer n and returns true if n is prime. Unlike isPrime, which tests for divisibility by all integers between 2 and the square root of n, it tests for divisibility using only prime numbers in this range. Only test prime factors from the primesFast list.
-- Type Signature primesFast :: [Int]
Create an infinite list of all primes and name it primesFast. Must be constructed with isPrimeFast.
Note that the function isPrimeFast uses the list primesFast, and the list primesFast is generated using the function isPrimeFast. This is the beauty of lazy evaluation – you can use earlier parts of the list to generate the later parts of the list. Just don't get ahead of yourself!
Computes the length of the longest common subsequence of two strings 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.)
Here is a link to a description on Wikipedia of how the table-based algorithm works: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
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.
iSqrt :: Int-> Int iSqrt n = floor(sqrt(fromIntegral n))