Project 6: The Functor-Applicative-Monad Hierarchy

Project 6: The Functor-Applicative-Monad Hierarchy

Implement the Functor, Applicative, and Monad type class hierarchy from scratch for multiple types. Understand why each abstraction exists and prove the laws hold.

Quick Reference

Attribute	Value
Difficulty	Expert
Time Estimate	2-3 weeks
Language	Haskell (Alternatives: Scala, PureScript, OCaml)
Prerequisites	Project 5 (ADTs), understanding of type classes, higher-kinded types
Key Topics	Functors, Applicatives, Monads, Type Class Laws, Category Theory Connection
Main Resources	“Haskell Programming from First Principles” Chapters 16-18, Typeclassopedia

---

1. Learning Objectives

By completing this project, you will:

1. Understand the hierarchy conceptually: Explain why Functor, Applicative, and Monad form a progression and what each level adds
2. Implement instances for multiple types: Write Functor, Applicative, and Monad instances for Maybe, Either, List, Reader, State, and IO
3. Prove type class laws: Verify that your instances satisfy the required laws
4. Distinguish Applicative from Monad: Explain precisely when you need Monad’s power and when Applicative suffices
5. Compose effectful computations: Use the abstractions to sequence operations that might fail, carry state, or perform I/O
6. Recognize the patterns: See where these abstractions appear in real-world code and other languages
7. Understand the category theory connection: Know what functors and monads mean mathematically (at a conceptual level)

---

2. Conceptual Foundation

2.1 The Big Picture

Before diving into definitions, let’s understand what problem these abstractions solve.

The Core Problem: Computation in Context

Programs deal with values, but often those values come with “context”:

• A value that might not exist (Maybe)
• A value that might be an error (Either)
• A value that comes from configuration (Reader)
• A value that changes state (State)
• A value that requires I/O to produce (IO)
• Multiple possible values (List)

We want to work with these “values in context” while abstracting over what the context actually is.

The Hierarchy

Functor
   |
   |  "You can map over me"
   |
   v
Applicative
   |
   |  "You can apply wrapped functions to wrapped values"
   |
   v
Monad
   |
   |  "You can sequence operations where later depends on earlier"
   |
   v
(More specialized abstractions...)

Each level adds capability:

• Functor: Transform the value inside, preserving structure
• Applicative: Combine independent contexts
• Monad: Chain dependent computations

2.2 Functor: Mapping Over Structure

The Intuition

A Functor is anything you can map over. If you have a value “in a box” and a function that transforms values, Functor lets you apply the function inside the box:

f :: a -> b

     ┌───┐                ┌───┐
     │ a │  ───fmap f───> │ b │
     └───┘                └───┘
     Maybe                Maybe

The structure (Maybe, List, IO, etc.) is preserved. Only the value inside changes.

The Definition

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

Note that f is a type constructor (kind * -> *), not a concrete type. Maybe, [], IO are all type constructors.

The infix operator <$> is a synonym for fmap:

