The IO monad has a non-strict bind

The Maybe monad has a bind function that is strict in its arguments:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

The IO monad however has a non-strict bind function:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

And so does the strict State monad:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

It's easy to see in the source code:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

To reduce m >>= k to Weak Head Normal Form, you only need to go as far as the StateT constructor; you don't need to touch any of the parameters. I suppose something similar happens with IO.

What's so strict then about the IO monad and the strict State monad? Their run functions. This:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

As opposed to this:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

Notice how in the strict case putting the expression in WHNF with seq is enough to trigger the exception.

Of course, with IO we don't have a explicit run function (one that isn't evil, I mean). We just put the IO action into main.

Notice however that even the strict State monad is not too strict:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

This doesn't trigger an exception, either:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

But this does:

	λ (undefined >>= undefined :: Maybe ()) `seq` ()
	*** Exception: Prelude.undefined
	λ (undefined >>= undefined :: IO ()) `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ (undefined >>= undefined :: State () ()) `seq` ()
	()
	m >>= k = StateT $ \ s -> do
	(a, s') <- runStateT m s
	runStateT (k a) s'
	λ import Control.Monad.State.Strict
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	*** Exception: Prelude.undefined
	λ import Control.Monad.State.Lazy
	λ runStateT (undefined >> return () :: State () ()) () `seq` ()
	()
	λ import Control.Monad.State.Strict
	λ import Debug.Trace
	λ runStateT ((trace "Hi" $ return ()) >> return undefined :: State () ()) () `seq` ()
	Hi
	()
	λ import Control.Concurrent
	λ forkIO $ return undefined
	ThreadId 534
	λ forkIO $ return $! undefined
	<interactive>: Prelude.undefined
	ThreadId 580

Some good links about laziness here, here, here, here, here and here.

Understanding representable functors

Representable functors are put to good use in the linear library, and they can be a useful tool in other contexts. Here's a (hopefully not completely misleading) post on the subject.

The general idea

Consider the functor that carries a type a to the type of infinite lists of elements of type a. Let's call that functor Stream. So Stream Bool is the type of infinite lists of boolean values, Stream Char is the type of infinitely long strings, and so on.

There is a type with which the Stream functor has a special relationship: the type ℕ of natural numbers. Think about it: any value of type Stream a can be alternately represented by a function of type ℕ -> a. To recover the stream, we just have iterate over the naturals, applying the function at each step. Conversely, we can regard a Stream a value as a "memoized" version of a ℕ -> a function. We can recover the function by indexing on the stream.

There are other functors that have a similar "special relationship" with a certain type. That type need not be ℕ. Consider the following very simple functor:

	{-# LANGUAGE DeriveFunctor #-}
	data Pair a = Pair a a deriving (Show,Functor)

This Pair functor has a special relationship with the Bool type. A value of type Pair a can be alternately represented by a function Bool -> a. Conversely, we can regard a value of type Pair a as a memoized or tabulated version of a Bool -> a function.

There seems to be a pattern here!

One more example: the Identity functor is represented by the trivial unit type (), that has only one value and carries no information. Identity a is just a, so there are no "positions" over which to "range", so to speak.

Composition, products, sums

Functors have the nice property that the composition of two functors is still a functor. We can ask ourselves if the composition of two representable functors is still representable. The answer is yes.

The composition (think of it as "nesting") of two functors is represented by the product of the representations of the original functors. Think of the type Stream (Stream a). It is like an infinite bidimensional array of a values. To index into it, we need two coordinates. So it is represented by (ℕ,ℕ).

The product of two functors is a functor as well. And the product of two representable functors is again representable! It is represented by the sum of the representations of the original functors. Supose you have a pair (Stream a, Stream a). If we want to index into it, we must first choose a side, and then drill into the stream of that side. So the product is represented by Either ℕ ℕ.

A third way of combining functors is summing them. Is a sum of representable functors representable? I don't know about the theory, but intuitively the answer seems to be no. We can't "index" on sum types, because we might attempt to target a branch that isn't there!

The Haskell implementation

The Representable typeclass can be found in module Data.Functor.Rep of the adjunctions package. It has the Distributive class as a prerrequisite. Distributive can be understood as the class of functors with a "fixed shape" whose values can be zipped together easily.

If you check the source, you'll see that the type families extension is used to associate each instance of Representable with its representation. It is instructive to explore which correspond to which. For example, Rep Identity = () as we have alredy mentioned.

You might wonder, why is Stream missing from the list of instances, after having been used many times as an example? It's there, actually, but you have to squint a little.

The Stream functor can be defined as Cofree Identity (the definition of Cofree is here). Cofree Identity is represented by sequences of unit () values. And the type of sequences of () is isomorphic to the natural numbers.

Applicative vs. Monad

In an Applicative, effects build the railroad upon which the locomotive of function application will travel. All the effects take place while building the railroad, not when the locomotive moves. The locomotive cannot change its course in any way.

A Monad is like having a locomotive in a railroad which is still under construction. Passengers can actually yell to the construction crew a few meters ahead to tell them things like "I like the scenery on this side, please lay the tracks a bit more towards the right" or "you can stop laying tracks, I get out right here". Of course, for this strange railway, the company can't provide a timetable or a fixed list of stops that can be checked before embarking on the train.