Monad (functional programming)

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Sister project The Wikibook Haskell has a page on the topic of

In functional programming, a monad is a kind of abstract data type used to represent computations (instead of data in the domain model). Programs written in functional style can make use of monads to structure procedures that include sequenced operations,[1][2] or to define arbitrary control flows (like handling concurrency, continuations, or exceptions).

Formally, a monad is constructed by defining two operations bind and return and a type constructor M that must fulfill several properties. These properties make possible the correct composition of functions that use values from the monad as their arguments (so called monadic functions). The monad acts as a framework in that it's a reusable behavior that decides the order in which the specific monadic functions are called, and manages all the undercover work required by the computation.[3]

The primary uses of monads in functional programming are to express input/output (I/O) operations and changes in state without using language features that introduce side effects[4]. 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." In imperative programming the side effects are embedded in the semantics of the programming language; with monads, they are made explicit in the monad definition.

The name monad derives from category theory, a branch of mathematics that describes patterns applicable to many mathematical fields. (As a minor terminological mismatch, the term "monad" in functional programming contexts is usually used with a meaning corresponding to that of the term "strong monad" in category theory, a specific kind of category theoretical monad.[citation needed])

The Haskell programming language is a functional language that makes heavy use of monads, and includes syntactic sugar to make monadic composition more convenient. All of the code samples below are written in Haskell unless noted otherwise.

Contents

[edit] Motivation

Consider a function, such as division, which is undefined for some known values, such as zero. Division might occur repeatedly in a calculation, like this one, which returns the resistance of two electrical resistors in parallel:

-- par is a function that takes two real numbers and returns another
par :: Float -> Float -> Float
par x y = 1 / ((1 / x) + (1 / y))

Not a convincing example: two parallel resistors where either is zero amount to a zero resistance; no Maybe's or Monads should even be considered for par. 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:

