notes/docs/lectures/compilers/05_functors.md

Functor

Parsing an expression in parentheses:

parseP :: Parser AST
parseP = do symbol '('
		t <- exp
		symbol  ')'
		return t

Before we write this sort of code, we need to understand type classes (especially monads)

Types vs Typeclasses

Types	Type classes
Bool	Eq
Char	Show
AST	Num
String	Functor
	Monad

Eq: type class for equality; a type can only be in this type class if two values of that type can be compared

A type can be a member (instance) of a type class, meaning that it has the properties/functions that the class requires

e.g. Bool is an instance of Eq and Show

Is there a type that is not in Eq?

(\c -> c :: Int) == (\c -> c :: Int)

ERROR: No instance for Eq(Int -> Int)

Why?

f :: Int -> Int
g :: Int -> Int

Then f == g should be fn == gn for every n, the computer cannot do this (halting problem).

Type Constructors

A type constructor takes a type to construct a new type.

Maybe - not a type but a type constructor

Maybe String - a type

newtype Parser a = P (String -> [a, String])

Parser is a type constructor

Parser AST is a type

Functor is a type class of which parser is an instance

Functor

class Functor f where
fmap :: (a -> b) -> fa -> fb

instance Functor Maybe where
fmap g (Just x) = Just (g x)
fmap g Nothing = Nothing -- fmap id = id

-- lists
instance Functor [] where
fmap g [] = []
fmap g (t:ts) = (g t) : fmap g ts

-- goal: write parser as a functor
newtype Parser a = P ( String -> [a, String] )
-- Need: fmap :: (a->b) -> Parser a -> Parser b

instance Functor Parser where
fmap g pa =  -- parser pa
	P (\str -> map (\(x,s) -> (gx,s))
					parse pa str)

Rules of Functors

fmap id = id -- identity
fmap (f . g) = fmap f . fmap g

Haskell doesn't enforce these rules; however, following them is convention.