For this assignment you'll implement a handful of functions using the basic
recursive patterns discussed in class. For each exercise, we indicate the
pre-existing Haskell library functions you're permitted to use in your
implementation. You may use any language construct --- e.g., pattern matching,
where clauses, etc., covered so
far. Type definitions have also been provided for you; don't change these.
All your code for this assignment should go into a file named "MP1.hs" within
src/mps" directory in your repository.
Each exercise is worth 3 points. A correct implementation that adheres to the rules will receive full credit. A partially correct implementation (that compiles!) will receive 1-2 points. An implementation that breaks the rules (e.g., uses prohibited functions) or doesn't compile will receive no points.
cycleN :: Int -> [a] -> [a]
Write a function that takes a number
n and a list
l and return a list
containing the elements of
> cycleN 0 [1..10]  > cycleN 5 "hello" "hellohellohellohellohello"
countLessThan :: (Ord a) => a -> [a] -> Int
Write a function that takes a value and a list and returns the number of items in the list less than the provided value.
> countLessThan 10 [0..20] 10 > countLessThan 'g' "supercalifragilisticexpialidocious" 10
removeAll :: (Eq a) => [a] -> [a] -> [a]
Write a function that takes two lists and returns a list containing only those elements in the second list that do not appear in the first.
> removeAll [1..3] [0..10] [0,4,5,6,7,8,9,10] > removeAll "aeiou" "supercalifragilisticexpialidocious" "sprclfrglstcxpldcs"
join :: a -> [[a]] -> [a]
Write a function that joins lists together using a separator value --- the separator should only appear between elements, and not at the end.
> join '-' ["hello", "how", "are", "you"] "hello-how-are-you" > join 0 [, [2,3]] [1,0,2,3]
unzip' :: [(a,b)] -> ([a], [b])
Write a function that takes a list of two-tuples and returns a tuple of two
lists -- the first containing the first element of each tuple, and the
second the second element (the reverse of "
> unzip' [('a',1),('b',5),('c',8)] ("abc",[1,5,8])
runLengthEncode :: String -> [(Int,Char)]
Run-length encoding is a simple form of data compression that replaces characters in a stream with the count of adjacent occurrences of that character and just a single instance of the character itself. Write a function that takes a string and returns a list of tuples reprenting the run-length encoding of that string.
> runLengthEncode "aaaaaaabbb" [(7,'a'),(3,'b')] > runLengthEncode "happy daaay" [(1,'h'),(1,'a'),(2,'p'),(1,'y'),(1,' '),(1,'d'),(3,'a'),(1,'y')]
runLengthDecode :: [(Int,Char)] -> String
Write a function that takes the output of
runLengthEncode and returns the
> runLengthDecode [(1,'h'), (5,'i')] "hiiiii" > runLengthDecode $ runLengthEncode "whhhhaaaaat?" "whhhhaaaaat?"
vigenere :: String -> String -> String
The Vigenere encryption scheme is similar to the Caesar cipher presented in class in that it makes use of shifting, but instead of a single numeric key applied uniformly to the entire plain text, a string of characters is used as the key. The numeric value of each character (as its position in the alphabet) is used as a shift value, and if the key is shorter than the length of the plain text it is simply repeated.
E.g., to encrypt the plain text "FOOBAR" with the key "BAZ", we can proceed as follows:
Pair each letter of the plain text with a letter from the key:
F O O B A R B A Z B A Z
Convert each letter to its numeric value (A=0, B=1 ... Z=25)
5 14 14 1 0 17 1 0 25 1 0 25
Add them together:
6 14 39 2 0 42
"Wrap" the numbers around so they're in the range 0-25:
6 14 13 2 0 16
Convert the numbers back into letters:
G O N C A Q
Write a function that takes a key and plain text and returns the Vigenere encrypted cipher text. Plain text can contain a mix of lowercase and uppercase letters and punctuation, but all letters will be interpreted as uppercase. Punctuation will not be encrypted. The key will contain only letters (lower or upper case), but again will only be interpreted as uppercase.
> vigenere "baz" "foobar" "GONCAQ" > vigenere "Yadda" "Hello, world!" "FEOOO, UOUOD!"
toUpper (to use the last four you'll need to
To submit your work, be sure your "
MP1.hs" file is added to your repository in
src/mps" subdirectory, then commit all your changes and push your work to
our shared BitBucket repository. We'll go over this in class.