# Coverting tuples to lists

• Let's say you wanted to convert pairs to lists of Strings

pairToStringList :: (Show a, Show b) => (a, b) -> [String]
pairToStringList (a, b) = [show a, show b]
*Main> pairToStringList (True, Just 3)
["True","Just 3"]
• Now say you want to convert a pair of Enums to a list of Ints

pairToIntList :: (Enum a, Enum b) => (a, b) -> [Int]
pairToIntList (a, b) = [fromEnum a, fromEnum b]
• Can we generalize this function? Would like to say:

pairToList conv (a, b) = [conv a, conv b]
pairToList show (True, Just 3)   -- error
• Unfortunately, can't pass methods as arguments, only functions

pairToList :: (a -> b) -> (a, a) -> [b]

# Polymorphism with fundeps

• Let's represent ad hoc polymorphic methods with a class

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE FlexibleInstances #-}

class Function f a b | f a -> b where
funcall :: f -> a -> b
instance Function (a -> b) a b where
funcall = id

pairToList :: (Function f a c, Function f b c) =>
f -> (a, b) -> [c]
pairToList f (a, b) = [funcall f a, funcall f b]
• Use placeholder singleton types to represent particular methods

data ShowF = ShowF
instance (Show a) => Function ShowF a [Char] where
funcall _ = show

instance (Enum a) => Function FromEnumF a Int where
funcall _ = fromEnum

# Function in action

• Now singleton types act like method arguments:

*Main> pairToList ShowF (True, 3)
["True","3"]
*Main> pairToList FromEnumF (False, 7)
[0,7]
• Now, what if you wanted tupleToList for arbitrary n-tuples?
• Can auto-generate instances for a generic tuple fold, e.g.:
class TupleFoldr f z t r | f z t -> r where
tupleFoldr :: f -> z -> t -> r
• Works okay for small tuples, craps out around 10-tuple without larger -fcontext-stack argument
• Unfortunately, I'm temporarily out of compile-time tricks
• An alternative is to use run-time type information (RTTI)
• RTTI easier to reason about, but adds runtime overhead and errors
• We will come back to static tricks at end of lecture

# DeriveDataTypeable extension

• Haskell allows six classes to be automatically derived
• Show, Read, Eq, Ord, Bounded, Enum
• DeriveDataTypeable extension adds two more: Typeable, Data

data MyType = Con1 Int | Con2 String deriving (Typeable, Data)
• These types encode run-time type information in various ways
• Require that inner types (Int, String above) also have instances
• Okay to use parameterized types, though
data MyTyCon a = MyTyCon a deriving (Typeable, Data)
• Most standard library types have Typeable and Data instances
• Provide programming approach known as "scrap your boilerplate"

# The Typeable class

• import Data.Typeable to get Typeable class:

class Typeable a where
typeOf :: a -> TypeRep -- Note: never evaluates argument

data TypeRep -- Opaque, but instance of Eq, Ord, Show, Typeable
• This allows us to compare types for equality

rtTypeEq :: (Typeable a, Typeable b) => a -> b -> Bool
rtTypeEq a b = typeOf a == typeOf b
*Main> rtTypeEq True False
True
*Main> rtTypeEq True 5
False
• Big Whoop!
• Couldn't we already do this at compile time with OverlappingInstances?
• Doing it dynamically is less exciting, but different
• And allows one very important function...

# Type Casting

• GHC has a function unsafeCoerce

unsafeCoerce :: a -> b
• And note: it doesn't just return
• If the name doesn't scare you, the type signature should
• Let's use Typeable to make a safe cast function

cast :: (Typeable a, Typeable b) => a -> Maybe b
cast a = fix \$ \ ~(Just b) -> if typeOf a == typeOf b
then Just \$ unsafeCoerce a
else Nothing
*Main> cast "hello" :: Maybe String
Just "hello"
*Main> cast "hello" :: Maybe Int
Nothing
• Safe if typeOf on two different types always returns different TypeReps
• Guaranteed by deriving (Typeable); SafeHaskell disallows manual instances

# Generalized casting

• To cast monadic computations, etc., use generalized cast, gcast:

