Monad: effectful programming

Frame of mind

What is a number? You normally don't ask that, nor do you answer it directly. Perhaps you answer indirectly: examples, how to use numbers, how to work with numbers, some properties (axioms and theorems) like how addition is commutative. And lastly, you learned numbers by practice.

Likewise with vector spaces. Remember those? Your best bet at teaching or learning them is again through examples, applications, properties, and ultimately practice.

The same approach is best for monad. Don't seek a direct answer to “what is a monad?”. Do look for and work out more examples, applications, properties. If you can write correct code, fix incorrect code, and predict the outcome of other people's code, you already understand more than you think, even if you can't write a sounds-good essay.

Practice. 40 hours a day.

Parameterized “container” types as effect types

I now want you to think of [], Maybe, Either e as types of effects or effectful programs, not always as types of data structures.

“Effect” is very broad and usually not given a precise definition, but if you know the phrase “function with a side-effect”, that's the idea. In the Haskell culture, it usually means what mathematical functions don't normally do, e.g.: no answer, multiple answers, accessing state variables, performing I/O—the latter two lead to getting different answers at different times.

f :: Int -> String in Haskell means that f 4 :: String is the same string every time, without effect. If some specific kind of effect is desired, we make a parameterized type E to represent it—e.g., Maybe or [] in this section—and change types to f :: Int -> E String, so f 4 :: E String does not have to give the same string every time, instead just the same “effectful behaviour” every time (but you expect this anyway).

It suffices to focus on “E String” (so without “Int ->”) and think of it as the type of effectful programs that give string answers. E.g., if m1, m2 :: Maybe String, think of them as two programs that give string answers (the effect: could fail).

From this perspective, the methods of Functor, Applicative, and later Monad are connectives—combining basic effectful programs into complex ones. E.g., liftA2 (++) m1 m2 combines m1 and m2.

Maybe: one answer or failure

Suppose I have:

recipMay :: Double -> Maybe Double
recipMay a | a == 0 = Nothing
           | otherwise = Just (1 / a)    -- or: pure (1 / a)

Think of recipMay x :: Maybe Double as a program that may answer a Double or flag failure, depending on x. It computes 1/x iff sensible to.

If I want 2 + 1/x while admitting that 1/x may fail, I use fmap (\r -> 2 + r) (recipMay x).

If I want 1/x + 1/y while admitting that 1/x or 1/y may fail, I use liftA2 (+) (recipMay x) (recipMay y).

Lastly, pure x is a program that simply says “the answer is x”, so it is Just x here.

twoPlusRecip :: Double -> Maybe Double
twoPlusRecip x = fmap (\r -> 2 + r) (recipMay x)

addRecips :: Double -> Double -> Maybe Double
addRecips x y = liftA2 (+) (recipMay x) (recipMay y)

Either e is similar, plus the extra type e (field type of Left) to carry the reason for failure.

[]: multiple answers

Suppose I have:

sqrts :: Double -> [Double]
sqrts a | a < 0 = []
        | a == 0 = [0]    -- or: pure 0
        | otherwise = [- sqrt a, sqrt a]

Think of sqrts x :: [Double] as a program that has up to 2 answers, depending on x. It computes real-valued ±√x whenever sensible (x≥0).

If I want 2 ± √x (up to 2 answers), I use fmap (\r -> 2 + r) (sqrts x).

If I want ±√x ± √y (up to 4 answers), I use liftA2 (+) (sqrts x) (sqrts y).

Lastly, pure x is a program that simply says “1 answer, it's x”, so it is [x] here.

addSqrts :: Double -> Double -> [Double]
addSqrts x y = liftA2 (+) (sqrts x) (sqrts y)

A related example shows a limitation of the Applicative methods and a teaser preview of Monad. If I want ±√(2 + ±√x), Applicative methods don't help me. Reason: in liftA2 f foo bar, bar is not given an answer from foo, but my outer ±√ needs to see an answer from the inner ±√. Monad methods will let me do that.

