[SOLVED] Scala, OCaml, Haskell, Elm

Assignment 3

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 namedproblem-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 isInt -> Int -> Int. The arrow is right associative, so you can read that asInt -> (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 ofa
• last : [a] -> a last returns the last element of a list, its type signature is exactly the same as that ofhead.
• permutations : [a] -> [[a]] a function that takes a list ofas and returns a list of all permutations of[a]
• map : (a -> b) -> [a] -> [b] map takes a function fromatob, a list ofas, and returns ab. 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 wrotea -> b -> [a] -> [b], we would be talking about a function that takes ana, and returns a function that takes ab, 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, andaandbare type variables. We will use lowercase letters to denote type variables (which can stand for any type), such asa,b,f, and uppercase characters to denote concrete types, likeInt,String,[Double].

Scala skeleton and helper functions for Assignment 3

Hi everyone,

Here is the Scala version of the skeleton:

https://gist.github.com/migimunz/105e5a1e3ddafd0f73d2f95a06687e05

This piece of code depends on parser combinators, so please add the following to your build.sbt:

libraryDependencies += org.scala-lang.modules %% scala-parser-combinators % 1.1.0

To make things easier if you have trouble importing, make your Main file be in package Base as well.

Functionsprovided:

• parseList[T](s: String): Option[List[T]]
• parseRope[T](s: String): Option[Rope[T]]
• print(x: T): String // where T can be Boolean, Char, Int, String, List[T], Rope[T]

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:Your input will be two lists of lists, the first will contain ints, the second strings.The listscontaining ints should be transformed using indirectMap into a list of lists of doubled integers as described in the example above. The lists 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:

(list (list 1 2 3) (list 4 5 6))

(list (list foo bar baz) (list abc bcd dca))

Output:

(list (list 2 4 6) (list 8 1 12))

(list (list oof rab zab) (list cba dcb acd))

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 four lists. The first two are to be zipped together, and the third and fourth to be zipped together.

Example input:

(list 1 2 3 4)

(list foo bar baz)

(list bob alice lisa)

(list true false true true)

Output:

(list 1 foo 2 bar 3 baz)

(list bob true alice false lisa true)

Note that a list of tuples (eg. [(Int, String)]) will automatically be formatted correctly when you call toString list

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, -2, 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:Your input will be a list of strings and a list of ints.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:

(list bob alice tom)

(list 1 2 5)

Output:

(list b o b a l i c e t o m)

(list 1 1 1 1 2 1 1 2 3 5 8)

PROBLEMS 47

PROBLEMS 47 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 47, 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:concatandlist, 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:

(+ (list 10 8) (+ (list 4 4) (list 0 4)))

(+ (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)whereAis the type of a key andBis 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 typeCto a list ofDs. Finally, thereducer 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.
Googles 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