Assignment Thre
Pick a language from the following list to use for this assignment: Scala, OCaml, Haskell, Elm
Solve the following problems in that language, subject to the following restrictions: you cannot use assignment, mutable data structures, loops, or (unless explicitly allowed by the stated problem) explicit recursion. The intent is for you to practice pure functional programming and to gain experience using standard functional tools like map and fold.
To aid grading, each problem will have two parts: the first part states a function or set of functions for you to define, and the second part states a particular task for you to implement using the function(s) you have defined. This second part will involve reading from standard input in a specified format, and should print to standard output in a specified format. Failure to use the appropriate formats will significantly affect the grading of this assignment.
Each problem should be solved in a separate file named problem-1.<ext>, problem-2.<ext>, etc, where <ext> is an appropriate extension for the chosen language (*.scala, *.ml, *.hs, *.scm, etc).
Type signatures
The problems below describe functions you need to implement with words, but it is crucial that you get familiar with reading type signatures and understand what they mean.
One of the important concepts in functional programming is currying, or treating all functions as 1-ary functions (functions with a single parameter) that return other functions. In other words, a function like addition, that takes two integers and returns an integer, can be viewed as a function that takes an integer, and returns a function that takes another integer, and returns an integer. The notation is Int -> Int -> Int. The arrow is right associative, so you can read that as Int -> (Int -> Int). Here are a few more examples:
- head : [a] -> a– head is a function that returns the first element of a list. [a] is the type of list of a
- last : [a] -> a– last returns the last element of a list, its type signature is exactly the same as that of head.
- permutations : [a] -> [[a]]– a function that takes a list of as and returns a list of all permutations of [a]
- map : (a -> b) -> [a] -> [b]– map takes a function from a to b, a list of as, and returns a b. Note that this is a higher order function, it takes another function as its first parameter. Also note the parenthesis around the argument type, if we wrote a -> b -> [a] -> [b], we would be talking about a function that takes an a, and returns a function that takes a b, and returns a function that takes [a], and so on.
The functions types you saw so far are of generic functions – they work for any concrete types, and a and b are type variables. We will use lowercase letters to denote type variables (which can stand for any type), such as a, b, f, and uppercase characters to denote concrete types, like Int, String, [Double].
PROBLEM 1 (2pts)
Define a generic function ‘indirectMap’ with the following type signature: (A -> B) -> [[A]] -> [[B]]. In other words, indirectMap takes a function that transforms As into Bs (which for convenience we will call ‘f’), and then returns a function that takes a list of lists of As and returns a list of lists of Bs (using ‘f’ to transform the As into Bs).
Example: if we pass indirectMap a function that doubles integers, then pass the resulting function a list [[1, 2, 3], [4, 5, 6]], we should get [[2, 4, 6], [8, 10, 12]] as the final output.
Task: the input will be formatted as a series of lines each containing a sequence of integers separated by spaces, followed by an empty line, then a series of lines each containing a sequence of strings separated by spaces. The lines containing integers should be read into a list of lists of integers and that should be transformed using indirectMap into a list of lists of doubled integers as described in the example above. The lines containing strings should be read into a list of lists of strings and that should be transformed using indirectMap into a list of list of reversed strings. The output should mirror the input, except using the transformed values.
Example input:
1 2 3
4 5 6
foo bar baz
100 200 300
Output:
2 4 6
8 10 12
oof rab zab
001 002 003
PROBLEM 2 (2pts):
Define a generic function ‘zip’ with the following type signature: [A] -> [B] -> [(A,B)]. In other words, zip takes a list of As, and then returns a function that takes a list of Bs and returns a list of pairs containing the corresponding elements of the provided lists. If one list is longer than the other then the extra elements are ignored.
Example: given the list [1, 2, 3, 4] and the list [“alice”, “bob”, “charlie”], we should get the list [(1, “alice”), (2, “bob”), (3, “charlie”)] as the final output.
Note that some of the languages allowed for this assignment already provide a function with this specification (by various names). You are not allowed to use that provided function to solve this problem.
Task: Your program will take two pairs of lines, separated by an empty line. The first pair represents a list of integers and a list of strings. The second pair represents lists of strings and booleans. The output should be a line containing the zipped pairs of integers and strings, and a line containing the zipped pairs of strings and booleans.
Example input:
1 2 3 4
foo bar
bob alice lisa
true false true true
Output:
1 foo 2 bar
bob true alice false lisa true
PROBLEM 3 (3pts):
Define a generic function ‘flatMap’ with the following type signature: (A -> [B]) -> [A] -> [B]. In other words, flatMap takes a function (which for convenience we will refer as ‘f’) that transforms things of type A to lists of Bs, and then returns a function that takes a list of As and returns a list of Bs (using ‘f’ to transform the As into lists of Bs and then flattening the resulting lists into a single list).
Example: if we pass flatMap a function that transforms a string into a list of its individual characters, then pass the resulting function a list [“abc”, “def”], we should get the single list [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’] as the final output. If we pass flatMap a function that transforms an integer into a list containing that integer and its negation a list [1, 2, 3], we would expect to get [1, -1, 2, -3, 3, -3] as the output.
Note that some of the languages allowed for this assignment already provide a function with this specification (by various names). You are not allowed to use that provided function to solve this problem.
Task: the input will be formatted as a sequence of strings separated by spaces on the first line followed by a sequence of integers separated by spaces on the second line. You should use flatMap to transform the list of strings into lists of characters as described in the example above. You should use flatMap to transform the list of integers into a list of integers using a function ‘f’ that transforms an integer i into a list of integers that give the fibonacci sequence up to index i (e.g., f(0) = [1], f(1) = [1, 1], f(2) = [1, 1, 2], etc). The output should mirror the input, except using the transformed values.
Example input:
bob alice tom
1 2 5
Output:
‘b’ ‘o’ ‘b’ ‘a’ ‘l’ ‘i’ ‘c’ ‘e’ ‘t’ ‘o’ ‘m’
1 1 1 1 2 1 1 2 3 5 8
PROBLEMS 4–7
PROBLEMS 4–7 use the following definition of a data structure called a ‘rope’, which provides an alternate implementation of lists that allows for efficient list concatenation. A rope of things of type X is defined as either a data type ‘List X’ or a data type ‘Concat (Rope X) (Rope X)’. In other words, if you are given a rope you either have a list of Xs or you have two sub-ropes, which you should interpret as the first rope concatenated with the second rope. The type Rope can be defined as a union type (which are common in functional languages, though they are not present in languages like C++ or Java).
In each solution for Problems 4–7, define a Rope type to be used in that solution. All of the solutions will use the same type definition.
Input: Your input will be a number of lines containing s-expressions. The last empty line will indicate end of input. These expressions represent operations on lists. An s-expression is a sequence of expressions separated by spaces, inside parentheses. For example, (+ 2 5) is an s-expression, and can be read as “add 2 and 5”. In this notation, the operation is the first element, and the arguments are all following elements until the closing parenthesis. Arguments can be other s-expressions as well, so (+ (+ 3 4) (- 5 2)) is an s-expression that can be evaluated to 10.
The inputs to your program will be s-expressions with only two operations: concat and list, which concatenate two lists, and create a list out its arguments respectively. Your program will turn these into the appropriate rope structure. For example:
(+ (list 7 8) (+ (1 2 3) (4 5 6))) maps to a rope that looks like this: Cons(List(7, 8), Cons(List(1, 2, 3), List(4, 5, 6))).
Output:
Your output will also be an s-expression, denoting the new rope returned by the function your solution implemented. Examples will be provided with every problem definition.
PROBLEM 4 (2PT):
Define a generic function ‘mapRope’ that implements the standard map functionality on lists, except for ropes instead. Your program will take two ropes: A rope of ints, and a rope of strings. The rope of ints will be transformed by a function that doubles numbers, and the rope of strings by a function that reverses strings.
Input example:
(+ (list 5 4) (+ (list 2 2) (list 0 2)))
(+ (list foo bar) (list baz zab))
Output:
(cons (list 10 8) (cons (list 4 4) (list 0 4)))
(cons (list oof rab) (list zab baz))
PROBLEM 5 (4pts)
Define a generic function ‘foldRope’ that implements the standard fold functionality on lists, except for ropes instead.
Task: Your program will take a rope of integers and fold it by appending them all to a string.
Input example:
(+ (list 2 3) (+ (list 1) (list 4 5)))
Output:
“23145”
PROBLEM 6 (2pts):
Define a generic function ‘ropeLength’ that returns the number of elements contained in a rope.
Bonus point: Implement ropeLength using only foldRope.
Task: Your program will take a rope of ints as input, and simply print its length, that being the length of all the inner lists appended together.
Input example:
(+ (list 2 3) (+ (list 1) (list 4 5)))
Output
5
PROBLEM 7 (3pts):
Define a generic function ‘ropeToList’ that takes a rope and returns a standard list containing the elements of the rope.
Task: Your program will take a single rope as input, and print a single list as output.
Example input:
(+ (list 2 3) (+ (list 1) (list 4 5)))
Output:
(list 2 3 1 4 5)
PROBLEM 8 (4pts):
Define a generic function ‘mapReduce’ with the following type signature: ((A, B) -> (C, D)) -> ((C, [D]) -> (C, D)) -> [(A, B)] -> [(C, D)].
This is the famous “MapReduce” framework developed at Google for distributed computation. Users provide two functions, a “mapper” (i.e., the (A, B) -> (C, D) argument) and a “reducer” (i.e., the (C, [D]) -> (C, D) argument). The data provided to the framework are key/value pairs (i.e., (A, B) where A is the type of a key and B is the type of a value). MapReduce applies the mapper to each key/value pair (A, B) to get a new list of key/value pairs [(C, D)]. The framework then groups all resulting key/value pairs that have the same key value, resulting in a set of pairs (C, [D]) mapping each key of type C to a list of Ds. Finally, the mapper takes a (C, [D]) pair, i.e., a key and a list of associated values, and reduces it into a (C, D) pair, i.e., a key and a single value computed from the list of values.
Google’s implementation of MapReduce actually distributes these operations onto multiple cores and provides load balancing, fault tolerance, and addresses other system issues that we are going to ignore. We are only going to implement the core functionality as described above.
Your program will implemente the generic mapReduce function, then apply it to the problem of finding the frequency of words in sentences. The input will be a a list of words separated by spaces. Your program will count the occurence of each word in the input sentence, and output each word,
Note: You must implement the generic version of mapReduce, then apply it to counting words by providing two functions, f and g. f will turn each word into a (String, Int) tuple, which your mapReduce function will group as (String, [Int]), a list of ints for each string. The second function g will then reduce those pairs into (String, Int), where the first element is the word, and the second element the number of times that word appeared in the input sentence.
Examples:
Input: Tom jumped over a red dog with a red scarf
Output:
Tom: 1
jumped: 1
over: 1
a: 2
red: 2
dog: 1
with: 1
scarf: 1
Input: train bus car bus bus car train bus
Output:
train: 2
bus: 4
car: 2