Monads in functional programming

From Wikipedia, the free encyclopedia

Some functional programming languages make use of monads to structure programs which include operations that must be executed in a specific order. The name monad derives from category theory, a branch of mathematics that describes patterns applicable to many mathematical fields. The primary uses of monads in functional programming are to express input/output operations and changes in state without using language features that introduce side effects. They exploit a loophole that, although a function cannot directly cause a side effect, it can construct a value describing a desired side effect that the caller should apply at a convenient time. However, I/O and state management are by no means the only uses of monads. They are useful in any situation where the programmer wants to carry out a purely functional computation while a related computation is carried out "on the side." The Haskell programming language makes heavy use of monads, and includes syntactic sugar to make monad composition more convenient.

Contents

[edit] Motivation

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.
(//):: Maybe Float -> Maybe Float -> Maybe Float
x // y = ...   -- the definition appears below.
par:: Float -> Float -> Maybe Float
par x y = 1 // ((1 // x) + (1 // y))   -- types do not actually match, see below for correct version

The result of this division operator could then be passed to other functions. Dividing by zero anywhere in the computation would give an "undefined" value for the entire computation; otherwise the computation would produce a numerical result. This concept of "maybe values" is one situation where monads are useful.

[edit] Definition

Defining a monad (according to the formulation used in Haskell) involves specifying

  1. A type association between every data type and another type that attaches the monad's information to it. In Haskell's notation, the name of the monad represents this association. If M is the name of the monad and t is a data type, then "M t" is the corresponding type in the monad.
  2. An object-mapping function that attaches monad information to a value of any type. In Haskell, this function is called return due to the way it is used in the do-notation described later. The object-mapping function has the polymorphic type t→M t.
  3. A binding operation: Given some data that has been carried into the monad, and a function that maps values (not in the monad) to values in the monad, the binding operation applies the latter to the contents of the former. The binding operation has the type (M t)→(t→M u)→M u and Haskell represents it as the infix operator ">>=".

Consider how these apply to the "Maybe" example.

  1. A type in the Maybe monad is just the underlying type, plus a value representing "nothing", i.e. undefined.
    data Maybe t = Just t | Nothing
  2. A value mapped into the Maybe monad is just the same value.
    return x = Just x
  3. Applying a function to something that is just a value means applying it directly to that value. Applying a function to nothing produces nothing.
    (Just x) >>= f = f x
    Nothing >>= f = Nothing

For a monad to behave correctly, the definitions must obey a few rules.

  • "return" must preserve all information about its argument.
    (return x) >>= f ≡ f x
    m >>= return ≡ m
  • Binding two functions in succession is the same as binding one function that can be determined from them.
    (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

In the last rule, the notation \x -> defines an anonymous function that maps any value x to the expression that follows.

[edit] Failure

Some monads can represent computations that might fail. A monad that can will have a function mzero, that produces a value that represents a failed computation.

Applying a function to a failed value should fail. Formally:

  • mzero >>= f = mzero

For example, in the Maybe monad if we apply Nothing to a function, we'll get Nothing back:

  • mzero = Nothing

[edit] do-notation

Although there are times when it makes sense to use >>= directly in a program, it is more typical to use a format called "do-notation" that mimics the appearance of non-functional languages. The compiler translates do-notation to expressions involving >>=. For example, the following do-block defines a safe division operation for values in the Maybe monad.

x // y = do
  a <- x  -- Extract the values "inside" x and y, if there are any.
  b <- y
  if b == 0 then mzero else return (a / b)

The do-block notation can be used with any monad as it is simply syntactic sugar for >>=.

[edit] Examples

[edit] Maybe monad

The Maybe monad has already been defined above. The following definitions complete the original motivating example of the "par" function.

add x y = do
  x' <- x
  y' <- y
  return (x' + y')

par x y = let
  one = return 1
  jx = return x
  jy = return y
  in one // (add (one // jx) (one // jy))

If the result of any division is Nothing, it will propagate through the rest of the expression. What's more, the function can be made to act differently on failure by running it through a different monad.

[edit] Identity monad

The simplest monad is the identity monad, which attaches no information to values.

Id x = x
return x = x
x >>= f = f x

A do-block in this monad simply binds names to values and then substitutes them in an expression.

[edit] Lists

Lists are also a monad.

-- "return" constructs a one-item list.
return x = [x]
-- "bind" concatenates the results of applying f to each item in list xs.
xs >>= f = concat (map f xs)

In the list monad, a do-block is a list comprehension. The list monad is sometimes used to find all possible results of a nondeterministic computation. Sets, multisets, and other collections also have monads.

The list monad can also represent failure. A list is a list of successes, so a failure is no successes:

 mzero = []

Running the division example in the list monad will produce [] on division by zero.

[edit] I/O

A monad for I/O operations is usually implemented in the language implementation rather than being defined publicly. The following example demonstrates the use of an I/O monad to interact with the user.

do
  putStrLn "What is your name?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

[edit] State transformers

A state transformer monad allows a programmer to attach state information of any type to a calculation. Given any value, the corresponding value in the state transformer monad is a function that accepts a state, then outputs another state along with a value.

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

Note that this monad, unlike those already seen, takes a type parameter, the type of the state information. The monad operations are defined as follows:

-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies transformer m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s

Useful state transformers include:

readState = \s -> (s, s) -- Examine the state at this point in the computation.
writeState x = \s -> ((), x) -- 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.

[edit] Others

Other concepts that researchers have expressed as monads include:

[edit] Alternate formulation

Although Haskell defines monads in terms of the "return" and "bind" functions, it is also possible to define a monad in terms of "return" and two other operations, "join" and "map". This formulation fits more closely with the definition of monads in category theory. The map operation, with type (t→u)→(M t→M u), takes a function between two types and produces a function that does the "same thing" to values in the monad. The join operation, with type M (M t)→M t, "flattens" two layers of monadic information into one.

The two formulations are related as follows:

(map f) m ≡ m >>= (\x -> return (f x))
join m ≡ m >>= (\x -> x)

m >>= f ≡ join ((map f) m)

[edit] 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 inadequate means for I/O and monads were devised during the development of Haskell 1.3 as a suitable system for combining extensible I/O 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.

[edit] See also

Wikibooks
Wikibooks Haskell has a page on the topic of

[edit] References

[edit] External links

Retrieved from "http://en.wikipedia.org../../../m/o/n/Monads_in_functional_programming.html"
In other languages