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/24 01:02] morse [Resources:] |
cs330_f2016:lab15 [2021/06/30 23:42] (current) |
||
|---|---|---|---|
| Line 25: | Line 25: | ||
| 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== | ||
| Line 43: | Line 43: | ||
| <code haskell> | <code haskell> | ||
| -- Type Signature | -- Type Signature | ||
| - | isPrimeFast :: Int -> 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 80: | Line 81: | ||
| * 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.) | ||
| * 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>. | * 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. See the Haskell documentation for how to do this. | + | * 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> | ||
| ---- | ---- | ||
| Line 91: | Line 99: | ||
| * http://book.realworldhaskell.org/read | * http://book.realworldhaskell.org/read | ||
| * http://learnyouahaskell.com | * http://learnyouahaskell.com | ||
| + | * https://learnxinyminutes.com/docs/haskell/ | ||
cs330_f2016/lab15.1479949364.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
