Monads in functional programming

From Free net encyclopedia

---

Current revision

Some functional programming languages, particularly Haskell, make use of the monad concept from category theory, a branch of mathematics that describes patterns applicable to many mathematical fields.

A monad can be thought of as an alternate mathematical "world" that supplements each value and function with extra functionality. They enable a programmer to make the routine parts of a computation implicit, such as the order of operations or the detection of errors, while focusing on the aspects that are more relevant to the problem at hand. To define a monad, the programmer provides a set of rules for attaching the implicit handling to a given value or function, so that executing the function will also execute the monad's calculations. The IO monad, for example, attaches the action of reading input to the calculation that uses the input.

One disadvantage of monads is that they do not combine easily; it is not straightforward to attach the functionality of several monads to a single computation. Monad transformers can achieve this effect when necessary, at the cost of adding complexity.

Contents 1 History 2 Example: Maybe monad 3 Notations 3.1 Category-theoretic notation 3.2 Bind operator 3.3 do-notation 4 Monad types 5 More examples 5.1 Maybe monad revisited 5.2 Identity monad 5.3 Lists 5.4 State transformers 5.5 I/O 5.6 Others 6 See also 7 References 8 External links

History

After the mathematical background, the concept of monads was first applied to programming in the context of purely functional programming and the Haskell programming language. Earlier versions of Haskell had had inadequate means for IO and monads were devised during the development of Haskell 98 as a suitable system for combining extensible IO with lazy evaluation.

In addition to IO, scientific articles and Haskell libraries have successfully applied monads to varying topics including parsers and programming language interpreters. The concept of monads along with the Haskell do-notation for them has also been generalized to form arrows.

As of 2006, Haskell and its derivatives are the only major users of monads in programming. There exist formulations also in Scheme and Perl, and monads have been an option in the design of a new ML standard. Effect systems compete with monads in describing side effects as types.

Example: Maybe monad

Before discussing the details of monads, it might help to give a motivating example. Consider a function that is undefined for some known values, such as division. Division might occur repeatedly in a calculation, like this one:

par:: Float -> Float -> Float -- Takes two real numbers and returns another
par x y = 1 / ((1 / x) + (1 / y))

Instead of avoiding any errors by checking whether each divisor is zero, it might be convenient to have a modified division operator that does the check implicitly, as in the following pseudocode:

-- "Maybe Float" extends the Float type so that it can represent failed calculations.
(//):: Float -> Float -> Maybe Float
x // y = ...   -- the definition is in next section 
par:: Float -> Float -> Maybe Float
par x y = 1 // ((1 // x) + (1 // y))

We would like that the result of the division operator could be passed into any other function. At the end we might have just a number, or if some divisor was zero, we might have nothing:

data Maybe a = Just a | Nothing -- Either it's Just a value, or it's Nothing.

This world of "maybe values" is one of many monads that Haskell provides.

Notations

Computer scientists have used at least three notations for monads, and terminology varies. The following descriptions use the Haskell names for operations. Monad comprehension notation has had a limited use.

Category-theoretic notation

Following the definition of a monad in category theory, a program can specify a monad as a set of three type-generic functions:

• A function return that turns a value in any type into a value in a corresponding monadic type;
• A function fmap that turns a function between two types into a function between the corresponding monadic types;
• A function join that maps doubly monadic values (such as Just (Just 3)) to corresponding singly monadic values (Just 3). join is called concatm by some authors.

A definition of these operations must satisfy the following laws:

1. fmap(id) = id
2. fmap(f o g) = fmap(f) o fmap(g)
3. fmap(f) o return = return o f
4. fmap(f) o join = join o fmap(fmap(f))
5. join o return = id
6. join o fmap(return) = id
7. join o fmap(join) = join o join

Conceptually, return and fmap describe how to find values and operations in a particular monadic world that correspond to those in the normal world. The join operation reduces the result of any number of jumps into a monadic world to the basic monadic type. Strictly speaking this is called a strong monad, since monads in general do not require the transformations to be functions.

See monad (category theory)

Bind operator

The category theory formulation can be made more straightforward to implement in computer programming by replacing the join and fmap operations with a bind operation. This operation is represented by the infix operator >>= which takes a value in the monadic type for type a as its left argument, and a function mapping values of type a to another monadic type (in the same monad) as its right argument. The bind operator "peeks inside" its left argument and applies its right argument to any values of type a it finds. Haskell provides no other general basic operations on monads, so there is no other generic way to use a monadic value at runtime than to apply the bind operator for its monad. Since the bind operator is associative and non-commutative, this constrains the execution into a sequence.

The bind operator must obey the following laws:

1. (return x) >>= f ≡ f x
2. m >>= return ≡ m
3. m >>= (return o f) ≡ (fmap f) m
4. m >>= (λx. (f x) >>= g) ≡ (m >>= f) >>= g

These two formulations of monads are equivalent according to the following identities:

• m >>= f ≡ join ((fmap f) m)
• join m ≡ m >>= id
• (fmap f) m ≡ m >>= (return o f)

Since computations often do not use a monad's contained value, Haskell also provides an operator >> that simply throws it away, defined as follows:

m >> n = m >>= (λx. n)

This corresponds to the sequencing in imperative programming languages that is denoted with a semicolon in languages such as C. Both A; B in C and A >> B in Haskell mean that B is carried out in the environment after effects of A.

do-notation

To support the use of monads, Haskell has a specific syntax for the bind operation called the do-notation. An expression in the notation starts with the keyword do and is followed by a sequence of operations in a monad. The result of an operation can be bound to a variable and used in later operations.

An example in the IO monad:

main :: IO ()
main = do putStrLn "Hello! What's your name?"
          name <- getLine
          putStrLn ("Nice to meet you, "++name++".")

The compilers translate this to the following expression with monad sequencing and lambda abstraction:

main :: IO ()
main = putStrLn "Hello! What's your name?" >> 
       getLine >>= \name -> putStrLn ("Nice to meet you, "++name++".")

This program discards the value produced by the first putStrLn, since it doesn't contain any information this program needs. The value produced by getLine, however, is passed to the second putStrLn.

Monad types

Any type can be made an instance of the Monad type class by defining the method return for making such a monad and the operator >>= for sequencing a monad operation to another. For the definitions to make sense, they should follow the monad laws. Optionally, an error method and a result-discarding bind can be specified.

Simple types with useful monad interpretations include a list and Either. List can be used to produce results of an operation sequence for all combinations of inputs (ie. simulate nondeterminism). Either represents a value with two possible types, and in case of an error one type is used to skip the rest of the sequence and report the error instead of a successful result in the other type.

More examples

Maybe monad revisited

Now a complete description of the Maybe monad is possible:

data Maybe a = Just a | Nothing
return x = Just x
fmap f (Just x) = Just (f x)
fmap f Nothing = Nothing
(Just x) >>= f = f x
Nothing >>= f = Nothing

The division example is then implemented as follows:

(//):: Maybe Float -> Maybe Float -> Maybe Float
x // y = do a <- x; b <- y; if b == 0 then Nothing else return (a / b)

(+++):: Maybe Float -> Maybe Float -> Maybe Float
x +++ y = do a <- x; b <- y; return (a + b)

par:: Float -> Float -> Maybe Float
par x y = let one = Just 1 in one // ((one // Just x) +++ (one // Just y))

If any result of // is Nothing then it will propagate through the rest of the expression.

Identity monad

In the identity monad, every type is its own monadic type.

return x = x
fmap f x = f x
x >>= f = f x

A do-block in this monad is no different from a let-expression.

Lists

Lists are also a monad.

return x = [x]
fmap f xs = map f xs
xs >>= f = concat (map f xs)

In the list monad, a do-block is a list comprehension. It can also be considered as non-deterministic operations where the list consists of all possible values. Sets, multisets, and other collections also have monads.

State transformers

The need to express computations involving state data provided one of the main motivations for supporting monads in functional languages. One can pass state data around explicitly in the calculation, but this leads to verbose code that obscures the programmer's intent. Furthermore, expressing state-modifying computations in a standard way allows compilers to optimize them by overwriting the previous state data.

The trick to maintaining referential transparency is to consider state transformers as values; the state itself is not available until runtime. The transformers implicitly carry it through the calculation while returning other explicit values. A typical formulation is:

type StateTrans s a = s -> (a, s)

-- Introduce the value x into a state-transforming calculation.
return x = \s -> (x, s)

-- Adapt function f for use in a state transformer.
fmap f m = \s -> let (x, s') = m s in (f x, s')

-- Modify transformer m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s

Useful transformers include:

readState = \s -> (s, s) -- Examine the state at this point in the computation.
writeState t = \s -> ((), t) -- Replace the state.

Another operation applies a state transformer to a given initial state:

applyTrans:: StateTrans s a -> s -> (a, s)
applyTrans t s = t s

do-blocks in a state monad are sequences of operations that can examine and update the state data.

I/O

Considering the external world (such as disks and network connections) as state data allows functional languages to express input and output operations. The entire program then becomes a transformer on the I/O state, although that transformer might spend most of its time evaluating purely functional code.

Others

Other concepts that researchers have expressed as monads include:

• Continuations
• Exception handling
• Graphical user interfaces
• Logging
• Interprocess communication
• Parsers
• Interpreters
• Strict evaluation
• Interfaces to code written in other languages

See also

• Arrows in functional programming - whereas monads generalize the results of a computation to effects, arrows further generalize the inputs similarly.

Template:Book

References

• Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
• Philip Wadler. The Essence of Functional Programming. Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1992.
• Simon L. Peyton Jones, Philip Wadler. Imperative Functional Programming. Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina. 1993

External links

• All About Monads
• Monads as Containers
• Monads for the Working Haskell Programmer
• "Monads for Functional Programming" (PDF) by Philip Wadler
• The Haskell Programmer's Guide to the IO Monad — Don't Panic (PDF)