c++

you are asked to implement map, lter and reduce using C++. If you know some functional programming languages, you should have heard of these three names. We will describe the ideas in the following sessions.

When we use programming to solve tasks, often, we need to deal with lists of stus. For example, databases are essentially lists of data entries and strings are basically lists of characters. map, lter and reduce allow convenient modication and aggregation of lists.

2.3.1 map Firstly, let just look at the concept of map. Mathematically, given a list L = [x1, x2, , xn] and a function f, by mapping f onto L, we get

map(f, L) = [f(x1), f(x2), , f(xn)]. map can be applied whenever we want to apply operations to every element of the list. For example, to convert a list of characters to upper cases, we just map toUpper function onto the list, where toUpper converts lower cases to upper cases. Given a list of books, if we want the corresponding list of authors, we just map getAuthor function onto the list, where getAuthor(book) returns the correct author. Given a list of game units, if we want to heal them all (e.g., a Mage casted an area of eect (AOE) healing ability), then we just map heal onto the list of game units. Now let us get back to C++. For simplicity, for this assignment, we only consider lists where the elements are integers, and we only consider functions that map integers to integers. Your implementation should at the very least provide the following functionalities: Given a list of integers, the resulting list has every value tripled. That is, [x1, x2, ..., xn] becomes [3x1, 3x2, ..., 3xn]. Given a list of integers, the resulting list has every value raised to the power of 2.

That is, [x1, x2, ..., xn] becomes [x2

1, x2

2, ..., x2

n].

Given a list of integers, the resulting list has every member become the absolute value. That is, [x1, x2, ..., xn] becomes [|x1|, |x2|, ..., |xn|]. In your implementation, you are required to use C++ standard vector or deque for storing the lists. One possible way to implement the above functionalities is as follows (feel free to use other methods such as functional pointers - the only requirement is that you use recursion): We can create a base class with name MapGeneric, which has a private method int f(int) that species the operation we want to map onto a list. This method is overridden later in the derived classes to deliver specic map operations. The function f can be declared to be pure virtual. The MapGeneric class also has a public method vector MapGeneric::map(vector) that takes a vector as the input and returns the resulting vector after mapping. You should use recursion to implement this map function. (You may use deque instead of vector.)

Three derived classes MapTriple, MapSquare and MapAbsoluteValue can be im-plemented and each one overrides the original f method according to dierent re-quirement. For example, MapTriple::f(x) should return 3x.

2.3.2 lter Mathematically, given a list L = [x1, x2, , xn] and a function g(x) that returns a boolean value, if we lter L based on g(x), we end up with only elements that pass the g(x)test. That is, if g(x1) = g(x3) = g(x4) = true and g(x2) = g(x5) = false, then

filter(g, L) = [x1, x3, x4]. lter can be applied whenever we want to select some elements from a list. For example, to lter out all digits from a list of characters, we just lter isDigit() on the list, where isDigit() determines whether a character is a digit or not. Given a list of books, if we want to search for books that are novels, we just lter isNovel() from the list, where isNovel() returns whether the book is a novel or not. Given a list of game units, if we want to heal only the allied units, then we lter isAllied and then map heal. Now let us get back to C++. For simplicity, for this assignment, the function used to lter elements only returns boolean. Your implementation should at the very least provide the following functionalities: Given a list of integers, lter out the even values. That is, [1, 2, 3, 4, 5, 6, 7] becomes [1, 3, 5, 7]. Given a list of integers, lter out the positive values:. That is, [1, 1, 2, 2, 4, 7] becomes [1, 2]. Given a list of integers, select all two-digit positive numbers. That is, [11, 1, 23, 4354, 1, 22, 4, 22] becomes [11, 23, 22]. In your implementation, you are required to use C++ standard vector or deque for storing the lists. One possible way to implement the above functionalities is as follows (feel free to use other methods such as functional pointers - the only requirement is that you use recursion): We can create a base class with name FilterGeneric, which has a private method bool g(int) that species the operation we want to map onto a list. This method is overridden later in the derived classes to deliver specic map operations. The function g can be declared to be pure virtual. The FilterGeneric class also has a public method vector FilterGeneric::filter(vector) that takes a vector as the input and returns the resulting vector after ltering. You should use recursion to implement this lter function. (You may use deque instead of vector.) Three derived classes FilterOdd, FilterNonPositive and FilterForTwoDigitPositive can be implemented and each one overrides the original g method according to dif-ferent requirement. For example, FilterOdd::g(x) should return true if and only if x is odd.

2.3.3 reduce Mathematically, given a list L = [x1, x2, , xn] and a binary operator , then

reduce( , L) = ((((x1 x2) x3) ...) xn).

For example, if is +, then reduce(+, L) is simply the sum of all xi with i = 1...n. if is , then reduce(, L) is simply the product of all xi with i = 1...n. if xi xj = max{xi, xj} is + which means the binary operator picks the larger operand as the result, then reduce( , L) is the maximum over the set L. if xi xj = xj, then reduce( , L) produces the last element of the list. reduce can be applied for aggregating results as evidenced above. (It should be noted that here we are talking about a simplied version of reduce, so it may not look too impressive.) Now let us get back to C++. For simplicity, for this assignment, we only consider lists where the elements are integers, and we only consider binary operators that take in two integer operands and produce one integer result. For simplicity, you may assume there is no list has less than 2 elements. Your implementation should at the very least provide the following functionalities: Given a list of integers, use reduce to nd out the minimum value. Given a list of positive integers, use reduce to nd out the greatest common de-nominator of all the integers in the list. In your implementation, you are required to use C++ standard vector or deque for storing the lists. One possible way to implement the above functionalities is as follows (feel free to use other methods such as functional pointers - the only requirement is that you use recursion): We can create a base class with name ReduceGeneric, which has a private method int binaryOperator(int, int) that species the operator. This method is over-ridden later in the derived classes to deliver specic map operations. The function binaryOperator can be declared to be pure virtual. The ReduceGeneric class also has a public method vector ReduceGeneric::reduce(vector) that takes a vector as the input and returns the result of reduce. You should use recursion to implement this reduce function. (You may use deque instead of vector.) Two derived classes ReduceMinimum and ReduceGCD can be implemented and each one overrides the original binaryOperator method according to dierent require-ment. For example, ReduceMinimum::binaryOperator(x,y) should return the smaller value between x and y.

2.4 Testing Then in your main function, Construct a vector/deque using these 20 integers. We denote the list by L = [x1, x2, ..., x20]. Convert the original list L to L = [3|x1|, 3|x2|, ..., 3|xn|] using map (hint: map twice). From L , select all positive two digit integers that are also odd (hint: lter twice). Let the resulting list be L . Compute the minimum value and the greatest common denominator of L (using reduce). Output the results, separated by space (output should be min gcd). Sample input: 6, -11, 53, -16, 73, 128, 105, 104, -71, -179, 102, 12, 21, -145, -99, 199, -156, -186, 43, -189 Sample output: 33 3 For your reference, L = [18, 33, 159, 48, 219, 384, 315, 312, 213, 537, 306, 36, 63, 435, 297, 597, 468, 558, 129, 567], L = [33, 63]. Sample input: -5, -24, -123, -81, 200, 157, 84, 67, -83, -60, -72, 192, -25, -20, -50, -181, -70, -15, -108, -123 Sample output: 15 15 For your reference, L = [15, 72, 369, 243, 600, 471, 252, 201, 249, 180, 216, 576, 75, 60, 150, 543, 210, 45, 324, 369], L = [15, 75, 45].