Parametricity is a property of parametrically polymorphic functions which roughly says that "the more generic a function type is, the more restricted we are in implementing the function." This is because parametric polymorphism removes information about the concrete values, leaving only structural properties, later allowing the type to be instantiated with different concrete types of values. Intuitively, if we consider the set of inhabitants of some given type, then the more parametric the type, the smaller will be the set of values with such a type. In practice, parametricity allows us to reason about our functions based on the types, and is the theory behind some fancy extensions to the typeclass derivation mechanism of Haskell. In this problem, we will explore some consequences of this property and learn to use types as a reasoning tool, through deriving programs by calculation. 1.1[26=12 pts ] The Algebra of Datatypes Definition: an inhabitant of a type is a value v such that v::. denotes the size of the set of inhabitants of . To get started, we'll look at inhabiting ADTs, and then functions. For this question, do not consider undefined (sometimes written ) as a valid answer. data Animal = Cat I Dog I Mouse 1. How many inhabitants does Animal have? Give an example. data AnimalPair = AnimalPair Animal Animal data Either a b= Left a | Right b 2. How many inhabitants does AnimalPair have? Give an example. 6. How many inhabitants does Either (Maybe Animal) (Pair (Pair Animal Animal) Animal) have? data Naybe a = Just a I Nothing 1.2[26=12 pts ] Types and Lambda Calculus 3. How many inhabitants does Maybe Animal have? Give an example. Now we consider the effect polymorphism has on the inhabitation of function types. For each of the following types, (a) write down how many distinct functions there are for the given most general type and (b) give an example (if one exists). Write all your functions in form. 1. aa Answer: A Hrow manv inhahitante dros Mavhe a have? Civa unur ancunor in tarme af a 2. ab data Pair a b = Pair a b 4. abb 1. ppts| Give a definition for bog::(ab)[a[b] 5. (abc)(ab)ac 2. [4pts] Give a definition for zog::a[ab][b]. 6. aZ6. (Hint: Zn is the set of integers modulo n.) 3. [4pts] Write boq using hoq. Answer: 1.3 [12pts] Type Tetris Now we shall put parametricity to work as a reasoning tool to write Haskell programs completely mechanically - by simply plugging together functions of the correct types. For each part, give a definition in Haskell using only the following functions: ($)(.)flipmapconcat:(ab)ab:(bc)(ab)(ac):(abc)(bac):(ab)[a][b]:[[a]][a] You may, however, compose the given functions by creating abstractions. These are all standard Haskell functions, so you can verify your solutions out in GHCi. (Enter :t to print the type of the function). For example, consider the function hog with the type: hog::(cd)(abc)abd Given the above type, we can derive the following function definition: hog=(.).(.) To solve these problems, you may find it useful to first write them using abstractions