import Data.Maybe (fromJust)

gcast :: (Typeable a, Typeable b) => c a -> Maybe (c b)
gcast ca = mcr
where mcr = if typeOf (unc ca) == typeOf (unc \$ fromJust mcr)
then Just \$ unsafeCoerce ca
else Nothing
unc :: c x -> x
unc = undefined
*Main> fromJust \$ gcast (readFile "/etc/issue") :: IO String
"\nArch Linux \\r  (\\n) (\\l)\n\n"
*Main> fromJust \$ gcast (readFile "/etc/issue") :: IO Int
*** Exception: Maybe.fromJust: Nothing
• Note undefined function unc in definition of gcast
• Common idiom--poses no problem because typeOf is not strict
• Recall context Typeable b => is like a hidden argument; often use undefined functions with type signatures to unpack types and get dictionaries

# Using Typeable: mkT[Boilerplate1]

• Write a function that behaves like id except on one type

mkT :: (Typeable a, Typeable b) => (b -> b) -> a -> a
mkT f = case cast f of
Just g -> g
Nothing -> id
• mkT stands for "make transformation"
• Example:

newtype Salary = Salary Double deriving (Show, Data, Typeable)

raiseSalary :: (Typeable a) => a -> a
raiseSalary = mkT \$ \(Salary s) -> Salary (s * 1.04)
*Main> raiseSalary ()
()
*Main> raiseSalary 7
7
*Main> raiseSalary (Salary 7)
Salary 7.28

# Using Typeable: mkQ[Boilerplate1]

• Function that computes over one type or returns default val:

mkQ :: (Typeable a, Typeable b) => r -> (b -> r) -> a -> r
mkQ defaultVal fn a = case cast a of
Just b -> fn b
Nothing -> defaultVal
• mkQ stands for "make query"
• Example

salaryVal :: Typeable a => a -> Double
salaryVal = mkQ 0 \$ \(Salary s) -> s
*Main> salaryVal ()
0.0
*Main> salaryVal 7
0.0
*Main> salaryVal (Salary 7)
7.0

# Functions on multiple types: extQ

• mkQ only works for one type
extQ :: (Typeable a, Typeable b) =>
(a -> r) -> (b -> r) -> a -> r
extQ q f a = case cast a of
Just b -> f b
Nothing -> q a
• Now can cascade multiple one-type query functions

myShow :: Typeable a => a -> Maybe String
myShow = mkQ Nothing (Just . show :: Int -> Maybe String)
`extQ` (Just . show :: Bool -> Maybe String)
`extQ` (Just . show :: Integer -> Maybe String)
`extQ` (Just . show :: Double -> Maybe String)
• Kind of tedious, but could approximate goal of tupleToList at beginning of lecture if tuples contain limited number of types

# ExistentialQuantification extension

• Lets you introduce type variables on right side of data declaration

