BYU CS classes

For this lab, you will need to implement the following functions and data structures in Haskell:

-- Type Signature
take_while :: (a -> Bool) -> [a] ->[a]
 
-- Function Call
take_while p l
 
-- Examples
take_while odd [1, 3, 5, 7, 8, 9] = [1,3,5,7]
take_while (\x -> (x < 5)) [1,2,3,4,5,1,2] = [1,2,3,4]

Returns the prefix of l such that for all elements p returns true. This is not filter.

-- Type Signature
build_infinite_list:: (Integer -> a) -> [a]
 
-- Function Call
build_infinite_list f
 
-- Examples
(build_infinite_list (*2)) = [2,4,6,8,...]

Lazily constructs an infinite list such that list!!i returns (f i).

-- Type Signature
isPrime:: Integer -> Bool

IsPrime takes integer n and returns true if n is prime, false otherwise.

-- 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
build_infinite_list :: (Integer -> a) -> [a]

-- Type Signature
isPrimeFast :: Integer -> bool

Takes an integer n and returns true if n is prime. Only test prime factors from primesFast.

-- Type Signature
primesFast :: [Integer]

Create an infinite list of all primes and name it primesFast. Must be constructed with isPrimeFast.

-- Type Signature
build_table :: Integer -> Integer -> (Integer -> Integer -> a) -> [[a]]

Takes two integers, h and w, and a function f, and lazily constructs a table of size h by w, so the value at any position i,j equals (f i j).

-- Type Signature
lcs_length :: [a] -> [a] -> Integer

Computes the length of the longest common sub sequence of two lists s1 and s1. Strings in Haskell are lists of characters.

You must use build-table to construct a table of the answer for sub-problem 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.

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.