In this = + we will play with polynomials. We represent a polynomial anx² + an−1x^−1 +a2x²+a1x+ao in HASKELL as a list of pairs (a;, i), 0 ≤ i ≤ n. Whenever a; 0 the respective pair will not be present in the list. Note that the list representation of a polynomial is not necessarily sorted in any way. You may take () (the empty list) to be a representation of the identity element for polynomial addition. We refer henceforth to this representation of polynomials as the coefficient-index list. For example the polynomial 2x³ + 6x² + 3x + 4 may be represented by several coefficient-index lists including [(2,3), (6,2), (3,1), (4,0)] and [(4,0), (3,1), (6,2), (2,3)] (and for that matter everything in between). The polynomial 2x³ +3x may be represented by either [(3,1), (2,3)] or [(2,3), (3,1)]. It turns out that a different representation of polynomials is much more convenient for operating on them in HASKELL. We call this implementation the full coefficient list. The full coefficient list of a polynomial anx¹ + an−1xn−1 + ··· + a2x² + a1x + a0 is the list [a0, a1, ..., an] of all the coefficients (including null coefficients) sorted in increasing order of their index. We start the assignment by providing conversion functions between the two representations of polynomials. For this purpose: 1. Modify the Quicksort implementation presented in class so that it sorts lists of pairs (a,i) with respect to the second component i, thus obtaining the function polySort. 2. Define a function polyExpand that adds the missing (null) coefficients to a polynomial. You can assume that the polynomial is already sorted in increasing order of its coefficients. For example polyExpand [(3.0,1), (2.0,3)] should evaluate to [(0.0,0), (3.0,1), (0.0,2), (2.0,3)]. 3. Use a map to define a function polyList that receives the output of polyExpand and drops the indices, thus obtaining the full coefficient list representation of the polynomial. For example: polyList [(0.0,0), (3.0,1), (0.0,2), (2.0,3)] should evaluate to [0.0,3.0,0.0,2.0]. 4. Put all the functions above together to define the function polyConvert that receives the coefficient-index list representation of a polynomial and evaluates to the full coefficient list representation of that polynomial. For example:

In this = + we will play with polynomials. We represent a polynomial anx² + an−1x^−1 +a2x²+a1x+ao in HASKELL as a list of pairs (a;, i), 0 ≤ i ≤ n. Whenever a; 0 the respective pair will not be present in the list. Note that the list representation of a polynomial is not necessarily sorted in any way. You may take () (the empty list) to be a representation of the identity element for polynomial addition. We refer henceforth to this representation of polynomials as the coefficient-index list. For example the polynomial 2x³ + 6x² + 3x + 4 may be represented by several coefficient-index lists including [(2,3), (6,2), (3,1), (4,0)] and [(4,0), (3,1), (6,2), (2,3)] (and for that matter everything in between). The polynomial 2x³ +3x may be represented by either [(3,1), (2,3)] or [(2,3), (3,1)]. It turns out that a different representation of polynomials is much more convenient for operating on them in HASKELL. We call this implementation the full coefficient list. The full coefficient list of a polynomial anx¹ + an−1xn−1 + ··· + a2x² + a1x + a0 is the list [a0, a1, ..., an] of all the coefficients (including null coefficients) sorted in increasing order of their index. We start the assignment by providing conversion functions between the two representations of polynomials. For this purpose: 1. Modify the Quicksort implementation presented in class so that it sorts lists of pairs (a,i) with respect to the second component i, thus obtaining the function polySort. 2. Define a function polyExpand that adds the missing (null) coefficients to a polynomial. You can assume that the polynomial is already sorted in increasing order of its coefficients. For example polyExpand [(3.0,1), (2.0,3)] should evaluate to [(0.0,0), (3.0,1), (0.0,2), (2.0,3)]. 3. Use a map to define a function polyList that receives the output of polyExpand and drops the indices, thus obtaining the full coefficient list representation of the polynomial. For example: polyList [(0.0,0), (3.0,1), (0.0,2), (2.0,3)] should evaluate to [0.0,3.0,0.0,2.0]. 4. Put all the functions above together to define the function polyConvert that receives the coefficient-index list representation of a polynomial and evaluates to the full coefficient list representation of that polynomial. For example: