Let’s dive a bit into a little Haskell journey to prove that the well known Option data type, can behave like a Monad, we’ll also see how it relates to a Functor, Applicative, and more.

What is a monad?

For practical purposes, let’s just see what it does. Then try to define it later.

Step 1: Defining the Option Type

To begin, we define our type:

data Option a = Some a | None
  deriving (Show, Eq)

This is a simple “optional” type. If you’ve worked with Maybe, this will be very familiar. Option can either hold a value (Some a) or be empty (None).

Now, let’s prove how we can make it fit into all these cool Haskell type classes like Functor, Applicative, Monad, and others.

Step 2: Option as a functor

A Functor is something that you can “map” over. In Haskell, the fmap function applies a function to the contents of the structure.

instance Functor Option where
  fmap f (Some a) = Some (f a)
  fmap _ None = None

Easy enough, right? Here is a concrete example:

fmap (+60) (Some 40)  -- Output: Some 100
fmap (+60) None       -- Output: None

Step 3: Option as an Applicative

Next, let’s define it as an Applicative. This allows us to apply functions that are themselves inside Option. Here’s how we define it:

instance Applicative Option where
  pure = Some
  Some f <*> Some a = Some (f a)
  None <*> _ = None
  _ <*> None = None

• The pure function takes a value and wraps it in Some.
• The binary operator <*> is for applying functions that are wrapped in Some.
• If either the function or the value is None, the result is None.

Example:

Some (+60) <*> Some 40           -- Output: Some 100
((+) <$> Some 60) <*> Some 40    -- Output: Some 100
(+) <$> Some 60 <*> Some 40      -- Output: Some 100
(+) <$> Some 60 <*> None         -- Output: None

This is handy for combining multiple computations.

Step 4: Option as a Semigroup and Monoid

Semigroup is about combining things. For Option, we define how to combine two Options using the <> operator:

instance (Semigroup a) => Semigroup (Option a) where
  Some a <> Some b = Some (a <> b)
  None <> _ = None
  _ <> None = None

If we have two Some values, we combine them using <> from the underlying type (like combining lists or numbers). If either is None, the result is None.

Monoid extends Semigroup by introducing an identity element. Here’s the Monoid instance:

instance (Monoid a) => Monoid (Option a) where
  mempty = Some mempty

The identity element for Option is Some mempty. If we’re dealing with strings, for example, mempty would be the empty string.

Some "Hello" <> Some "World"  -- Output: Some "HelloWorld"

Step 5: Option as a Monad

Finally, we reach the Monad! A Monad is a structure that lets you chain computations together, literally.

It’s just a matter of defining its operators.

Chaining is done by using the bind operator >>=.

instance Monad Option where
  None >>= _ = None
  Some a >>= f = f a

if Option is None, we stop there. But if it’s Some a, we apply the function f to the value a.

Some 60 >>= (\x -> Some (x + 40))  -- Output: Some 100
None >>= (\x -> Some (x + 40))     -- Output: None

It also enables the do notation, which makes any Haskell program behave similarly to imperative programs.

example :: Option Int
example = do
  x <- Some 60
  Some (x + 40)

This is where Option shines as a Monad, as it allows you to chain computations that might fail, without having to check for None at every step.

Step 6: Going beyond with Alternative, MonadFail and MonadPlus

We can also add some extra powers to Option through Alternative, MonadFail and MonadPlus.

These give us ways to combine or recover from failures:

instance Alternative Option where
  empty = None
  None <|> b = b
  a <|> _ = a

instance MonadFail Maybe where
  fail _ = Nothing

instance MonadPlus Option where
  mzero = None
  None `mplus` b = b
  a `mplus` _ = a

This means that if the first computation fails (None), we can try the second one using <|> or mplus.

Example:

Some 40 <|> None  -- Output: Some 40
None <|> Some 60  -- Output: Some 60

If you’ve looked into parser combinators, there is always an abstraction that implements Alternative.

-- Taken from https://github.com/futureg-lab/fg-bytegen/blob/main/src/TextProcessor.hs
parseLiteral :: Parser FgValue
parseLiteral =
  let underscore = char '_'
   in do
        head <- letter <|> underscore -- !
        tail <- many (letter <|> digit <|> underscore) -- !
        let literal = head : tail
        return $ case literal of
          "false" -> Bool False
          "true" -> Bool True
          "null" -> NullValue
          _ -> Literal literal

-- guess what string the above accepts?

MonadFail is useful when paired with the do notation..

