CSE 505 - Autumn 2001 - Assignment 4

Due October 26, in class. As usual please turn this in on paper - cut and paste your programs and sample output.

Write and test a Haskell function
```
scale n s
```
that takes an integer n and a list of integers s, and returns a new list of integers. Each element of the result should be n times the corresponding element of s. (This question, like the next one, may be strangely familiar.)
Write and test a Haskell function
```
sublist s r
```
that returns true if s is a sublist of r, and false if not.
Write and test an interactive Haskell program that prompts the user for pairs of polynomials in x, multiplies them and prints the results. The two polynomials can be entered in any form that is convenient, but the output should be in prettyprinted form. For example:
```
polynomial #1: Poly [Term 1 3, Term 1 2, Term 1 1, Term 1 0]
polynomial #2: Poly [Term 1 1, Term -1 0]
result:  x^4 - 1

continue? y
polynomial #1: Poly [Term -3 3, Term 1 1, Term 5 0]
polynomial #2: Poly []
result: 0

continue? n
bye from polynomial multiplier
```
The above inputs represent polynomials as follows:
Poly [Term 1 3, Term 1 2, Term 1 1, Term 1 0]
represents the polynomial x^3 + x^2 + x + 1.
Poly [Term 1 1, Term -1 0]
represents x - 1
Poly []
represents 0.
Here are some polynomial pairs to test your function on:
```
x^3 + x^2 + x + 1
x - 1

-3*x^3 + x + 5
0

x^3 + x - 1
-5

- 10*x^2 + 100*x + 5
x^9999 - x^7 - x^5 + x + 3
```
You can change the format of the input strings or the interaction sequence if you prefer something different. Assume the input is syntactically correct.
Hints: represent a polynomial as a list of terms, where each term consists of a coefficient and an exponent. The list should be sorted by the size of the exponent. Don't include terms with a zero coefficient. If you define your polynomial type as a derived instance of Read and Show, then you will automatically get a read and show function. The input format shown above, for example, works with the derived read function for my polynomial datatype. My declaration for this type is:
```
data PolynomialType = Poly [TermType] deriving (Read,Show)
```
Naturally you'll need a declaration for TermType also.
First define your types, and make some test instances of those types. (They should show in the default format.) Then write the multiply function and test it, then write and test the prettyprint function, and finally put it all in an interactive program.
Make up, write, and test your own Haskell program that uses infinite data structures in an interesting way. (If you can't think of anything interesting, make up a program that uses them in an uninteresting way.) You can get full credit for a simple program, but if you feel inspired to do something more elaborate it'd be fun to see the result.
As an example of a satisfactory and simple program, you could define a function compound that calculates compound growth. The function takes a start year, a start amount, and a growth rate, and return an infinite list of tuples. Each tuple should be the year and the amount for that year. (The first tuple in the list will just consist of the start year and the start amount.) Then use this to calculate the infinite list of yearly total populations of the earth, assuming 6 billion people now and an annual growth rate of 1.3%.
There is a Haskell graphics package if you want to do something graphical - see the Haskell web site. An ancient 505 web site (for 1994) has some samples in Miranda (another pure functional language, closely related to Haskell): Miranda examples.
If you have an example that you like, please make a slide with your function to show in class on October 26, or be prepared to demo it on the laptop. I'd like students to show some interesting examples they have done. Don't be shy!