GHC Language extensions

Background: Monad transformers

Using StateT

Review: MonadIO

Background: recursive bindings

Recursion and monadic bindings

The DoRec extension

Example uses of mfix and rec

Implementing mfix

A generic mfix is not possible

MonadFix instance for StateT

Review: Type classes

MultiParamTypeClasses extension

FlexibleInstances extension

OverlappingInstances extension

Most specific instances

A case against OverlappingInstances

module Help where
class MyShow a where
myshow :: a -> String
instance MyShow a => MyShow [a] where
myshow xs = concatMap myshow xs

showHelp :: MyShow a => [a] -> String
showHelp xs = myshow xs -- doesn't see overlapping instance

module Main where
import Help

data T = MkT
instance MyShow T where
myshow x = "Used generic instance"
instance MyShow [T] where
myshow xs = "Used more specific instance"

main = do { print (myshow [MkT]); print (showHelp [MkT]) }
*Main> main
"Used more specific instance"
"Used generic instance"

FlexibleContexts extension

Monad classes

Problem: we've defeated type inference

FunctionalDependencies extension

Sufficient conditions of decidable instances

  1. The Paterson Conditions: for each assertion in the context

    1. No type variable has more occurrences in the assertion than in the head

      class Class a b | a -> b
      instance (Class a a) => Class [a] Bool -- bad: 2 * a => 1 * a
      instance (Class a b) => Class [a] Bool -- bad: 1 * b => 0 * b
    2. The assertion has fewer constructors and variables than the head

      instance (Class a Int) => Class a Integer   -- bad: 2 => 2
  2. The Coverage Condition: For each fundep left -> right, the types in right cannot have type variables not mentioned in left

    class Class a b | a -> b
    instance Class a (Maybe a) -- ok: a "covered" by left
    instance Class Int (Maybe b) -- bad: b not covered
    instance Class a (Either a b) -- bad: b not covered

Undecidable vs. exponential -- who cares?

UndecidableInstances extension

MonadIO revisited

Summary of extensions

Type-level natural numbers

data Zero = Zero      -- Type-level 0
data Succ n = Succ n -- Type-level successor (n + 1)

class NatPlus a b c | a b -> c, a c -> b where
natPlus :: a -> b -> c
natMinus :: c -> a -> b

instance NatPlus Zero a a where
natPlus _ a = a
natMinus a _ = a

-- Note failure of coverage condition below
instance (NatPlus a b c) => NatPlus (Succ a) b (Succ c) where
natPlus (Succ a) b = (Succ (natPlus a b))
natMinus (Succ c) (Succ a) = natMinus c a

Type-level booleans

data HFalse = HFalse deriving Show
data HTrue = HTrue deriving Show

class HNot a b | a -> b where hnot :: a -> b
instance HNot HFalse HTrue where hnot _ = HTrue
instance HNot HTrue HFalse where hnot _ = HFalse

class HEven a b | a -> b where hEven :: a -> b
instance HEven Zero HTrue where hEven _ = HTrue
instance (HEven n b, HNot b nb) => HEven (Succ n) nb where
hEven (Succ n) = hnot (hEven n)
*Main> hEven Zero
*Main> hEven (Succ Zero)
*Main> hEven (Succ (Succ Zero))
*Main> hEven (Succ (Succ (Succ Zero)))

Computing over types

The utility of TypeEq

Heterogeneous lists

Operations on heterogeneous lists

Object-oriented programming

"Tying the recursive knot"