Differences

This shows you the differences between two versions of the page.

--- cs330_f2016:lab15 [2016/11/08 17:27]
wingated created
+++ cs330_f2016:lab15 [2021/06/30 23:42] (current)
@@ Line 1: / Line 1: @@
 ====Objective:====
+To better understand programming using lazy evaluation.
 ----
-====Deliverable:====
+====Preparation:====
-For this lab, you will need to implement the following functions and data structures in Haskell:
+Download and install the GHC compiler and GHCI from https://www.haskell.org/downloads.
-===Part 1: Utility Functions===
+Note: the "minimal" install includes the GHC compiler but not the GHCI interactive portion.
-==Take_while==
+Make sure to download and install the full or "Haskell Platform" version.
-<code haskell>
--- Type Signature
-take_while :: (a -> Bool) -> [a] ->[a]
--- Function Call
+----
-take_while p l
+====Deliverables:====
--- Examples
+For this lab, you will need to implement the following functions and data structures in Haskell:
-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]
-</code>
-Returns the prefix of l such that for all elements p returns true. This is not filter.
-==build_infinite_list==
-<code haskell>
--- Type Signature
-build_infinite_list:: (Integer -> a) -> [a]
--- Function Call
-build_infinite_list f
--- Examples
-(build_infinite_list (*2)) = [2,4,6,8,...]
-</code>
-Lazily constructs an infinite list such that list!!i returns (f i).
-===Part 2: Primes===
+===Part 1: Primes===
 ==isPrime==
 <code haskell>
 -- Type Signature
-isPrime:: Integer -> Bool
+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. 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.
 ==primes==
 <code haskell>
 -- Type Signature
-primes:: [Integer]
+primes :: [Int]
 </code>
 Create an infinite list of all primes and name it primes.
@@ Line 52: / Line 37: @@
 <code haskell>
 filter :: (a -> Bool) -> [a] -> [a]
-isPrime :: Integer -> Bool
+isPrime :: Int -> Bool
-build_infinite_list :: (Integer -> a) -> [a]
 </code>
@@ Line 59: / Line 43: @@
 <code haskell>
 -- Type Signature
-isPrimeFast :: Integer -> bool
+isPrimeFast :: Int -> Bool
 </code>
-Takes an integer n and returns true if n is prime. **Only test prime factors from primesFast.**
+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.**
 ==primesFast==
 <code haskell>
 -- Type Signature
-primesFast :: [Integer]
+primesFast :: [Int]
 </code>
-Create an infinite list of all primes and name it primesFast. **Must be constructed with isPrimeFast.**
+Create an infinite list of all primes and name it primesFast.
+**Must be constructed with isPrimeFast.**
-===Part 3: Longest Common Sub-sequence===
+Note that the function isPrimeFast uses the list primesFast, and the list primesFast is generated using the function isPrimeFast.
-==build-table==
+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
-build_table :: Integer -> Integer -> (Integer -> Integer -> a) -> [[a]]
+lcsLength :: String -> String -> Int
 </code>
-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).
+Computes the length of the longest common subsequence of two strings s1 and s1.
+Strings in Haskell are lists of characters.
-==lcs_length==
+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.)
-<code haskell>
--- Type Signature
-lcs_length :: [a] -> [a] -> Integer
-</code>
-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.
+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:===
+----
+====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

Differences

Page Tools