Reverse Maybe as Another Applicative-not-Monad

Yuriy Syrovetskiy — Wed, 22 Feb 2017 08:52:22 +0000

Applicative vs. Monad

Every time somebody wants to show the difference between Applicative and Monad, they always pick ZipList, which is an Applicative but not a Monad.

I recently found yet another example which is less common.

First'

Consider the following type:

newtype First' a b = First' (Maybe a)

It is bivariant (both covariant and contravariant) in its tail argument b. Compiler sees this clearly:

{-# LANGUAGE DeriveFunctor #-}
newtype First' a b = First' (Maybe a)
    deriving (Functor)

I leave writing non-derived Functor instance to you as an excercise.

Please note that this functor ignores its argument completely, unlike pure Maybe.

The name First' isn't a coincidence. We're going to use semantics of Data.Monoid.First here. Namely, First allows to mappend two Maybe values without descending into them:

λ> Nothing <> Just 'A'

<interactive>:
    No instance for (Monoid Char) arising from a use of ‘<>'
    ...

λ> First Nothing <> First (Just 'A')
First {getFirst = Just 'A'}

Monoid

Let's write Monoid for our First' with the same semantics:

instance Monoid (First' a b) where
    mempty = First' Nothing
    x@(First' (Just _)) `mappend` _ = x
    _ `mappend` y = y

Let's try it in repl:

λ> First' Nothing <> First' (Just 'A')
First' (Just 'A')

It works!

Applicative

Let's go next level. We're going to write Applicative instance with this semantics. We also can reuse monoid instance.

instance Applicative (First' a) where
    pure _ = First' Nothing
    First' x <*> First' y = First' x <> First' y

Check:

λ> First' Nothing <*> First' (Just 'A')
First' (Just 'A')
λ> First' Nothing *> First' (Just 'A')
First' (Just 'A')

Reverse Maybe

Why this is a reverse Maybe?

Maybe semantics may be expresses as:

Nothing -> failure, stop
Just x -> continue with x

λ> Nothing *> Just 1
Nothing
λ> Just 1 *> Just 2
Just 2

First' semantics is:

Nothing -> continue
Just x -> result is x, stop

λ> First' Nothing *> First' (Just 2)
First' (Just 2)
λ> First' (Just 1) *> First' (Just 2)
First' (Just 1)

Monad?

First' doesn't seem to be a Monad though. But I'm too lazy to prove it. If you can provide such a proof, please let me take a look at it.

Const

Vladislav Zavialov noted that First' is merely

type First' a b = Const (First a) b

where First is from Data.Monoid.

Indeed,

λ> Const (First Nothing) *> Const (First (Just 2))
Const (First {getFirst = Just 2})
λ> Const (First (Just 1)) *> Const (First (Just 2))
Const (First {getFirst = Just 1})

And Const is yet another interesting Applicative-not-Monad example.

Hi, I'm Yuriy Syrovetskiy

Yuriy Syrovetskiy — Thu, 16 Feb 2017 17:02:05 +0000

I have been coding for 17 years.

You can find me on GitHub as cblp

I live in Moscow, Russia.

I work for Kaspersky Lab.

I mostly program in these languages: Haskell and C.

I am currently learning more about distributed systems.

Nice to meet you.

Forem: Yuriy Syrovetskiy