BYU CS classes

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====Objective:====

To better understand programming using lazy evaluation.

----
====Preparation:====

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.

----
====Deliverables:====

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

===Part 1: Primes===
==isPrime==
<code haskell>
-- Type Signature
isPrime :: Int -> Bool
</code>
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. 

==primes==
<code haskell>
-- Type Signature
primes :: [Int]
</code>
Create an infinite list of all primes and name it primes.

Useful Functions
<code haskell>
filter :: (a -> Bool) -> [a] -> [a]
isPrime :: Int -> Bool
</code>

==isPrimeFast==
<code haskell>
-- Type Signature
isPrimeFast :: Int -> Bool
</code>
Takes an integer n and returns true if n is prime.
**Only test prime factors from the primesFast list.**

==primesFast==
<code haskell>
-- Type Signature
primesFast :: [Int]
</code>
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!

===Part 2: Longest Common Subsequence===
==lcsLength==
<code haskell>
-- Type Signature
lcsLength :: String -> String -> Int
</code>
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.

----
====Hints:====
  * Use mod to test for divisibility.
  * Consider using infinite lists (e.g., [2..]), higher-order functions, and list comprehension.
  * You may find the takeWhile function to be useful.
  * To help you debug isPrimesFast, consider using the primes list (not the primesFast list).
  * Although it is not required, the functions isPrime and isPrimeFast can each be written with a single line of code.  Can you figure out how?  (If not, a more brute-force recursive implementation will work as well.)
  * Since isPrimeFast uses the list primesFast, and primesFast is generated using isPrimeFast, you have to seed it by explicitly including that 2 is a prime number.  This can be done as a special case of isPrimeFast or by starting the primesFast list as 2:<the rest of your code to generate it>.
  * For the lcsLength function, you will need to use an array rather than lists so that you can have random access into the table.  Here is a tutorial on Haskell arrays for how to do this:https://www.haskell.org/tutorial/arrays.html.  In particular, pay attention to the "wavefront" example.
  * To access an element of a string, use the "!!" operator.  For example, s1!!j returns the jth element of the string s1 (using zero-based indexing).
  * Here's some code for a simple function that returns the largest Int value smaller than the square root of another Int.  It's pretty straightforward, but it does involve some type conversions that we want to spare you from having to figure out.
<code>
iSqrt :: Int-> Int
iSqrt n = floor(sqrt(fromIntegral n))
</code>

----
====Resources:====
  * https://www.haskell.org
  * https://wiki.haskell.org/Tutorials
  * http://book.realworldhaskell.org/read
  * http://learnyouahaskell.com
  * https://learnxinyminutes.com/docs/haskell/
BYU CS classes

User Tools

Site Tools

Page Tools