(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

The Laws

Functors must satisfy two laws:

Identity Law:

fmap id = id

Mapping the identity function changes nothing.

Composition Law:

fmap (f . g) = fmap f . fmap g

Mapping a composed function is the same as composing mapped functions.

These laws ensure fmap is “structure-preserving”–it only changes the values, not the shape.

Examples

-- Maybe
instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap f (Just x) = Just (f x)

-- List
instance Functor [] where
  fmap = map  -- The familiar map function!

-- Either (fixed left type)
instance Functor (Either e) where
  fmap _ (Left e)  = Left e
  fmap f (Right x) = Right (f x)

-- IO
instance Functor IO where
  fmap f action = do
    x <- action
    return (f x)

Why Functor Matters

Functor captures the essence of “container-like” things. Once you implement fmap, you can:

-- Transform values in any Functor
increment :: Functor f => f Int -> f Int
increment = fmap (+1)

-- Works for Maybe, List, IO, Either, ...
increment (Just 5)        -- Just 6
increment [1, 2, 3]       -- [2, 3, 4]
increment (Right 10)      -- Right 11

2.3 Applicative: Combining Contexts

The Limitation of Functor

Functor lets us apply a one-argument function. But what about multi-argument functions?

fmap (+) (Just 3)  -- Just (3 +) :: Maybe (Int -> Int)

We get a function inside a context. Now we need to apply it to another value in a context. Functor can’t do this–it only handles a -> b, not f (a -> b).

The Intuition

Applicative lets us apply functions that are themselves in a context:

     ┌─────────┐     ┌───┐           ┌───┐
     │ a -> b  │ <*> │ a │  ───────> │ b │
     └─────────┘     └───┘           └───┘
       Maybe          Maybe          Maybe

This enables multi-argument functions in contexts:

pure (+) <*> Just 3 <*> Just 5  -- Just 8

The Definition

class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

• pure: Lift a value into the minimal context
• (<*>): Apply a wrapped function to a wrapped value (pronounced “ap” or “apply”)

Note: Applicative requires Functor. The hierarchy is: Functor => Applicative.

Alternative Formulation: liftA2

Applicative can also be defined with:

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y

This lifts a binary function into an applicative context.

The Laws

Applicatives must satisfy four laws:

Identity:

pure id <*> v = v

Homomorphism (pure distributes over application):

pure f <*> pure x = pure (f x)

Interchange:

u <*> pure y = pure ($ y) <*> u

Composition:

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

There’s also a compatibility law with Functor:

fmap f x = pure f <*> x

Examples

-- Maybe
instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  _ <*> Nothing = Nothing
  Just f <*> Just x = Just (f x)

-- List (all combinations!)
instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

-- Either
instance Applicative (Either e) where
  pure = Right
  Left e <*> _ = Left e
  _ <*> Left e = Left e
  Right f <*> Right x = Right (f x)

The Power of Applicative

-- Validate multiple independent things
data Person = Person String Int

-- Each validation is independent
validateName :: String -> Maybe String
validateAge :: Int -> Maybe Int

-- Combine with Applicative
validatePerson :: String -> Int -> Maybe Person
validatePerson name age = Person <$> validateName name <*> validateAge age

-- Or using liftA2:
validatePerson name age = liftA2 Person (validateName name) (validateAge age)

The key insight: the validations are independent. We don’t need the name to validate the age. This independence is what Applicative captures.

Applicative for Parallelism

Because Applicative computations are independent, they can potentially run in parallel:

-- Fetch two independent resources
fetchBoth :: IO (Data, Config)
fetchBoth = (,) <$> fetchData <*> fetchConfig

-- These could run concurrently!

Libraries like async exploit this for concurrent programming.

2.4 Monad: Dependent Sequencing

The Limitation of Applicative

Applicative can combine independent contexts, but sometimes later operations depend on earlier results:

-- We need the user's ID to look up their profile
lookupUser :: String -> Maybe User
lookupProfile :: User -> Maybe Profile

-- With Applicative, we can't express this dependency!
-- We need the User before we can call lookupProfile

The Intuition

Monad lets us sequence operations where each step can depend on the previous result:

     ┌───┐                        ┌───┐
     │ a │ ───(a -> m b)───────> │ b │
     └───┘                        └───┘
       m                            m

The function a -> m b can inspect the a and decide what m b to produce. This is dependent computation.

The Definition

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b  -- "bind"
  return :: a -> m a                  -- Same as pure

The >>= operator (pronounced “bind”) is the heart of Monad. It:

1. Extracts the value from the context
2. Passes it to a function that produces a new context
3. Returns that new context

Note: Monad requires Applicative (which requires Functor).

The Laws

Monads must satisfy three laws:

Left Identity:

return a >>= f = f a

Wrapping a value and immediately binding is the same as just calling the function.

Right Identity:

m >>= return = m

Binding with return changes nothing.

Associativity:

(m >>= f) >>= g = m >>= (\x -> f x >>= g)

Binding is associative (like function composition).

These ensure that sequencing behaves predictably.

Examples

-- Maybe
instance Monad Maybe where
  Nothing >>= _ = Nothing
  Just x  >>= f = f x

-- List
instance Monad [] where
  xs >>= f = concat (map f xs)  -- Or: concatMap f xs

-- Either
instance Monad (Either e) where
  Left e  >>= _ = Left e
  Right x >>= f = f x

Do-Notation

Haskell provides syntactic sugar for monadic code:

-- Without do-notation:
lookupBoth :: String -> Maybe Profile
lookupBoth name =
  lookupUser name >>= \user ->
  lookupProfile user >>= \profile ->
  return profile

-- With do-notation:
lookupBoth :: String -> Maybe Profile
lookupBoth name = do
  user <- lookupUser name
  profile <- lookupProfile user
  return profile

The <- arrow “extracts” the value from the monad for use in subsequent lines.

2.5 The Crucial Difference: Applicative vs Monad

This is the most important conceptual point to understand.

Applicative: Static Structure

With Applicative, the structure of the computation is fixed before running:

-- We know we'll run BOTH validateName AND validateAge
validatePerson name age = Person <$> validateName name <*> validateAge age

Even if validateName fails, we could (in principle) still run validateAge and collect both errors. The structure doesn’t depend on intermediate results.

Monad: Dynamic Structure

With Monad, later structure depends on earlier values:

-- We might NOT run lookupProfile if lookupUser fails or returns the wrong user
lookupBoth name = do
  user <- lookupUser name
  if userActive user
    then lookupProfile user
    else return defaultProfile

The if decision happens after extracting user. We can’t know which branch runs without actually running lookupUser.

Why This Matters

Feature	Applicative	Monad
Structure	Known statically	Depends on values
Parallelism	Possible	Generally sequential
Error handling	Can collect all errors	Short-circuits
Power	Less	More
Optimization	More opportunities	Fewer opportunities

Rule of thumb: Use Applicative when possible, Monad when necessary.

2.6 The Reader Monad

Reader represents computations that read from an environment.

Motivation

Many functions need configuration or context:

loadUser :: Config -> UserId -> User
loadSettings :: Config -> Settings
buildPage :: Config -> User -> Settings -> Page

Threading Config through every function is tedious. Reader abstracts this pattern.

Definition

newtype Reader r a = Reader { runReader :: r -> a }

instance Functor (Reader r) where
  fmap f (Reader ra) = Reader $ \r -> f (ra r)

instance Applicative (Reader r) where
  pure a = Reader $ \_ -> a
  Reader rf <*> Reader ra = Reader $ \r -> rf r (ra r)

instance Monad (Reader r) where
  Reader ra >>= f = Reader $ \r ->
    let a = ra r
        Reader rb = f a
    in rb r

-- Ask for the environment
ask :: Reader r r
ask = Reader id

-- Run with a modified environment
local :: (r -> r) -> Reader r a -> Reader r a
local f (Reader ra) = Reader (ra . f)

Usage

type App a = Reader Config a

loadUser :: UserId -> App User
loadUser uid = do
  config <- ask
  return (fetchUser (dbConnection config) uid)

buildPage :: UserId -> App Page
buildPage uid = do
  user <- loadUser uid
  settings <- loadSettings
  config <- ask
  return (render config user settings)

-- Run the computation
main = do
  let config = Config { ... }
  let page = runReader (buildPage 123) config
  print page

2.7 The State Monad

State represents computations that read and modify state.

Motivation

Some algorithms need mutable state:

-- Generate unique IDs
nextId :: State Int Int
nextId = do
  n <- get
  put (n + 1)
  return n

Rather than threading state explicitly, State abstracts the pattern.

Definition

newtype State s a = State { runState :: s -> (a, s) }

instance Functor (State s) where
  fmap f (State sa) = State $ \s ->
    let (a, s') = sa s
    in (f a, s')

instance Applicative (State s) where
  pure a = State $ \s -> (a, s)
  State sf <*> State sa = State $ \s ->
    let (f, s')  = sf s
        (a, s'') = sa s'
    in (f a, s'')

instance Monad (State s) where
  State sa >>= f = State $ \s ->
    let (a, s') = sa s
        State sb = f a
    in sb s'

-- Get the current state
get :: State s s
get = State $ \s -> (s, s)

-- Set the state
put :: s -> State s ()
put s = State $ \_ -> ((), s)

-- Modify the state
modify :: (s -> s) -> State s ()
modify f = State $ \s -> ((), f s)

Usage

-- A simple stack machine
type Stack a = [a]
type StackOp a = State (Stack a)

push :: a -> StackOp a ()
push x = modify (x:)

pop :: StackOp a a
pop = do
  (x:xs) <- get
  put xs
  return x

-- Run a computation
example :: StackOp Int Int
example = do
  push 1
  push 2
  push 3
  a <- pop
  b <- pop
  return (a + b)

-- runState example [] == (5, [1])

2.8 The IO Monad

IO represents computations that interact with the outside world.

Why IO is a Monad

Haskell is pure–functions can’t have side effects. But programs need I/O! The solution: I/O actions are values of type IO a.

• IO a is a description of an action that, when executed, produces an a
• The Monad interface lets us sequence these descriptions
• The runtime system executes the resulting description

-- A value that describes printing "Hello"
putStrLn :: String -> IO ()

-- A value that describes reading a line
getLine :: IO String

-- Sequence actions
greet :: IO ()
greet = do
  putStrLn "What's your name?"
  name <- getLine
  putStrLn ("Hello, " ++ name ++ "!")

The main function has type IO (). The runtime executes this action.

Pure Functions in IO Context

-- Pure function
double :: Int -> Int
double x = x * 2

-- Use in IO context
main :: IO ()
main = do
  putStrLn "Enter a number:"
  line <- getLine
  let n = read line :: Int      -- Pure
  let result = double n          -- Pure
  putStrLn ("Doubled: " ++ show result)

Mixing pure and impure code is natural with the Monad interface.

2.9 Category Theory Connection

You don’t need category theory to use monads, but understanding the connection deepens your understanding.

Functors in Category Theory

A functor is a structure-preserving map between categories:

• Maps objects to objects: Type a to type F a
• Maps morphisms to morphisms: Function a -> b to function F a -> F b (that’s fmap!)
• Preserves identity and composition (the Functor laws!)

In Haskell, we work in the category Hask (types as objects, functions as morphisms). A Functor instance defines an endofunctor on Hask.

Monads in Category Theory

A monad on a category C consists of:

• An endofunctor T : C -> C
• A natural transformation eta : Id -> T (that’s return!)
• A natural transformation mu : T^2 -> T (that’s join!)

The monad laws in categorical form:

join . fmap join = join . join        -- Associativity
join . fmap return = join . return = id  -- Identity

The >>= form is equivalent:

m >>= f = join (fmap f m)

Why This Matters

Understanding the categorical view reveals:

1. Monads are a very general pattern (not Haskell-specific)
2. The laws ensure predictable composition
3. Related concepts (natural transformations, adjunctions) provide more tools

2.10 Common Derived Operations

From the core operations, we derive many useful functions:

-- Sequence actions, discarding first result
(>>) :: Monad m => m a -> m b -> m b
m >> n = m >>= \_ -> n

-- Apply a function inside a monad
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

-- Lift a value
pure :: Applicative f => a -> f a

-- Join nested contexts
join :: Monad m => m (m a) -> m a
join mm = mm >>= id

-- Map then join
(=<<) :: Monad m => (a -> m b) -> m a -> m b
(=<<) = flip (>>=)

-- Kleisli composition
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \a -> f a >>= g

-- Sequence a list of actions
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

-- Map then sequence
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
mapM f = sequence . fmap f

-- Filter with a monadic predicate
filterM :: Monad m => (a -> m Bool) -> [a] -> m [a]

-- Fold with a monadic function
foldM :: Monad m => (b -> a -> m b) -> b -> [a] -> m b

---

3. Project Specification

3.1 Phase 1: Functor Instances (Days 1-3)

Implement Functor for all your types from Project 5.

Task 1: MyFunctor Class

class MyFunctor f where
  myFmap :: (a -> b) -> f a -> f b

-- Infix synonym
(<$$>) :: MyFunctor f => (a -> b) -> f a -> f b
(<$$>) = myFmap

Task 2: Instances

instance MyFunctor MyMaybe where ...
instance MyFunctor (MyEither e) where ...
instance MyFunctor MyList where ...
instance MyFunctor MyTree where ...
instance MyFunctor ((->) r) where ...  -- Reader without newtype

Task 3: Law Verification

Write property tests for the functor laws:

prop_functorIdentity :: (MyFunctor f, Eq (f a)) => f a -> Bool
prop_functorIdentity x = myFmap id x == x

prop_functorComposition :: (MyFunctor f, Eq (f c))
                        => Fun a b -> Fun b c -> f a -> Bool
prop_functorComposition (Fn f) (Fn g) x =
  myFmap (g . f) x == myFmap g (myFmap f x)

3.2 Phase 2: Applicative Instances (Days 4-7)

Task 4: MyApplicative Class

class MyFunctor f => MyApplicative f where
  myPure :: a -> f a
  (<**>) :: f (a -> b) -> f a -> f b

-- Derived operations
myLiftA2 :: MyApplicative f => (a -> b -> c) -> f a -> f b -> f c
myLiftA2 f x y = f <$$> x <**> y

myLiftA3 :: MyApplicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
myLiftA3 f x y z = f <$$> x <**> y <**> z

(*>>) :: MyApplicative f => f a -> f b -> f b
x *>> y = (const id) <$$> x <**> y

(<<*) :: MyApplicative f => f a -> f b -> f a
x <<* y = const <$$> x <**> y

Task 5: Instances

instance MyApplicative MyMaybe where ...
instance MyApplicative (MyEither e) where ...
instance MyApplicative MyList where ...  -- All combinations!
instance MyApplicative ((->) r) where ...  -- Reader

Task 6: ZipList Alternative

newtype MyZipList a = MyZipList { getMyZipList :: MyList a }

-- Applicative that zips rather than taking all combinations
instance MyApplicative MyZipList where ...

Task 7: Law Verification

prop_applicativeIdentity :: (MyApplicative f, Eq (f a)) => f a -> Bool
prop_applicativeIdentity v = (myPure id <**> v) == v

prop_applicativeHomomorphism :: (MyApplicative f, Eq (f b))
                             => Fun a b -> a -> Bool
prop_applicativeHomomorphism (Fn f) x =
  (myPure f <**> myPure x) == (myPure (f x) :: f b)

prop_applicativeInterchange :: (MyApplicative f, Eq (f b))
                            => f (Fun a b) -> a -> Bool
prop_applicativeInterchange u y =
  (u' <**> myPure y) == (myPure ($ y) <**> u')
  where u' = fmap applyFun u

3.3 Phase 3: Monad Instances (Days 8-12)

Task 8: MyMonad Class

class MyApplicative m => MyMonad m where
  (>>>=) :: m a -> (a -> m b) -> m b
  myReturn :: a -> m a
  myReturn = myPure

-- Derived operations
(>>>) :: MyMonad m => m a -> m b -> m b
m >>> n = m >>>= \_ -> n

myJoin :: MyMonad m => m (m a) -> m a
myJoin mm = mm >>>= id

(=<<<) :: MyMonad m => (a -> m b) -> m a -> m b
(=<<<) = flip (>>>=)

-- Kleisli composition
(>==>) :: MyMonad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >==> g = \a -> f a >>>= g

Task 9: Instances

instance MyMonad MyMaybe where ...
instance MyMonad (MyEither e) where ...
instance MyMonad MyList where ...
instance MyMonad ((->) r) where ...  -- Reader

Task 10: Reader and State

newtype MyReader r a = MyReader { runMyReader :: r -> a }
newtype MyState s a = MyState { runMyState :: s -> (a, s) }

instance MyFunctor (MyReader r) where ...
instance MyApplicative (MyReader r) where ...
instance MyMonad (MyReader r) where ...

instance MyFunctor (MyState s) where ...
instance MyApplicative (MyState s) where ...
instance MyMonad (MyState s) where ...

-- Reader operations
myAsk :: MyReader r r
myLocal :: (r -> r) -> MyReader r a -> MyReader r a

-- State operations
myGet :: MyState s s
myPut :: s -> MyState s ()
myModify :: (s -> s) -> MyState s ()

Task 11: Law Verification

prop_monadLeftIdentity :: (MyMonad m, Eq (m b)) => a -> Fun a (m b) -> Bool
prop_monadLeftIdentity a (Fn f) = (myReturn a >>>= f) == f a

prop_monadRightIdentity :: (MyMonad m, Eq (m a)) => m a -> Bool
prop_monadRightIdentity m = (m >>>= myReturn) == m

prop_monadAssociativity :: (MyMonad m, Eq (m c))
                        => m a -> Fun a (m b) -> Fun b (m c) -> Bool
prop_monadAssociativity m (Fn f) (Fn g) =
  ((m >>>= f) >>>= g) == (m >>>= (\x -> f x >>>= g))

3.4 Phase 4: Practical Applications (Days 13-14)

Task 12: Validation

-- Applicative that accumulates errors
newtype MyValidation e a = MyValidation (MyEither (MyList e) a)

-- Note: This is Applicative but NOT a valid Monad!
instance Semigroup e => MyApplicative (MyValidation e) where ...

-- Use case:
data PersonError = NameTooShort | AgeTooLow | EmailInvalid

validatePerson :: String -> Int -> String -> MyValidation PersonError Person

Task 13: Parser

newtype MyParser a = MyParser { runMyParser :: String -> MyMaybe (a, String) }

instance MyFunctor MyParser where ...
instance MyApplicative MyParser where ...
instance MyMonad MyParser where ...

-- Primitive parsers
myChar :: Char -> MyParser Char
myString :: String -> MyParser String
mySatisfy :: (Char -> Bool) -> MyParser Char

-- Combinators
myMany :: MyParser a -> MyParser (MyList a)
myMany1 :: MyParser a -> MyParser (MyList a)
mySepBy :: MyParser a -> MyParser sep -> MyParser (MyList a)

3.5 Deliverables

1. Library modules with all type classes and instances
2. Property tests for all laws
3. Example applications (validation, parsing, state machine)
4. Documentation with law proofs (can be informal)

---

4. Solution Architecture

4.1 Module Organization

src/
  MyPrelude/
    Functor.hs      -- MyFunctor class and instances
    Applicative.hs  -- MyApplicative class and instances
    Monad.hs        -- MyMonad class and instances
    Reader.hs       -- MyReader type
    State.hs        -- MyState type
    Validation.hs   -- MyValidation type
    Parser.hs       -- MyParser type
  MyPrelude.hs      -- Re-exports

test/
  Laws/
    FunctorLaws.hs
    ApplicativeLaws.hs
    MonadLaws.hs
  Instances/
    MaybeSpec.hs
    EitherSpec.hs
    ListSpec.hs
    ReaderSpec.hs
    StateSpec.hs

examples/
  ValidationExample.hs
  ParserExample.hs
  StateExample.hs

4.2 Implementation Order

1. Functor first: It’s the simplest and required by others
2. Applicative second: Requires Functor, required by Monad
3. Monad third: The full power
4. Derived operations: Build on the core
5. Practical types: Reader, State, Validation, Parser

4.3 Key Implementation Insights

For List Applicative

-- All combinations (non-determinism)
instance MyApplicative MyList where
  myPure x = MyCons x MyNil
  fs <**> xs = myFlatMap (\f -> myFmap f xs) fs

For Reader

-- The key insight: a Reader is a function
instance MyMonad (MyReader r) where
  MyReader ra >>>= f = MyReader $ \r ->
    let a = ra r
        MyReader rb = f a
    in rb r

For State

-- The key insight: State threads the state through
instance MyMonad (MyState s) where
  MyState sa >>>= f = MyState $ \s ->
    let (a, s') = sa s
        MyState sb = f a
    in sb s'

---

5. Implementation Guide

5.1 Phase 1 Milestones

Milestone 1.1: MyFunctor class defined

• Class compiles
• Works with any * -> * type

Milestone 1.2: Basic instances

• Maybe, Either, List work
• Laws verified by tests

Milestone 1.3: Function instance

• (->) r as Functor (composition!)
• Understand Reader pattern emerges

5.2 Phase 2 Milestones

Milestone 2.1: MyApplicative class

• Extends MyFunctor
• Both pure and <*> defined

Milestone 2.2: Maybe and Either

• Short-circuit on Nothing/Left
• Laws verified

Milestone 2.3: List Applicative

• All combinations behavior
• Understand non-determinism interpretation

Milestone 2.4: ZipList

• Alternative Applicative for lists
• Demonstrate multiple valid instances

5.3 Phase 3 Milestones

Milestone 3.1: MyMonad class

• Extends MyApplicative
• Bind and return defined

Milestone 3.2: Core instances

• Maybe, Either, List complete
• Laws verified

Milestone 3.3: Reader Monad

• Wrap function type
• Implement ask, local
• Practical example

Milestone 3.4: State Monad

• Wrap state transformer
• Implement get, put, modify
• Stack machine example

5.4 Hints

Hint 1: Derive fmap from Applicative

myFmap f x = myPure f <**> x

This must be consistent! Verify with tests.

Hint 2: Derive (<*>) from Monad

mf <**> mx = mf >>>= \f -> mx >>>= \x -> myReturn (f x)

Again, must be consistent.

Hint 3: Join and Bind

They’re interderivable:

myJoin mm = mm >>>= id
m >>>= f = myJoin (myFmap f m)

Hint 4: Reader is just function

-- Reader r a is isomorphic to (r -> a)
-- ask = id
-- local f m = m . f

Hint 5: State threads state

Think of State s a as: “Give me a state, I’ll give you a value and a new state.”

-- State s a ~ (s -> (a, s))
-- get = \s -> (s, s)
-- put s' = \_ -> ((), s')

---

6. Testing Strategy

6.1 Law Testing with QuickCheck

-- Generic law tests parameterized by type
testFunctorLaws :: forall f a b c.
  (MyFunctor f, Eq (f a), Eq (f c), Arbitrary (f a), Show (f a))
  => Proxy f -> Proxy a -> Proxy b -> Proxy c -> Spec
testFunctorLaws _ _ _ _ = describe "Functor laws" $ do
  it "identity" $ property (prop_functorIdentity @f @a)
  it "composition" $ property (prop_functorComposition @f @a @b @c)

6.2 Specific Instance Tests

describe "MyMaybe Monad" $ do
  it "binds Just correctly" $
    (MyJust 3 >>>= \x -> MyJust (x + 1)) `shouldBe` MyJust 4

  it "binds Nothing correctly" $
    (MyNothing >>>= \x -> MyJust (x + 1)) `shouldBe` MyNothing

  it "sequences correctly" $
    (MyJust 3 >>> MyJust 4) `shouldBe` MyJust 4

6.3 Integration Tests

describe "Reader monad" $ do
  it "provides environment" $ do
    let comp = myAsk >>>= \r -> myReturn (r + 1)
    runMyReader comp 5 `shouldBe` 6

  it "local modifies environment" $ do
    let comp = myLocal (+10) myAsk
    runMyReader comp 5 `shouldBe` 15

describe "State monad" $ do
  it "threads state correctly" $ do
    let comp = myGet >>>= \n -> myPut (n + 1) >>> myGet
    runMyState comp 0 `shouldBe` (1, 1)

6.4 Property Tests for Kleisli Composition

prop_kleisliAssociative :: (MyMonad m, Eq (m d))
  => Fun a (m b) -> Fun b (m c) -> Fun c (m d) -> a -> Bool
prop_kleisliAssociative (Fn f) (Fn g) (Fn h) a =
  ((f >==> g) >==> h) a == (f >==> (g >==> h)) a

---

7. Common Pitfalls

7.1 Wrong Applicative for Either

Wrong (stops at first error):

instance MyApplicative (MyEither e) where
  myPure = MyRight
  MyLeft e <**> _ = MyLeft e  -- Doesn't try second!
  _ <**> MyLeft e = MyLeft e
  MyRight f <**> MyRight x = MyRight (f x)

This is correct for Either but loses information. If you want to accumulate errors, use Validation.

7.2 Confusing Applicative and Monad

This needs Monad:

-- We need the result of the first to decide what to do
process :: MyMaybe Int -> MyMaybe Int
process mx = mx >>>= \x ->
  if x > 0
    then MyJust (x * 2)
    else MyNothing

This only needs Applicative:

-- Both computations are independent
combine :: MyMaybe Int -> MyMaybe Int -> MyMaybe Int
combine mx my = (+) <$$> mx <**> my

7.3 State Threading Errors

Wrong (uses same state twice):

instance MyApplicative (MyState s) where
  MyState sf <**> MyState sa = MyState $ \s ->
    let (f, _)  = sf s   -- Ignores new state!
        (a, s') = sa s   -- Uses original state!
    in (f a, s')

Right:

instance MyApplicative (MyState s) where
  MyState sf <**> MyState sa = MyState $ \s ->
    let (f, s')  = sf s
        (a, s'') = sa s'  -- Uses updated state
    in (f a, s'')

7.4 Reader vs State Confusion

• Reader: Read-only environment (configuration, dependencies)
• State: Mutable state (counters, accumulators)

If you find yourself wanting to “update” the Reader environment, you probably want State.

7.5 Forgetting the Laws

Instances that don’t satisfy the laws will behave unexpectedly:

-- If left identity fails:
return a >>= f /= f a
-- Code that relies on this equivalence will break!

Always verify your instances satisfy the laws.

---

8. Extensions and Challenges

8.1 Basic Extensions

1. MonadFail: Handle pattern match failures
2. Alternative/MonadPlus: Add choice (<|>) and failure (empty)
3. MonadFix: Fixed points in monadic computations

8.2 Advanced Extensions

1. Monad Transformers: Stack monads (covered in Project 9)
2. Free Monads: Separate syntax from interpretation (covered in Project 12)
3. Comonads: The dual of monads (extend, extract)
4. Arrows: Generalization of functions with effects

8.3 Research Topics

1. Effect Systems: Algebraic effects and handlers
2. Selective Functors: Between Applicative and Monad
3. Indexed Monads: State types that change
4. Graded Monads: Track effect levels in types

---

9. Real-World Connections

9.1 Monads in Other Languages

Language	Monad Support
Scala	for comprehensions, flatMap
F#	Computation expressions
OCaml	let* syntax (4.08+)
Rust	? operator for Result, no general abstraction
JavaScript	Promise.then (monad-like, not lawful)
C#	LINQ (query syntax), async/await
Python	No built-in, libraries exist
Swift	Optional chaining (limited)

9.2 Industry Patterns

• Error Handling: Either/Result for explicit errors (Rust, Haskell)
• Async: Promise/Future/Task (JS, Scala, C#)
• Dependency Injection: Reader pattern
• Configuration: Reader + Environment types
• Parsing: Parser combinators (parsec, megaparsec)
• State Machines: State monad pattern

9.3 When to Use What

Situation	Abstraction
Transform values in containers	Functor
Combine independent effects	Applicative
Validate multiple things	Applicative + Validation
Chain dependent operations	Monad
Read-only configuration	Reader
Mutable state	State
Side effects	IO

---

10. Interview Questions

After completing this project, you should be able to answer:

1. What is a Functor and what are its laws?
   • A type constructor with fmap
   • Identity: fmap id = id
   • Composition: fmap (f . g) = fmap f . fmap g
   • Preserves structure while transforming contents
2. What is the difference between Functor, Applicative, and Monad?
   • Functor: map function over structure
   • Applicative: apply wrapped function to wrapped value
   • Monad: chain operations where later depends on earlier
   • Each adds power; use the weakest sufficient
3. When would you use Applicative over Monad?
   • When computations are independent
   • When you want to accumulate errors
   • When you might want parallelism
   • When the structure is known statically
4. Explain the Reader monad.
   • Represents computations that read from an environment
   • ask retrieves the environment
   • local runs with a modified environment
   • Used for configuration, dependency injection
5. Explain the State monad.
   • Represents computations that modify state
   • get retrieves current state
   • put sets new state
   • Threads state through sequential operations
6. What are the monad laws and why do they matter?
   • Left identity: return a >>= f = f a
   • Right identity: m >>= return = m
   • Associativity: (m >>= f) >>= g = m >>= (\x -> f x >>= g)
   • Ensure sequencing is predictable and refactoring is safe
7. How do Promises/async-await relate to monads?
   • Promise.then is like bind
   • async/await is like do-notation
   • Not lawful (exceptions, eager evaluation)
   • Same intuition: sequencing effectful operations

---

11. Self-Assessment Checklist

Functor

• Can implement Functor for any container type
• Can state and verify the Functor laws
• Understand (->) r as a Functor
• Can use <$> fluently

Applicative

• Can implement Applicative for Maybe, Either, List
• Understand the difference between List and ZipList
• Can use <*> and liftA2 fluently
• Can explain when Applicative suffices over Monad

Monad

• Can implement Monad for Maybe, Either, List
• Can state and verify the Monad laws
• Understand the relationship between >>= and join
• Can use do-notation effectively

Reader and State

• Can implement Reader from scratch
• Can implement State from scratch
• Know when to use each
• Can use ask, local, get, put

Laws and Theory

• Can prove instances satisfy laws (informally)
• Understand why laws matter for refactoring
• Can explain the categorical perspective (high level)
• Understand Kleisli composition

Practical Application

• Can build a Validation Applicative
• Can build a Parser Monad
• Can refactor code to use these abstractions
• Know when to use which abstraction

---

12. Resources

Primary Texts

1. “Haskell Programming from First Principles” by Allen & Moronuki
   • Chapter 16: Functor
   • Chapter 17: Applicative
   • Chapter 18: Monad
   • Excellent exercises, thorough explanations
2. “Programming in Haskell” by Graham Hutton
   • Chapter 12: Monads and More
   • Concise and mathematical
3. “Learn You a Haskell for Great Good!” by Miran Lipovaca
   • Chapter 11: Functors, Applicatives, and Monoids
   • Chapter 12: A Fistful of Monads
   • Visual and fun

Essential Online Resources

1. Typeclassopedia
   • Comprehensive guide to Haskell type classes
   • The definitive reference
2. All About Monads
   • Tutorial with many examples
   • Good for building intuition
3. Functors, Applicatives, and Monads in Pictures
   • Visual explanations
   • Great for intuition

Papers

1. “Applicative Programming with Effects” by McBride and Paterson
   • The original Applicative paper
   • Introduces idiom brackets (Applicative syntax)
2. “Monads for Functional Programming” by Philip Wadler
   • Classic introduction to monads
   • Excellent examples
3. “The Essence of the Iterator Pattern” by Gibbons and Oliveira
   • Relates iterators to Applicative/Traversable
   • Deep connections

Category Theory (Optional)

1. “Category Theory for Programmers” by Bartosz Milewski
   • Free online book
   • Connects theory to programming
2. nLab
   • Rigorous mathematical definitions
   • For those who want the full picture

Video Lectures

1. Haskell MOOC (University of Helsinki)
   • Weeks 4-5 cover these topics
   • Exercises included
2. Bartosz Milewski’s Category Theory (YouTube)
   • 3-part lecture series
   • Excellent for categorical perspective

---

“Once you understand monads, you lose the ability to explain them to others.” – The Monad Tutorial Fallacy

But that’s okay. After this project, you won’t need an explanation–you’ll have built them yourself.