cs330_f2016:lab15
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
cs330_f2016:lab15 [2016/11/22 05:02] morse |
cs330_f2016:lab15 [2021/06/30 23:42] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ** This version is basically final in terms of the deliverables, but we may add more to help you write the code. ** | ||
| - | |||
| ====Objective:==== | ====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. | ||
| ---- | ---- | ||
| - | ====Deliverable:==== | + | ====Deliverables:==== |
| For this lab, you will need to implement the following functions and data structures in Haskell: | For this lab, you will need to implement the following functions and data structures in Haskell: | ||
| Line 13: | Line 21: | ||
| <code haskell> | <code haskell> | ||
| -- Type Signature | -- Type Signature | ||
| - | isPrime :: Integer -> Bool | + | isPrime :: Int -> Bool |
| </code> | </code> | ||
| IsPrime takes integer n and returns true if n is prime, false otherwise. | 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. | + | 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== | ==primes== | ||
| <code haskell> | <code haskell> | ||
| -- Type Signature | -- Type Signature | ||
| - | primes :: [Integer] | + | primes :: [Int] |
| </code> | </code> | ||
| Create an infinite list of all primes and name it primes. | Create an infinite list of all primes and name it primes. | ||
| Line 29: | Line 37: | ||
| <code haskell> | <code haskell> | ||
| filter :: (a -> Bool) -> [a] -> [a] | filter :: (a -> Bool) -> [a] -> [a] | ||
| - | isPrime :: Integer -> Bool | + | isPrime :: Int -> Bool |
| </code> | </code> | ||
| Line 35: | Line 43: | ||
| <code haskell> | <code haskell> | ||
| -- Type Signature | -- Type Signature | ||
| - | isPrimeFast :: Integer -> bool | + | isPrimeFast :: Int -> Bool |
| </code> | </code> | ||
| Takes an integer n and returns true if n is prime. | 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.** | **Only test prime factors from the primesFast list.** | ||
| Line 43: | Line 52: | ||
| <code haskell> | <code haskell> | ||
| -- Type Signature | -- Type Signature | ||
| - | primesFast :: [Integer] | + | primesFast :: [Int] |
| </code> | </code> | ||
| Create an infinite list of all primes and name it primesFast. | Create an infinite list of all primes and name it primesFast. | ||
| Line 56: | Line 65: | ||
| <code haskell> | <code haskell> | ||
| -- Type Signature | -- Type Signature | ||
| - | lcsLength :: String -> String -> Integer | + | lcsLength :: String -> String -> Int |
| </code> | </code> | ||
| Computes the length of the longest common subsequence of two strings s1 and s1. | Computes the length of the longest common subsequence of two strings s1 and s1. | ||
| Line 68: | Line 77: | ||
| 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. | 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. | * Use mod to test for divisibility. | ||
| * Consider using infinite lists (e.g., [2..]), higher-order functions, and list comprehension. | * 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.) | * 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.) | ||
| - | * For the lcsLength function, you will need to use an array rather than lists so that you can have random access into the table. See the Haskell documentation for how to do this. | + | * 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). | * 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/ | ||
cs330_f2016/lab15.1479790938.txt.gz · Last modified: 2021/06/30 23:40 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