{-# LANGUAGE ExistentialQuantification #-}
data Step s a = Done | Skip !s | Yield !a !s
data Stream a = forall s. Stream (s -> Step s a) !s
• Given a value of type Stream a, there exists a type s such that...
But syntax uses forall, not exists, to avoid introducing new keyword
• Very safe extension (Control.Exception relies on it)
• Don't confuse with Rank2Types, where forall means for all types s:

data Stream a = Stream (forall s. s -> Step s a)
• Contexts on existential variables like hidden dictionary fields

data Showable = forall a. (Show a) => Showable a
instance Show Showable where
show (Showable a) = "Showable " ++ show a
• A Showable value has both a value of type a, and a dictionary for Show

# Example: Dynamic type

• Data.Dynamic has type Dynamic, which can hold anything Typeable

data Dynamic  -- opaque type
toDyn :: Typeable a => a -> Dynamic
fromDynamic :: Typeable a => Dynamic -> Maybe a
• Actual implementation slightly gross
• Uses unsafeCoerce to coerce everything to a placeholder Obj type
• But easy to implement safely with ExistentialQuantification:

data Dynamic = forall a. Typeable a => Dynamic a

toDyn :: Typeable a => a -> Dynamic
toDyn = Dynamic

fromDynamic :: Typeable a => Dynamic -> Maybe a
fromDynamic (Dynamic a) = cast a

# Example: Extensible exceptions [Marlow]

• GHC runtime implements primitive, unsafe exceptions

raise# :: a -> b
catch# :: IO a -> (b -> IO a) -> IO a  -- slight simplification
• Must ensure that, as used, b is always same type, otherwise get unsafe coercion
• In reality, want many exception types, organized into a hierarchy
• Control.Exception implements safe, hierarchical exceptions
• raise# and catch# only ever called with one type: SomeException
class (Typeable e, Show e) => Exception e where
toException :: e -> SomeException
toException = SomeException                 -- default impl
fromException :: SomeException -> Maybe e
fromException (SomeException e) = cast e    -- default impl

data SomeException = forall e. Exception e => SomeException e
deriving Typeable  -- note use of ExistentialQuantification
instance Show SomeException where
show (SomeException e) = show e

# Throwing and catching exceptions

class (Typeable e, Show e) => Exception e where
toException :: e -> SomeException
fromException :: SomeException -> Maybe e
• To throw an exception, first convert it to type SomeException

throw :: Exception e => e -> a
throw e = raise# (toException e)
• To catch an exception, must ensure it matches desired type

-- Define catchX because catch#'s real type more complicated
catchX :: IO a -> (b -> IO a) -> IO a
catchX (IO a) handler = IO \$ catch# a (unIO . handler)

catch :: (Exception e) => IO a -> (e -> IO a) -> IO a
catch action handler = catchX action handler'
where handler' se | Just e <- fromException se = handler e
| otherwise                  = throwIO se
• Note calling handler e makes fromException se uses e's Exception dictionary, because Just e is fromException's return value

# Making hierarchical exceptions

• Easy to add your own top-level exception type

data MyException = MyException deriving (Show, Typeable)
instance Exception MyException -- use default methods
• But you can also create a hierarchy of exception types

data AppError = forall e. Exception e => AppError e
deriving (Typeable)
instance Show AppError where show (AppError e) = show e
instance Exception AppError

data Error1 = Error1 deriving (Show, Typeable)
instance Exception Error1 where
toException = toException . AppError
fromException se = do  -- using Maybe as a Monad here
AppError e <- fromException se
cast e

-- Now can do the same for Error2, and catch both as AppError
• Let's you catch just Error1, or any AppError

# The Data class

class Typeable a => Data a where ...
• In addition to Typeable, can also derive Data
• Allows generic traversal and construction of data structures
• We will build it up one method at a time, using the following example
import Data.Data

data T a b = C1 a b | C2 deriving (Typeable, Data)
• deriving Data will cause this gfoldl method to be defined

gfoldl k z (C1 a b) = z C1 `k` a `k` b
gfoldl k z C2       = z C2
• This allows us to implement functions working over all sized tuples
• Two limitations:
1. Once you introduce types, things get uglier [cosmetic]
2. The only dictionaries available are Data and Typeable [fundamental]

# gfoldl traversals

• The actual type of gfoldl:

-- Recall:  gfoldl k z (C1 a b) = ((z C1) `k` a) `k` b

gfoldl  :: (forall d b. Data d => c (d -> b) -> d -> c b)  -- k
-> (forall g. g -> c g)                            -- z
-> a
-> c a
• If you ignore the c parameter, looks like re-applying constructor
• E.g., call gfoldl (\$) id x, where b type of partially applied constructor
• Can wrap Identity monad (applicative functor) around values to ignore c
raiseSalaries :: (Data x) => x -> x
raiseSalaries x = runIdentity \$ gfoldl step return (raiseSalary x)
where step cdb d = cdb <*> (pure \$ raiseSalaries d)
• Function only bumps salaries, leaves other data fields alone
*Main> raiseSalaries \$ Just (1, Salary 4, True, (Salary 7, ()))
Just (1,Salary 4.16,True,(Salary 7.28,()))

# gfoldl queries

• Can use a different type c to ignore constructor/arg types

newtype Q r a = Q { unQ :: r }

qappend :: (Monoid r) => Q r a -> Q r b -> Q r c
qappend (Q r1) (Q r2) = Q \$ mappend r1 r2
• Notice we completely ignore second type argument (a)
• Now say we want to sum all salaries in a structure

sumSalaries :: (Data x) => x -> Double
sumSalaries x = getSum \$ unQ \$ gfoldl step (\_ -> toQ x) x
where step tot d = tot `qappend` (Q \$ Sum \$ sumSalaries d)
toQ = mkQ (Q \$ Sum 0) \$ \(Salary s) -> Q \$ Sum s
*Main> sumSalaries (Salary 7, Salary 9, True, Just (Salary 4))
20.0

# Unfolding [Boilerplate2]

• We've seen how to traverse, modify, and reduce data structures
• Could, for instance, use gfoldl to serialize a data structure
• What about unserializing a data structure?
• Data contains two more useful methods

• Again, assume example type
data T a b = C1 a b | C2 deriving (Typeable, Data)
• And Data will contain the following methods for T:
toConstr (C1 _ _) = ...     -- encodes constructor number
toConstr C2       = ...

gunfold k z c = case constrIndex c of
1 -> k (k (z C1))
2 -> z C2
• This is the dual of gfoldl--instead of supplying the values to k, now k has a chance to feed values to the constructor

# Type of gunfold

class (Typeable a) => Data a where
dataTypeOf :: a -> DataType -- non-strict, return has [Constr]
toConstr :: a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r)
-> Constr
-> c a

