COMP[39]161 Concepts of Programming Languages
Semester 2, 2018

Tute (Week 11)

Table of Contents

1 Overloading

Consider the following file in Haskell:

class Compare a where
  cmp :: a -> a -> Bool

instance Compare Int where
  cmp x y = x <= y

instance (Compare a) => Compare [a] where
  cmp xs ys = and (zipWith cmp xs ys)

group  :: (Compare a) => [a] -> [[a]]
group []     = []
group (x:xs) = let (ys, zs) = span (cmp x) xs
                in (x:ys) : group zs

How would the type checker translate this code to remove the type classes?

type CompareDict a = (a -> a -> Bool)

intCompareDict :: CompareDict Int
intCompareDict x y = x <= y

listCompareDict :: CompareDict a -> CompareDict [a]
listCompareDict cmp = and (zipWith cmp xs ys)

group  :: CompareDict a -> [a] -> [[a]]
group cmp []     =  []
group cmp (x:xs) = let (ys, zs) = span (cmp x) xs
                    in (x:ys) : group cmp zs

2 Subtyping

2.1 Coercions and Subtyping

You are given the type Rectangle, parameterised by its height and width, and the type Square parameterised by the length of one of its sides. Neither type is mutable.

a. Which type is the subtype, which type is the supertype?

b. Give a subtype/supertype ordering of the following set of function types: Rectangle -> Rectangle, Rectangle -> Square, Square -> Rectangle, Square -> Square.

c. Define a data type Square and a data type Rectangle in Haskell. Then define a coercion function from elements of the subclass to elements of the superclass.

d. Show that the ordering you have given in the previous question is correct by defining coercion functions for each pair of types in a subtyping relationship in part (b).

a. Square is a subtype of Rectangle.

b. Rectangle -> Square is a subtype of Rectangle -> Rectangle and Square -> Square, which are both subtypes of Square -> Rectangle.


data Square = Square Int
data Rectangle = Rect Int Int

coerce :: Square -> Rectangle
coerce (Square w) = Rect w w


rs2rr :: (Rectangle -> Square) -> (Rectangle -> Rectangle)
rs2rr f = coerce . f

rs2ss :: (Rectangle -> Square) -> (Square -> Square)
rs2ss f = f . coerce

rr2sr :: (Rectangle -> Rectangle) -> (Square -> Rectangle)
rr2sr f = f . coerce

ss2sr :: (Square -> Square) -> (Square -> Rectangle)
ss2sr f = coerce . f

2.2 Constructor variance

List some examples of a covariant, contravariant and invariant type constructor.

A function's argument is contravariant. A function's return type is covariant. A data type like Endo below is invariant:

data Endo a = E (a -> a)

2018-11-16 Fri 19:37

Announcements RSS