-- // is an operator that takes two "Maybe Float"s and returns another.
-- "Maybe Float" extends the Float type to represent calculations that may fail.
(//) :: 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'))
-- where 1', x', y' are the "Maybe" versions of 1, x, y and +' "adds" Maybe Floats.
-- See below for details.

With the // operator, dividing by zero anywhere in the computation will result in the entire computation returning a special value of the Maybe monad called "Nothing", which indicates a failure to compute a value. Otherwise, the computation will produce a numerical result, contained in the other Maybe value, which is called "Just". The result of this division operator can then be passed to other functions. This concept of "maybe values" is one situation where monads are useful.

[edit] Concepts

[edit] Definition

A monad is a construction that, given an underlying type system, embeds a corresponding type system (called the monadic type system) into it (that is, each monadic type acts as the underlying type). This monadic type system preserves all significant aspects of the underlying type system, while adding features particular to the monad.

The usual formulation of a monad for programming is known as a Kleisli triple, and has the following components:

  1. A type construction that defines, for every underlying type, how to obtain a corresponding monadic type. In Haskell's notation, the name of the monad represents the type constructor. 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. A unit function that maps a value in an underlying type to a value in the corresponding monadic type. The result is the "simplest" value in the corresponding type that completely preserves the original value (simplicity being understood appropriately to the monad). In Haskell, this function is called return due to the way it is used in the do-notation described later. The unit function has the polymorphic type t→M t.
  3. A binding operation of polymorphic type (M t)→(t→M u)→(M u), which Haskell represents by the infix operator >>=. Its first argument is a value in a monadic type, its second argument is a function that maps from the underlying type of the first argument to another monadic type, and its result is in that other monadic type. The binding operation can be understood as having four stages:
    1. The monad-related structure on the first argument is "pierced" to expose any number of values in the underlying type t.
    2. The given function is applied to all of those values to obtain values of type (M u).
    3. The monad-related structure on those values is also pierced, exposing values of type u.
    4. Finally, the monad-related structure is reassembled over all of the results, giving a single value of type (M u).

In Object-oriented programming terms, the type construction would correspond to the declaration of the monadic type, the unit function takes the role of a constructor method, and the binding operation contains the logic necessary to execute its registered callbacks (the monadic functions).

In practical terms, a monad, unlike your everyday function result, stores function results and side-effect representations. This allows side effects to be propagated through the return values of functions without breaking the pure functional model. For example, Haskell's Maybe monad can have either a normal return value, or Nothing. Similarly, error monads (such as Either e, for some type e representing error information) can have a normal return value or an error value.

[edit] Examples

Consider how these apply to the "Maybe" example. A Maybe type is just the underlying type (represented by wrapping with "Just"), and a value representing "nothing", i.e. undefined.

data Maybe t = Just t | Nothing

The Maybe value corresponding to an underlying value, is just that value (represented by wrapping with "Just").

return x = Just x

Binding a function to something that is just a value means applying it directly to that value (the function must return a monadic type). Binding a function to nothing produces nothing.

mBind :: Maybe a -> (a -> Maybe b) -> Maybe b
(Just x) `mBind` f = f x
Nothing `mBind` f = Nothing
For the safe division example, "(/)" is the underlying function, "(//)" is the safe monadic version. There are two Maybe inputs. If either input is "Nothing", then "Nothing" is returned. Otherwise the inputs are Just a and Just b, from which a and b are extracted. If b is zero, (/) cannot be applied, so "Nothing" is returned, otherwise "Just (a / b)" is returned:
(//) :: Maybe a -> Maybe a -> Maybe a
_ // Nothing = Nothing
Nothing // _  = Nothing
_ // Just 0 = Nothing
Just x // Just y = Just (x / y)

A more general version that applies to all types m such that m is an instance of the Monad class:

(//) :: (Fractional a, Monad m) => a -> a -> m a
_ // 0 = fail "//: divide by zero"
x // y = return (x / y)

This is the definition of the same Maybe monad in the F# language:[5]

type MaybeBuilder() =
    member this.Bind(x, f) =
        match x with
        | Some(x) -> f(x)
        | _ -> None
    member this.Delay(f) = f()
    member this.Return(x) = Some x
 
let maybe = MaybeBuilder()

[edit] Axioms

For a monad to behave correctly, the definitions must obey a few axioms.[6] (The ≡ symbol is not Haskell code, but indicates an equivalence between two Haskell expressions.)

  • "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] Monadic zero

A monad can optionally define a "zero" value for every type. Binding a zero with any function produces the zero for the result type, just as 0 multiplied by any number is 0.

mzero >>= f ≡ mzero

Similarly, binding any m with a function that always returns a zero results in a zero

m >>= (\x -> mzero) ≡ mzero

Intuitively, the zero represents a value in the monad that has only monad-related structure and no values from the underlying type. In the Maybe monad, "Nothing" is a zero. In the List monad, "[]" (the empty list) is a zero.

[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 (perform-notation in OCaml, computation expressions in F#), that mimics the appearance of imperative languages. The compiler translates do-notation to expressions involving >>=. For example, the following code:

a = do x <- [3..4]
       [1..2]
       return (x, 42)

is transformed during compilation into:

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))

It is helpful to see the implementation of the list monad, and to know that concatMap maps a function over a list and concatenates (flattens) the resulting lists:

instance Monad [] where
  m >>= f  = concatMap f m
  return x = [x]
  fail s   = []

Therefore, the following transformations hold:

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))
a = [3..4] >>= (\x -> concatMap (\_ -> return (x, 42)) [1..2] )
a = [3..4] >>= (\x -> [(x,42),(x,42)] )
a = concatMap (\x -> [(x,42),(x,42)] ) [3..4]
a = [(3,42),(3,42),(4,42),(4,42)]

Notice that the list [1..2] is not used. The lack of a left-pointing arrow, translated into a binding to a function that ignores its argument, indicates that only the monadic structure is of interest, not the values inside it; for the list monad this is trivial, but e.g. for a state monad this might be used for changing the state without producing any more result values. The do-block notation can be used with any monad as it is simply syntactic sugar for >>=.

The following definitions for safe division for values in the Maybe monad are also equivalent:

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

x // y = x >>= (\a -> y >>= (\b -> if b == 0 then Nothing else Just (a / b)))

A similar example in F# using a computation expression:

let readNum () =
  let s = Console.ReadLine()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None
 
let secure_div = 
  maybe { let! x = readNum()
    let! y = readNum()
    if (y = 0) 
    then None
    else return (x / y)
  }

The syntactic sugar of the maybe block would get translated internally to the following expression:

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return( x/y ))))

[edit] Generic monadic functions

Given values produced by safe division, we might want to carry on doing calculations without having to check manually if they are Nothing (i.e. resulted from an attempted division by zero). We can do this using a "lifting" function, which we can define not only for Maybe but for arbitrary monads. In Haskell this is called liftM2:

liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 op mx my = do
    x <- mx
    y <- my
    return (op x y)

Recall that arrows in a type associate to the right, so liftM2 is a function that takes a binary function as an argument and returns another binary function. The type signature says: If m is a monad, we can "lift" any binary function into it. For example:

(.*.) :: Monad m => m Float -> m Float -> m Float
x .*. y = liftM2 (*) x y

defines an operator (.*.) which multiplies two numbers, unless one of them is Nothing (in which case it again returns Nothing). The advantage here is that we need not dive into the details of the implementation of the monad; if we need to do the same kind of thing with another function, or in another monad, using liftM2 makes it immediately clear what is meant (see Code reuse).

[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.

[edit] Identity monad

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

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

A do-block in this monad performs variable substitution; do {x <- 2; return 3*x} results in 6.

[edit] Collections

Some familiar collection types, including lists, sets, and multisets, are monads. The definition for lists is given here.

-- "return" constructs a one-item list.
return x = [x]
-- "bind" concatenates the lists obtained by applying f to each item in list xs.
xs >>= f = concat (map f xs)
-- The zero object is an empty list.
mzero = []

List comprehensions are a special case of the list monad. For example, the list comprehension [ 2*x | x <- [1..n], isOkay x] corresponds to the list monad do {x <- [1..n]; if isOkay x then return () else mzero; return (2*x)}. Similarly, other types of comprehensions, e.g. set comprehensions, are special cases of the corresponding type of monad, e.g. set monad.

The monads for sets and multisets support the use of set-builder notation similarly. The set monad is useful when the state of a computation is ambiguous, as in a parser that has not read enough input to decide what syntax it is reading. The parser can maintain a set that represents the possible syntaxes, and scan until the set has one item (meaning that a syntax was recognized) or no items (meaning that the input is unacceptable).

The monads for collections naturally represent nondeterministic computation. The list (or other collection) represents all the possible results from different nondeterministic paths of computation at that given time. For example, when you do x <- [1,2,3,4,5], you are saying that the variable x can non-deterministically take on any of the values of that list. If you were to return x, it would evaluate to a list of the results from each path of computation. Notice that the bind operator above follows this theme by performing f on each of the current possible results, and then it concatenates the result lists together.

You also often see statements like if condition x y then return () else mzero; if the condition is true, it chooses from one path of computation, which is a dummy value we are not assigning to anything; however, if the condition is false, then the mzero = [] monad value non-deterministically chooses from 0 values, effectively terminating that path of computation. Other paths of computations might still succeed. This effectively serves as a "guard" to enforce that only paths of computation that satisfy certain conditions can continue. So collections monads are very useful for solving logic puzzles, Sudoku, and similar problems.

In a language with lazy evaluation, like Haskell, if you only request the first element of a list monad, then, since lists are evaluated lazily, it only performs just enough work to get the first valid result -- that is, it chooses a path of computation, and then if it fails at some point (if it evaluates mzero), then it backtracks to the last branching point, and follows the next path, and so on. If you then request the second element, it again does just enough work to get the second solution, and so on. So the list monad is a simple way to implement a backtracking algorithm in a lazy language.

[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] Alternative 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. As before, the ≡ symbol indicates equivalence between two Haskell expressions.

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

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

[edit] History

Eugenio Moggi first described the general use of monads to structure programs.[7] Several people built on his work, including programming language researchers Philip Wadler and Simon Peyton Jones (both of whom were involved in the specification of Haskell). Early versions of Haskell used a problematic "lazy list" model for I/O, and Haskell 1.3 introduced monads as a more flexible way to combine I/O with lazy evaluation.

In addition to IO, scientific articles and Haskell libraries have successfully applied monads to 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.

Haskell and its derivatives have been for a long time 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. Recently the research language F# has included a feature called computation expressions or workflows, which are an attempt to introduce monadic constructs within a syntax more palatable to programmers with an imperative background.[8]

Effect systems are an alternative way of describing side effects as types.

[edit] See also

  • Arrows in functional programming — whereas monads generalize the results of a computation to effects, arrows further generalize the inputs similarly.
  • Monad transformers — which allow monads to be composed in a modular and convenient way.
  • Inversion of control — the abstract principle of calling specific functions from a reusable software entity.
  • Uniqueness types - an alternative way of dealing with side-effects in functional languages

[edit] References

  1. ^ Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
  2. ^ Philip Wadler. The Essence of Functional Programming. Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1992.
  3. ^ A physical analogy for monads, explains monads as assembly lines.
  4. ^ 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
  5. ^ F# Overview (IV.) - Language Oriented Programming
  6. ^ The three fundamental laws of Monad. See this page
  7. ^ Moggi, Eugenio (1991). "Notions of Computation and Monads". Information and Computation 93 (1). http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf. 
  8. ^ "Some Details on F# Computation Expressions". http://blogs.msdn.com/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx. Retrieved on 2007-12-14. 

[edit] External links

[edit] Haskell monad tutorials

[edit] Other documentation

[edit] Monads in languages other than Haskell

Retrieved from "http://en.wikipedia.org/wiki/Monad_(functional_programming)"
Personal tools