Generally speaking

Some instances of Applicative are container data structures, some others are not (e.g., the State monad shown later), but in most cases they can be seen as expressing some kinds of effects. From this perspective, with a bit of handwaving:

fmap f foo builds upon foo, the add-on being: using f to convert foo's answers.

liftA2 op foo bar composes foo and bar, using op to combine their respective answers.

pure x is a program that simply says “the answer is x, no effect”. (“Pure” is a way to say “effectless” because historically “impure” is a way to say “effectful”.)

Monad

Functor and Applicative methods help you compose smaller programs into bigger ones, but they have a limitation: In liftA2 f foo bar, bar's answer(s) or effect (e.g., how many answers) cannot depend on foo's answer(s).

What if you want to allow the second program to take a peek at an answer from the first program before deciding what to do? Like:

bind :: E a -> (a -> E b) -> E b

so “bind foo quaz” means a composite program that runs foo, then passes its answer(s), if any, to quaz. You may think of quaz as a callback.

bind_Maybe :: Maybe a -> (a -> Maybe b) -> Maybe b
bind_Maybe Nothing k = Nothing
bind_Maybe (Just a) k = k a

bind_Either :: Either e a -> (a -> Either e b) -> Either e b
bind_Either (Left e) _ = Left e
bind_Either (Right a) k = k a

bind_List :: [a] -> (a -> [b]) -> [b]
bind_List xs k = concat (map k xs)
-- Explanation: map k xs :: [[b]] is almost there, use concat to flatten

Example: ±√(2 + ±√x)

sqrtsTwoPlusSqrts :: Double -> [Double]
sqrtsTwoPlusSqrts x = bind_List (sqrts x) (\r -> sqrts (2 + r))

Example application: Compute all permutations of an input list.

-- All permutations of the input.
permsV1 :: Eq a => [a] -> [[a]]
permsV1 xs = permsAddV1 xs []

-- Helper: permsAdd xs ys = all permutations of xs prepended to ys
-- E.g.,
-- permsAdd [1,2] [6,4,7] = [2:1:[6,4,7], 1:2:[6,4,7]]
-- permsAdd [] [6,4,7] = [[6,4,7]]
permsAddV1 :: Eq a => [a] -> [a] -> [[a]]
permsAddV1 [] ys = [ys]
permsAddV1 xs ys = bind_List xs (\x -> permsAddV1 (delete x xs) (x : ys))
-- For each x in xs, I want to delete x from xs, add x to ys, and recurse.
-- OR:
-- Non-deterministically choose x from xs, ... ditto.

And there is a class for that too!

class Applicative f => Monad f where
    return :: a -> f a
    (>>=) :: f a -> (a -> f b) -> f b
    (>>) :: f a -> f b -> f b
    -- (>>) has Default implementation:
    foo >> bar = foo >>= \_ -> bar
    -- Handy when you don't need foo's answer, only its effect.
    -- We call this operator "then".

“return” means the same as “pure”. It is here for historical reasons (because Applicative is more recent). Do not think in terms of control flow—“return” does not exit anything.

More explanation for >>= (you can say “bind”): Suppose E is a Monad instance, and

foo :: E X
quaz :: X -> E Y
foo >>= quaz :: E Y

1. Think of E as an abstract type, so that there is no direct way to ask “what's foo's answer(s)?”. But >>= is tailor-made for E and has access to those answers.

2. Think of quaz as a callback. >>= will call quaz with an answer, if any. So you don't ask “how to extract the answer(s) from foo?”. You provide a callback for receiving and processing an answer. They call your callback whenever an answer is ready. “Don't ask us. We'll call you.”

My ±√(2 + ±√x) and permutation examples using Monad methods:

sqrtsTwoPlusSqrtsV2 :: Double -> [Double]
sqrtsTwoPlusSqrtsV2 x = sqrts x >>= \r -> sqrts (2 + r)

