Homework # 13 (corrected)
due Tuesday, May 11, 4:00 PM

Polynomials (Again!)

When we worked with polynomials over rings using ML, we had to pass around a tuple of functions to make up for the fact that overloading in ML was fixed. Unlike ML, Haskell has a way to extend overloading in a systematic way, using ``type classes.'' One advantage is that one doesn't need to explicitly pass in the needed functions; the Haskell system ensures that they are simply available when needed.

The Num type class permits you to use +, *, negate (unary minus) as well as integer constants (fromInteger). Write a function power that can take an Int and anything of a Num type and raise it to this power. It has the following type:

power :: (Num a) => Int -> a -> a
power n x = ...

Notice that you don't need to take a parameter corresponding to the (Num a) => part of the type.

Implement the following functions for polynomials where a polynomial is a list of something that satisfies the Num type class.

type Poly a = [a]
eval :: (Num a) => a -> Poly a -> a
scale :: (Num a) => a -> Poly a -> Poly a
polyadd :: (Num a) => Poly a -> Poly a -> Poly a
polymul :: (Num a) => Poly a -> Poly a -> Poly a

Then make [a] an instance of Num using these functions; in particular an integer becomes a one-element polynomial. (You can't make (Poly a) an instance because Poly is just a type renaming.) Show that all this works by evaluating:

Main> power 3 8
512
Main> power 3 [1,1]
[1,3,3,1]
Main> eval 1.0 (power 3 (1 + [0.0, 1.0]))
8.0

One of the benefits of Haskell is that it can handle infinite lists. Thus, we can use the polynomial package to represent infinite Taylor polynomials. For example:

$$e^x = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + \ldots + \frac{x^n}{n!} + \ldots$$

To do this, first define the infinite list of (double, not integer) factorials. Then define exppoly as the infinite polynomial using the factorial list. Use list comprehensions in both cases to do each in one line.

Thus one can evaluate:

Main> take 5 exppoly
[1.0,1.0,0.5,0.166666666666667,0.0416666666666667]
Main> eval 1.0 (take 5 exppoly)
2.70833333333333
Main> eval 1.0 (take 10 exppoly)
2.71828152557319

Put all these definitions in poly.hs. (Type :also poly to read in the file into hugs.)

Lazy Evaluation

Haskell uses ``lazy evaluation'' which is a kind of by-need parameter passing. The only expressions evaluated are the ones needed to produce a printed result. For each of the following ``let'' expressions, indicate which variables are evaluated, and explain:

1. 
   let
     x = 1
     y = 2
     f a b = b
     z = x + y
     a = f y 10
   in
     a * 3
   

2. 
   let 
     x = y + 1
     y = 3
   in
     x * x
   

3. 
   let
     x = 1
     y = 2
     z = 3
   in
     if x > 1 then y else z
   

4. 
   let
     x = 1:y
     y = 2:x
     z = 3:x
   in
     z !! 1
   

We recommend you try out these expressions in hugs; if you try one at the top-level prompt, you need to write the entire expression in one line and will need to use the verbose syntax for ``let'':

let { $x$=$e$; ... $x$=$e$;} in $e$

Input and Output

Answer the following questions:

1. Suppose the program creates a list of monadic values. Each value performs some reading and writing from/to the user. The main program then selects a single action:

   
   actions :: [IO ()]
   actions = ...
   
   main = actions !! 6
   

   What happens with the six actions in the list before the one selected? The ones after? Explain!
2. Suppose we had a function that takes two monadic values and returns one:

   
   mystery :: IO () -> IO () -> IO ()
   mystery x y = ...
   

   Suppose this function dosn't create any of its own monadic values, and the only function it may call is ``bind'' (AKA >>=) which has type:

   
   (>>=) :: IO a -> (a -> IO b) -> IO b
   

   This function has four different possible behaviors. Give the bodies of each and explain what the result of performing the result action will be.
3. A simple kind of purely functional (side-effect-free) input-output is to define the program as a function that takes the user input (as a list of characters) and returns a list of characters as the result. For example, the following function echoes back the input to the output after removing the letter 'Q' wherever it occurs:

   
   program :: [Char] -> [Char]
   program l = filter (\c -> c /= 'Q') l
   

   How can such a program be interactive? Explain!
4. Assuming that program has such a type (and perhaps does something much more interesting) how could we use it to define main of type IO ()? Give the (one-line!) definition of main on paper and explain how it works. We recommend you test it--type ``Control-C'' to get back to the hugs prompt.

Submitting Your Work

You submit your program work by putting it in the homework13 directory in your AFS class volume; creating this directory if necessary. You may do all your work in this directory, or you may wish to do your work in a different directory and copy things when correct into this directory. In any case, you will lose permission to write things in this directory after the deadline, which is 4:00pm on Tuesday, May 11th. In other words, you must be done before lecture starts.

The homework13 directory should include the following:

• poly.hs

About this document