cs330_f2016:labx
Differences
This shows you the differences between two versions of the page.
|
cs330_f2016:labx [2016/06/21 22:33] dcostello |
cs330_f2016:labx [2021/06/30 23:42] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====Objective:==== | ||
| - | ---- | ||
| - | ====Deliverable:==== | ||
| - | |||
| - | For this lab, you will need to implement the following functions and data structures in Haskell: | ||
| - | |||
| - | ===Part 1: Utility Functions=== | ||
| - | ==Take_while== | ||
| - | <code 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] | ||
| - | </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=== | ||
| - | ==isPrime== | ||
| - | <code haskell> | ||
| - | -- Type Signature | ||
| - | isPrime:: Integer -> Bool | ||
| - | </code> | ||
| - | IsPrime takes integer n and returns true if n is prime, false otherwise. | ||
| - | |||
| - | ==primes== | ||
| - | <code haskell> | ||
| - | -- Type Signature | ||
| - | primes:: [Integer] | ||
| - | </code> | ||
| - | Create an infinite list of all primes and name it primes. | ||
| - | |||
| - | Useful Functions | ||
| - | <code haskell> | ||
| - | filter :: (a -> Bool) -> [a] -> [a] | ||
| - | isPrime :: Integer -> Bool | ||
| - | build_infinite_list :: (Integer -> a) -> [a] | ||
| - | </code> | ||
| - | |||
| - | ==isPrimeFast== | ||
| - | <code haskell> | ||
| - | -- Type Signature | ||
| - | isPrimeFast :: Integer -> bool | ||
| - | </code> | ||
| - | Takes an integer n and returns true if n is prime. **Only test prime factors from primesFast.** | ||
| - | |||
| - | ==primesFast== | ||
| - | <code haskell> | ||
| - | -- Type Signature | ||
| - | primesFast :: [Integer] | ||
| - | </code> | ||
| - | Create an infinite list of all primes and name it primesFast. **Must be constructed with isPrimeFast.** | ||
| - | |||
| - | ===Part 3: Longest Common Sub-sequence=== | ||
| - | ==build-table== | ||
| - | <code haskell> | ||
| - | -- Type Signature | ||
| - | build_table :: Integer -> Integer -> (Integer -> Integer -> a) -> [[a]] | ||
| - | </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). | ||
| - | |||
| - | ==lcs_length== | ||
| - | <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. | ||
| - | |||
| - | 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:=== | ||
cs330_f2016/labx.txt ยท Last modified: 2021/06/30 23:42 (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
