Cover by Donald Bruce Stewart, Bryan O'Sullivan, John Goerzen

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

The List Monad

While the Maybe type can represent either no value or one, there are many situations where we might want to return some number of results that we do not know in advance. Obviously, a list is well suited to this purpose. The type of a list suggests that we might be able to use it as a monad, because its type constructor has one free variable. And sure enough, we can use a list as a monad.

Rather than simply present the Prelude’s Monad instance for the list type, let’s try to figure out what an instance ought to look like. This is easy to do: we’ll look at the types of (>>=) and return, perform some substitutions, and see if we can use a few familiar list functions.

The more obvious of the two functions is return. We know that it takes a type a, and wraps it in a type constructor m to give the type m a. We also know that the type constructor here is []. Substituting this type constructor for the type variable m gives us the type [] a (yes, this really is valid notation!), which we can rewrite in more familiar form as [a].

We now know that return for lists should have the type a -> [a]. There are only a few sensible possibilities for an implementation of this function. It might return the empty list, a singleton list, or an infinite list. The most appealing behavior, based on what we know so far about monads, is the singleton list—it doesn’t throw away information, nor does it repeat it infinitely:

-- file: ch14/ListMonad.hs returnSingleton :: a -> [a] returnSingleton x ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required