permsV2 :: Eq a => [a] -> [[a]]
permsV2 xs = permsAddV2 xs []

permsAddV2 :: Eq a => [a] -> [a] -> [[a]]
permsAddV2 [] ys = return ys
permsAddV2 xs ys = xs >>= \x -> permsAddV2 (delete x xs) (x : ys)

The Monad methods satisfies these axioms:

-- 1L. Monad left identity
return x >>= k  =  k x

-- 1R. Monad right identity
foo >>= \x -> return x  =  foo
foo >>=       return    =  foo

-- 2. >>= associativity
(foo >>= \x -> k1 x) >>= k2  =  foo >>= (\x -> k1 x >>= k2)
(foo >>=       k1  ) >>= k2  =  foo >>= (\x -> k1 x >>= k2)
-- (x is a fresh variable, i.e., no name clash)

Associative laws justify re-grouping. This is important for refactoring and implementing long chains by recursion.

Monad subsumes Applicative and Functor: From return and >>= we can get the methods of Applicative and Functor:

fmap f xs  =  xs >>= (\x -> return (f x))

liftA2 op xs ys  =  xs >>= (\x -> ys >>= (\y -> return (op x y)))

Monad is very important in theory, in both advanced mathematics and programming language semantics. To make a math model for a programming language, a Monad instance is carefully designed to represent the effects (e.g., if the language has exceptions, the Monad instance involves Either; if the language has state variables, we will see how to do it below), and >>= represents sequential composition. We will do this later in the course when we make toy interpreters for toy languages.

On the practical side:

• Inspired by the theoretical use for semantics, mini special-purpose languages (“embedded domain-specific languages”) are made right within Haskell by designing custom-made types to represent the desired effects or features, and implementing their Monad instances. Users then write programs by combining primitives using Monad methods (or Functor, Applicative methods).

  We will use this style for parsing later in the course.

• Taking that one step further with polymorphism, we will do dependency injection and mock testing below.