exampleWithMonadFail :: Option Int
exampleWithMonadFail = do
  x <- Some 5
  y <- fail "Something went wrong!"
  return (x + y)  -- This won't be evaluated since y failed

MonadPlus can help manage multiple potential failure points in computations, as it allows for a form of “fallback” behavior, it is quite literally the same as how we defined our Alternative instance if you look closely, so the value is in the semantics. You can refer to this for more explanations.

Some 1 `mplus` None `mplus` Some 3    -- Output: Some 1
None `mplus` None `mplus` Some 3      -- Output: Some 3

Step 7: Ordering with Ord

Finally, we can even sort Option values if the wrapped type supports ordering:

instance (Ord a) => Ord (Option a) where
  compare (Some a) (Some b) = compare a b
  compare None None = EQ
  compare None (Some _) = LT
  compare (Some _) None = GT

This defines how Option values compare to each other. If both are None, they’re equal. Otherwise, None is less than any Some value.

Examples:

compare (Some 40) (Some 30)   -- Output: LT
compare None (Some 40)        -- Output: LT
compare (Some 40) None        -- Output: GT

import Data.List (sort)

sort [Some 9, None, Some 6]   -- Output: [None,Some 6,Some 9]

Exercices

Try to understand why the code bellow evaluates to Some "prefonetwo".

example :: Option String
example =
  let a = Some "pref" <> Some "one"
      b = fail "bad" <|> mzero <|> pure "two"
   in (++) <$> a <*> b

Define “monad”

“In functional programming, a monad is a structure that combines program fragments (functions) and wraps their return values in a type with additional computation” - Wikipedia

“A monad is a monoid in the category of endofunctors” - Memes

“All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor” - Saunders Mac Lane

Formal definitions are nice but if you have carefully followed through, you might have already intuitively made sense of all of the stuff above! Why? Because they are just fancy ways to define “trait"s to a type, or implementing “interfaces” and in our case, these “interfaces” just so happen to have “mathy” names and property.

First, let’s translate the terms from Saunders Mac Lane definition (the source of the Monad meme).

1. Monoid = structure with binary operation and an identity element.
2. Endofunctors = functors from a category to itself.
3. The product × = composition of functors.
4. The identity set = identity functor.

Practically speaking you are only required to understand the following:

Category: A collection of objects and morphisms (arrows) between them. Arrows link one object to another, and they must follow two rules:

1. Composition: If f: A -> B and g: B -> C, we can compose them to get g ∘ f: A -> C.
2. Identity: Every object has an identity arrow, id_A: A -> A, which acts as a “do-nothing” arrow.

Category := Objects + Arrows between them

Functor: A mapping between two categories.

A functor maps:

1. Objects in one category to objects in another category.
2. Arrows (morphisms) between objects in the first category to arrows between objects in the second category.

Functors must preserve:

1. Identity: Identity arrows in the first category must map to identity arrows in the second category.
2. Composition: If g ∘ f is a composition of arrows in the first category, then the functor must map this to the composition of the corresponding arrows in the second category.

For example, you want to double each number. A functor (like the list type) allows you to apply a function to each element without changing the overall structure of the list:

numbers = [1, 2, 3]
fmap (*2) numbers        -- Output: [2, 4, 6]

-- With our custom Option
fmap (*2) (Some 11)      -- Output: Some 22

So, in a way…

Monads are basically just a special kind of Functor.

Option is a Functor, as it preserves structure, composability of functions (functions can “penetrate” within it) and maps other categories (data types) to itself.

Option is a monad, identity of the wrapped type is preserved as demonstrated with (Some . id) 3 == (id . Some) 3, and composition is defined with the bind function (>>=).

Let’s review the Monad definition again..

instance Monad Option where
  None >>= _ = None
  Some a >>= f = f a

And we didn’t cover this but in Haskell, the Functor class (not to be confused with instance) for Monad is defined as

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

class Functor m => Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

A monad must implement the fmap function from the Functor type class, and it typically does this using the bind operator (>>=) and the return function.

Another example, List is a Monad in Haskell:

fmap :: (a -> b) -> [a] -> [b]

You can also check other implementations, its MonadPlus for example is the “same” as doing concat <> (from its Semigroup definition) or ++.

[] `mplus` [1,2] `mplus` [3,4,5] `mplus` [] `mplus` [6,7]                      -- Output: [1,2,3,4,5,6,7]
[] `mplus` [Some 1] `mplus` [[Some 2],Some 3] `mplus` [] `mplus` [None, None]  -- Output: [Some 1,Some 2,Some 3,None,None]