CS 8, Fall 2009

Short Assignment 4: Principal Types

Instructions

You should write up or print out your solutions to this assignment, and either turn them in at lecture, or leave them in the TA's mailbox at Sudikoff by class time on Mon. Oct. 5, 2009.

Hand-written solutions are perfectly acceptable, as long as they are neat. Please make sure your name is clearly marked on all pages, and if your solution takes more than one page, please staple the pages together. As with all other work for this class, no late assignments will be accepted.

You must work alone on this short assignment.

1. filter

   Give the principal type and a recursive definition for filter.

2. Principal types of some higher-order function calls.

   Give the principal types for the following functions:

   mapLen x = map length x
   mapRev x = map reverse x
   zipAppend x y = zipWith (++) x y
   

3. Principal types of Class Example

   At the end of class I defined the following functions and demonstrated suffixes:

   consToHead x list = (x : head list) : list
   suffixes xs = foldr consToHead [[]] xs

   Give the principal type of each. (These are tricky - you may want to check your answer by entering them into ghci and doing ":type". But try to work them out first, and try to understand where you went wrong if your answer is wrong.)

   Finally, give the principal type of:

   mapSuffixes x = map suffixes x