dataTypeConstrs :: DataType -> [Constr]
indexConstr :: DataType -> Int -> Constr
maxConstrIndex :: DataType -> Int
• Now you can use cast to produce values to feed into constructor
• Can use to implement generic read/unmarshal functions

# The generic-deriving package

• All this boilerplate stuff happens at runtime
• Slows your program down, doesn't catch errors at compile time
• Another approach is to do it all statically [Magalhães]

• Define a single Generic class that converts any datatype to a Rep that can be computed over generically:
{-# LANGUAGE TypeFamilies #-}

class Generic a where
type Rep a :: * -> *
from :: a -> Rep a x
to :: Rep a x -> a
• type Rep is an extension called TypeFamilies. Can read above as:

class Generic a rep | a -> rep where
from :: a -> rep x
to :: rep x -> a
• But what is a generic representation?

# generic-deriving classes

• Need to be able to deconstruct/query Rep; let's use classes for that

{-# LANGUAGE TypeFamilies, KindSignatures #-}

class Datatype d where
datatypeName :: t d (f :: * -> *) a -> String
moduleName   :: t d (f :: * -> *) a -> String
class Selector s where
selName :: t s (f :: * -> *) a -> String
class Constructor c where
conName :: t c (f :: * -> *) a -> String
• For example:
{-# LANGUAGE TemplateHaskell #-}
import Generics.Deriving
import Generics.Deriving.TH

data T a b = C1 a b | C2 deriving (Show)
deriveAll ''T -- creates a Generic instance for T
*Main> datatypeName \$ from (C1 () ())
"T"

# generic-deriving types

-- Nullary constructor (e.g., C2 in data T = ... | C2)
data U1 p = U1

-- Constructor with multiple arguments
data (:*:) f g p = f p :*: g p
infixr 6 :*:

-- Type with multiple constructors
data (:+:) f g p = L1 { unL1 :: f p } | R1 { unR1 :: g p }
infixr 5 :+:

newtype K1 i c p = K1 { unK1 :: c }
type Rec0 = K1 R

newtype M1 i c f p = M1 { unM1 :: f p }
data D; type D1 = M1 D -- c instance of Datatype, f is C1 or :+:
data C; type C1 = M1 C -- c instance of Constructor, f is S1 or :*:
data S; type S1 = M1 S -- c instance of Selector, f is Rec0 or U1
• Ignore parameter p (reserved to support type parameters of kind ∗ → ∗)
• M1 exists so a single traversal method can skip over D1, C1, and S1
• Could say newtype Rec0 c p = K1 c, but some instances use K1 P

# Example deriveAll output

data T a b = C1 a b | C2 deriving (Show)

-- deriveAll ''T spit out:
data T_
instance Datatype T_ where
datatypeName _ = "T"
moduleName _ = "Main"

data T_C1_
data T_C2_
instance Constructor T_C1_ where conName _ = "C1"
instance Constructor T_C2_ where conName _ = "C2"

type Rep0T_ a_0 b_1 = D1 T_
(C1 T_C1_ (S1 NoSelector (Rec0 a_0) :*: S1 NoSelector (Rec0 b_1))
:+: (C1 T_C2_ (S1 NoSelector U1)))

instance Generic (T a_0 b_1) where
type Rep (T a_0 b_1) = Rep0T_ a_0 b_1
from (C1 f0 f1) = M1 (L1 (M1 (M1 (K1 f0) :*: M1 (K1 f1))))
from (C2)       = M1 (R1 (M1 (M1 U1)))
to (M1 (L1 (M1 (M1 (K1 f0) :*: M1 (K1 f1))))) = C1 f0 f1
to (M1 (R1 (M1 (M1 (U1)))))                   = C2

# How can we use this?

• Say we are defining our own Show-like class

class MyShow a where myShow :: a -> String
instance MyShow [Char] where myShow = show
instance MyShow Int where myShow = show
• Want it to work with all user-defined data types
• Let's define a class Show1 to deal with annoying p parameters
{-# LANGUAGE FlexibleInstances, UndecidableInstances,
OverlappingInstances, TypeSynonymInstances, TypeOperators,
TypeFamilies, TemplateHaskell, FlexibleContexts #-}

class MyShow1 f where myShow1 :: f p -> String
• And let's define generic traversal methods
instance (MyShow1 f) => MyShow1 (M1 i c f) where  -- for D1, S1
myShow1 m1 = myShow1 (unM1 m1)
instance (MyShow1 f, MyShow1 g) => MyShow1 (f :+: g) where
myShow1 (L1 a) = myShow1 a
myShow1 (R1 a) = myShow1 a

# Non-generic instances of MyShow1

• When we hit a constructor, want to print the name

instance (Constructor c, MyShow1 f) => MyShow1 (C1 c f) where
myShow1 m1 = conName m1 ++ myShow1 (unM1 m1)
• We're using OverlappingInstances, since already have M1 instance
• When we have no constructor args, don't show anything

instance MyShow1 U1 where myShow1 _ = ""
• When we have multiple constructor args, show them all

instance (MyShow1 f, MyShow1 g) => MyShow1 (f :*: g) where
myShow1 (fp :*: gp) = myShow1 fp ++ myShow1 gp
• When you hit the actual value, show it

instance (MyShow c) => MyShow1 (K1 i c) where
myShow1 k1 = ' ' : myShow (unK1 k1)
• Now we're calling myShow, which we haven't yet defined for many types

# Implementing a generic MyShow

• Now can define generic MyShow in terms of MyShow1

instance (Generic a, MyShow1 (Rep a)) => MyShow a where
myShow a = myShow1 \$ from a
• Can we avoid OverlappingInstances?
• Could have defined separate D1, S1 instances of Show1 (easy)
• Could have avoided completely generic instance
Recommended use is just to define a function myShowDefault, then
myShowDefault :: (Generic a, MyShow1 (Rep a)) => a -> String
myShowDefault a = myShow1 \$ from a

instance MyShow T1 where myShow = myShowDefault
instance MyShow T2 where myShow = myShowDefault
instance MyShow T3 where myShow = myShowDefault
...
• There's still the problem of different behavior for [Char] vs. [a]...
I don't see how to fix this one, but might be possible

# GHC support for generic deriving

• GHC 7.2 supports Generic deriving through two new language extensions
• DeriveGenerics extension
• Just add deriving (Generic) to the end of declarations
• DefaultSignatures extension
• Allows default methods that don't work for all instances
class MyShow a where
myShow :: a -> String
default myShow :: (Generic a, MyShow1 (Rep a)) => a -> String
myShow = myShowDefault
• Makes it easier to declare instances
instance MyShow T    -- no need for a where clause