• Other languages have learned from Haskell Monad for structuring data queries (C# LINQ, see FlatMap and SelectMany), concurrency (promises in Javascript and others), generally any programming style based on chaining callbacks, which is exactly what >>= is about.

The State Monad

Or: how to fake state in functional programming / math.

Fairy tale:

I have a type “State s a”. If foo :: State Int Double for example, it means foo gives a floating point number answer, and it has access to an int state variable. So “State Int” is a parameterized type that represents stateful effects with an Int-type state.

A few basic operations are provided below. Furthemore, “State s” is an instance of Functor, Applicative, and Monad, so you have connectives to chain up those basic operations too.

-- "get" reads and returns the current value of the state variable.
get :: State s s
-- Code shown later.

-- "put s1" sets the state variable to s1.  It returns the 0-tuple because there
-- is no information to return.
put :: s -> State s ()
-- Code shown later.

-- Bridge from stateful fantasy to mathematical reality! "functionize prog s0"
-- runs prog starting with initial state value s0 and gives you the final
-- answer.  Or, turns prog into a math pure function.
functionize :: State s a -> s -> a
-- Code shown later.

Example use: Evaluate a C expression in which you have a state variable c and you can do c++ and ++c.

data CExpr = Lit Double
           | Add CExpr CExpr | Sub CExpr CExpr | Mul CExpr CExpr | Div CExpr CExpr
           | C   -- read value of c
           | CPP -- c++
           | PPC -- ++c
    deriving Show
-- e.g., (c++ + c) + (14.4 / ++c): Add (Add CPP C) (Div (Lit 14.4) PPC)
-- c is an int variable, but the whole expression is intended to be double

sampleCExpr :: CExpr
sampleCExpr = Add (Add CPP C) (Div (Lit 14.4) PPC)

evalCExpr :: CExpr -> State Int Double
evalCExpr (Lit x) = pure x
evalCExpr (Add e1 e2) = liftA2 (+) (evalCExpr e1) (evalCExpr e2)
evalCExpr (Sub e1 e2) = liftA2 (-) (evalCExpr e1) (evalCExpr e2)
evalCExpr (Mul e1 e2) = liftA2 (*) (evalCExpr e1) (evalCExpr e2)
evalCExpr (Div e1 e2) = liftA2 (/) (evalCExpr e1) (evalCExpr e2)
evalCExpr C = fmap fromIntegral get
evalCExpr CPP = get
                >>= \i -> put (i+1)
                >> pure (fromIntegral i)
evalCExpr PPC = get
                >>= \i -> put (i+1)
                >> pure (fromIntegral (i+1))

How to make the fairy tale come true:

The trick is to have a state transition function instead, like s→s, and have some starter function (funtionize) that feeds it the initial value.

Except I also want it to give an answer. So actually s→(s,a): function from old-state to pair of new-state and answer.

data State s a = MkState (s -> (s, a))

-- Unwrap MkState.
deState :: State s a -> s -> (s, a)
deState (MkState stf) = stf

functionize :: State s a -> s -> a
functionize prog s0 = snd (deState prog s0)

get :: State s s
get = MkState (\s0 -> (s0, s0))
-- old state = s0, new state = old state = s0, answer s0 too.

put :: s -> State s ()
put s = MkState (\s0 -> (s , ()))
-- ignore old state, new state = s, answer the 0-tuple ().

fmap f foo aims at performing the same state change effect as foo, but converting the answer by f.

instance Functor (State s) where
    -- fmap :: (a -> b) -> State s a -> State s b
    fmap f (MkState stf) = MkState
        (\s0 ->
           -- Goal: Like stf but use f to convert a to b
           -- old state = s0, give to stf for new state s1 and answer a
           case stf s0 of (s1, a) ->
           -- overall new state is also s1, but change answer to f a
                              (s1, f a))

testStateFunctor = deState (fmap length program) 10
  where
    program :: State Integer String
    program = MkState (\s0 -> (s0+2, "hello"))
-- should give (12, 5)

pure a aims at giving the answer a without effect, meaning no state change in this context.

liftA2 op foo bar for State aims at sequential execution of foo followed by bar. Conceptually it's function composition, but uglier because of the tuples (s,a) and (s,b), and the finishing touch of using op to combine answers.

instance Applicative (State s) where
    -- pure :: a -> State s a
    -- Goal: Give the answer a and try not to have an effect.
    -- "effect" for State means state change.
    pure a = MkState (\s0 -> (s0, a))
    -- so new state = old state

    -- liftA2 :: (a -> b -> c) -> State s a -> State s b -> State s c
    --
    -- State transition goal:
    --                  overall old state
    -- --1st-program--> intermediate state
    -- --2nd-program--> overall new state
    --
    -- (Why not the other order? Actually would be legitimate, but we usually
    -- desire liftA2's order to follow >>='s order below.)
    liftA2 op (MkState stf1) (MkState stf2) = MkState
        (\s0 ->
           -- overall old state = s0, give to stf1
           case stf1 s0 of { (s1, a) ->
           -- intermediate state = s1, give to stf2                  
           case stf2 s1 of { (s2, b) ->
           -- overall new state = s2
           -- overall answer = op a b
           (s2, op a b) }} )

testStateApplicative = deState (liftA2 (:) prog1 prog2) 10
  where
    prog1 :: State Integer Char
    prog1 = MkState (\s0 -> (s0+2, 'h'))
    prog2 :: State Integer String
    prog2 = MkState (\s0 -> (s0*2, "ello"))
-- should give (24, "hello").  24 = (10+2)*2.

foo >>= quaz for State aims at sequential execution and answer passing. Conceptually function composition on steroid, but uglier because of the (s,a) tuple and the MkState wrapper.

instance Monad (State s) where
    return = pure

    -- (>>=) :: State s a -> (a -> State s b) -> State s b
    -- Goal:
    -- 1. overall old state --1st-program--> (intermediate state, a)
    -- 2. give a and intermedate state to 2nd program.
    MkState stf1 >>= k = MkState
        (\s0 ->
           -- overall old state = s0, give to stf1
           case stf1 s0 of { (s1, a) ->
           -- k is waiting for the answer a
           --      and also the intermediate state s1
           -- technicality: "(k a) s1" is conceptually right but nominally a
           -- type error because (k a) :: State s b, not s -> (s, b)
           -- Ah but deState can unwrap! (Or use pattern matching.)
           deState (k a) s1 } )

The State Monad on its own is sometimes indispensible but not very often. But if you understand how it's done, you can combine this technique with others to make something useful, something that would be hairy otherwise. E.g, to obtain both state and failure, it's one of:

data F1 s a = MkF1 (s -> Maybe (s, a))
data F2 s a = MkF2 (s -> (s, Maybe a))

(They do have semantic difference! Exercise: What's the difference? When do you use which?)

Dependency injection, Mock testing

File format checker for my toy file format: First three characters should be A, L, newline. Version 1, to be superceded.

toyCheckV1 :: IO Bool
toyCheckV1 =
    getChar
    >>= \c1 -> getChar
    >>= \c2 -> getChar
    >>= \c3 -> return ([c1, c2, c3] == "AL\n")

How do I test this? And/Or how do I restrict it to getChar and nothing funny behind my back? Answer: Dependency injection (or is it Template method?) Several ways to do this in Haskell. Here's one: Define our own type class for the relevant, permitted operations:

class Monad f => MonadToyCheck f where
    toyGetChar :: f Char
-- Simplifying assumptions: Enough characters, no failure.  A practical version
-- should add methods for raising and catching EOF exceptions.

The checker logic should be polymorphic in that type class:

toyCheckV2 :: MonadToyCheck f => f Bool
toyCheckV2 =
    toyGetChar
    >>= \c1 -> toyGetChar
    >>= \c2 -> toyGetChar
    >>= \c3 -> return ([c1, c2, c3] == "AL\n")

Only things toyCheckV2 can do: toyGetChar, monad methods, purely functional programming. Because user chooses f. And toyCheckV2 doesn't even know what it is. All it knows is it can call toyGetChar.

Now we can instantiate in two different ways, one way for production code, another way for mock testing.

For production code:

instance MonadToyCheck IO where
    toyGetChar = getChar

realProgram :: IO Bool
realProgram = toyCheckV2

Fake news for purely functional mock testing:

data Feeder a = MkFeeder (String -> (String, a))
-- Again, simplifying assumptions etc.  But basically like the state monad, with
-- the state being what's not yet consumed in the string.

-- Unwrap MkFeeder.
unFeeder :: Feeder a -> String -> (String, a)
unFeeder (MkFeeder sf) = sf

instance Monad Feeder where
    return a = MkFeeder (\s -> (s, a))
    prog1 >>= k = MkFeeder (\s0 -> case unFeeder prog1 s0 of
                                     (s1, a) -> unFeeder (k a) s1)

instance MonadToyCheck Feeder where
    -- toyGetChar :: Feeder Char
    toyGetChar = MkFeeder (\(c:cs) -> (cs, c))

instance Functor Feeder where
    fmap f p = p >>= \a -> return (f a)

instance Applicative Feeder where
    pure a = MkFeeder (\s -> (s, a))
    pf <*> pa = pf >>= \f -> pa >>= \a -> return (f a)

testToyChecker2 :: String -> Bool
testToyChecker2 str = snd (unFeeder toyCheckV2 str)

toyTest1 = testToyChecker2 "ALhello"   -- should be False
toyTest2 = testToyChecker2 "AL\nhello" -- should be True