Code and Notes (Week 8 Tuesday)

This is the Haskell code from today's lecture, including notes on experiments from our in-class discussions, with cleanups and further explanations added after.

Reminders:

ghc Main will compile Main.hs to an executable binary.
ghci will open a read-eval-print loop (REPL).
- There, use :l Main.hs to compile and load Main.hs.
- After that you can invoke individual functions of Main directly.
- Use :r to recompile the currently loaded file.
- Use :t blah to print the type of blah.

-- Week 8A: Parametric Polymorphism in Haskell
module Main where
import Data.Typeable

-- a polymorphic datatype and function
data MyList a = MyNil | MyCons a (MyList a)
  deriving Show -- this allows printing the datatype

toMyList :: a -> MyList a
toMyList x = MyCons x MyNil

-- a monomorphic swap function
swapInts :: (Int,Int) -> (Int,Int)
swapInts p = (snd p, fst p)

-- a polymorphic swap function
swap :: (a,b) -> (b,a)
swap p = (snd p, fst p)

-- Polymorphic recursion example
data Dims a = Step a (Dims [a]) | Epsilon
  deriving Show

-- Example Dims value, from the slide
-- NB: Can use :t in ghci to display type of a term
mydims :: Dims Int
mydims = Step 1 (Step [1, 2] (Step [[1, 2], [3, 4]] Epsilon))

-- A summing function on Dims, from the slide
sumDims :: (a -> Int) -> Dims a -> Int
sumDims f Epsilon = 0
sumDims f (Step x t) = (f x) + sumDims (sum . map f) t

-- One of Hindley-Milner polymorphism's requirements
-- is that forall quantification can only occur
-- on the outermost part of a type.
-- Both of the following take a function f of
-- form `[a] -> Int` and return an integer.

-- This one is Hindley-Milner polymorphic.
-- Note it can take a function f that doesn't
-- have to be polymorphic for all `a`.
outermostAll :: forall a. ([a] -> Int) -> Int
outermostAll f = f [] -- this implementation is valid for both types
-- outermostAll f = f [1,2] -- compile error! we don't know what a is

-- This one is not Hindley-Milner polymorphic.
-- Note it has to receive a function f that is
-- polymorphic for all `a`.
nonOutermost :: (forall a. [a] -> Int) -> Int
-- nonOutermost f = f [] -- this implementation is valid for both types
nonOutermost f = f [1,2] -- valid impl. for this type, because
                         -- we know f should work for any a

-- Some candidates for the argument f.
-- For which of the above do they work?
intFun :: [Int] -> Int
intFun [] = 0
intFun (h:t) = h + intFun t

boolFun :: [Bool] -> Int
boolFun [] = 0
boolFun (h:t) = if h then 1 + boolFun t else boolFun t

-- Note, unlike the above two, this one cannot refer to
-- any values because it has to work for all types a!
polyFun :: forall a. [a] -> Int
polyFun [] = 3
polyFun (h:t) = polyFun t

-- Parametricity and constraints on implementations
-- How many implementations?
foo :: Int -> Int
-- foo x = undefined -- define me!
-- We can think of a few! With basically infinite variations:
-- foo x = x + 1 -- you could have as many variations on this
--                  as you have constant Int values
foo x = x * x -- you could take x^n for any n
-- etc...
-- How about this one?
goo :: a -> a
-- goo x = undefined -- define me!
-- We only find one:
goo x = x

-- For completeness, so the module can be compiled
main :: IO ()
main = putStrLn $ "Hello Week 8!"