1.hs

-- you can call a function like `map` with a function and a list of integers, e.g.
map (+1) [0,1,2]   --> [1,2,3]

-- or on a list of strings
map (++", world!") ["Hello","Goodbye"]   --> ["Hello, world!","Goodbye, world!"]

-- question: can we use this function on any type, or just built in types?

-- `map` has this type signature:
map :: (a -> b) -> [a] -> [b]

-- which, due to the precedence of `->`, means this:
map :: (a -> b) -> ([a] -> [b])

-- that means that `map` takes a function from some type a to some type b, 
-- and gives you a new function from lists of a to lists of b. 

-- answer: any type!

-- but what if you want to map a function over another sort of data structure, like a tree?
-- we could write this easily using pattern matching:

-- first, the tree type
data Tree = Leaf Int
          | Branch Int Tree Tree

incrTree (Leaf n) = Leaf (n+1)
incrTree (Branch n l r) = Branch (n+1) (incrTree l) (incrTree r)

2.hs

-- now it's time to generalise a bit, why does a tree only contain integers?
-- here n is a type variable
data Tree n = Leaf n
            | Branch n (Tree n) (Tree n)

-- okay now rewrite the increment function
incrTree (Leaf n) = Leaf (n+1)
incrTree (Branch n l r) = Branch (n+1) (incrTree l) (incrTree r)

-- then we can use that on a tree, e.g.
incrTree $ Branch 5 (Leaf 7) (Leaf 9)   --> Branch 6 (Leaf 8) (Leaf 10)

-- and on a tree of floats!
incrTree $ Branch 5.0 (Leaf 7.0) (Leaf 9.0)   --> Branch 6.0 (Leaf 8.0) (Leaf 10.0)

-- But what about a tree of strings?
incrTree $ Leaf "Hello!"   --> type error! 

-- The `incrTree` function was automatically constrained to only work with numbers because
-- we used the (+) function in it. 
:t incrTree   --> incrTree :: (Num n) => Tree n -> Tree n    

-- i.e. a function that works on all values of type (Tree n) where n is an instance of the `Num` typeclass.

-- so here we are with a function for incrementing Trees of numbers. What if we want to
-- decrement a tree? We could write it:

decrTree (Leaf n) = Leaf (n-1)
decrTree (Branch n l r) = Branch (n-1) (decrTree l) (decrTree r)

-- but other than the name change, that only changed two characters!
-- why do we have to write all that boilerplate? 
-- let's write a `map` function for trees to make this easier.

treeMap :: (a -> b) -> (Tree a -> Tree b)
treeMap f (Leaf n) = Leaf (f n)
treeMap f (Branch n l r) = Branch (f n) (treeMap f l) (treeMap f r)

-- then we can write these other functions much more easily:
incrTree = treeMap (+1)
decrTree = treeMap (subtract 1)   -- (-1) just means negative 1 - an annoying quirk. 

3.hs

-- okay let's say we want to represent an optional value. 
-- some functions may return a valid value and otherwise
-- return nothing at all.
data Optional t = Invalid | Valid t

-- so what is the type of Invalid?
:t Invalid   --> Optional t

-- yes that's right, values can have a type that is not yet concrete.

-- we want to convert functions that work on normal types to functions 
-- that work on optional types. 
optify :: (a -> b) -> Optional a -> Optional b
optify f (Valid x) = Valid (f x)
optify f Invalid = Invalid 

4.hs

-- okay so how do we capture this notion of turning a function a -> b
-- into a function x a -> x b for some 'type function' x like Optional, Tree, [], etc.?

-- we introduce our own typeclass. let's call it Mappable.

class Mappable m where
    mmap :: (a -> b) -> (m a -> m b)

-- What this means is: "some things are Mappable, which means there is a function 
-- defined on them called `mmap`, which takes functions from a -> b and returns
-- a function from `m a` to `m b`. 

-- So lists are mappable, let's start with them:

instance Mappable [] where
    mmap f [] = []
    mmap f x:xs = (f x):(mmap f xs)

-- or:

instance Mappable [] where
    mmap = map

-- And so is Tree.

instance Mappable Tree where
    mmap f (Leaf n) = Leaf (f n)
    mmap f (Branch n l r) = Branch (f n) (mmap f l) (mmap f r)

-- And so is Optional.

instance Mappable Optional where
    mmap f (Valid x) = Valid (f x)
    mmap f Invalid = Invalid 

-- so what is the type of mmap?
:t mmap   --> (Mappable m) => (a -> b) -> m a -> m b

-- It turns out that Haskell defines Mappable for us. It just calls it something else:

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

-- And there are Functor instances for a wide variety of types in Haskell. e.g.

data Maybe x = Nothing | Just x
instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing