Monad (computer science)

In functional programming , monads are an abstract data type . An essential property of monads is the ability to transfer values ​​and calculations of a "simpler" type to calculations of a "higher" type that emerges from the simpler type using a type constructor, as well as the linking of several such transfers to a single one.

background

The main use of monads is to express input and output operations , stateful calculations, nondeterminism (also interpretable as iteration over collections and their combinations) and others. The language should not introduce any side effects .

The concept of the monad comes from category theory , a branch of mathematics that compares mathematical objects using morphisms or functors . The words monad or functor are in turn derived from concepts in philosophy.

The Haskell programming language is a functional language that makes heavy use of monads and tries to simplify monadic compositions , for example through syntactic sugar (including the so-called do notation).

Definitions

The usual formulation of a monad in programming has the following components:

1. A type constructor which defines, for each underlying type, such as the corresponding Monadentyp is obtained to. The name of this type constructor is often used synonymously with the whole monad. If M is the name of the monad and t is the data type, then M t is the corresponding monadic type.
2. A unit function that maps a value of the underlying type to the value of the corresponding monad type. The result is the "simplest" value in the corresponding type that can be obtained from the original value. In Haskell this function is called return . The unit function has the polymorphic type t → M t .
3. At least one further operation (see the following sections), which describes the combination of monadic operations.

The following operations are typical of monads and can be used to define them:

1. The unit function

   return :: a -> m a
   

2. The bind operator

   (>>=) :: m a -> (a -> m b) -> m b
   

   allows a monadic type to be passed to a function that only uses the underlying type. Its first argument is a value of monadic type and its second is a function that maps from the underlying type of the first argument to another monadic type. The return value is of the other monad type.
3. The Kleisli operator

   (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
   

   realizes a composition (execution one after the other) for functions that return a monadic type, but only use the respective underlying type.
4. The functor

   fmap :: (a -> b) -> m a -> m b
   

   allows a monadic type to be passed to a function that only uses the underlying type. Its first argument is a function f , which maps from any type a to any type b . Its second argument is a value of a monadic type based on the type a of the argument of f . The return value is of a monadic type based on the type b of the return value of f .
5. A natural transformation

   join :: m (m a) -> m a
   

   which allows the monadic type to be “flattened” by one nesting level (stands mfor the type constructor).

These operations must obey the following laws:

1. "Associativity" of >>=

     (ma >>= f) >>= g == ma >>= ( \a -> ((f a) >>= g) )
   

2. Associativity of >=>

     (f >=> g) >=> h  == f >=> (g >=> h)
   

3. Chaining and fmap

         fmap (f . g) == (fmap f) . (fmap g)
   

4. joinis a natural transformation from fmap . fmaponfmap

      (fmap f) . join == join . ((fmap . fmap) f)
   

5. Commutativity of fmapandjoin

         join . join  == join . (fmap join) -- das zweite join hat den typ m (m (m a)) -> m (m a)
   

6. returnis a natural transformation from idonfmap

    (fmap f) . return == return . f
   

7. Neutrality from returnunder>>=

   1       ma >>= return == ma
   2    (return a) >>= f == f a
   

8. Neutrality from returnunder>=>

         f >=> return == return >=> f == f
   

9. Neutrality of returnunder >=>, in fmap/ joinnotation

        join . return == join . (fmap return) == id
   

Based on Haskell

In Haskell, a monad is defined through operations returnand (>>=):

class Monad m where
  return ::   a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b

The other operations can then be defined using these two:

(f >=> g) a = f a >>= g
(fmap f) ma =  ma >>= (return . f)
   join mma = mma >>= id

Via the Kleisli operator

A monad can also be defined by its Kleisli category :

class Monad m where
  return ::  a -> m a
  (>=>)  :: (a -> m b) -> (b -> m c) -> (a -> m c)

The remaining operations then result as follows:

   ma >>= f = (id >=>  f)  ma
     fmap f =  id >=> (return . f)
       join =  id >=> id

Analogous to category theory

In category theory, a monad is usually defined via a functor fmap and two natural transformations return and join:

class Monad m where
  fmap   :: (a -> b) -> m a -> m b
  return ::       a  ->  m a
  join   ::  m (m a) ->  m a

The other operations can then be implemented as follows:

   ma >>= f = (join . (fmap f)) ma
    f >=> g =  join . (fmap g) . f

Relationships with other type classes

Every monad is also an applicative functor and therefore also a functor . The reverse is not true.

For historical reasons, this property was not explicitly found in Haskell's standard library, but the Glasgow Haskell Compiler introduced it with version 7.10.

This relationship becomes particularly clear if one compares the category-theoretical definition with the functor class in Haskell:

class Functor f where
  fmap   :: (a -> b) -> f a -> f b

fmapThe compatibility condition with the composition ( .) must also be fulfilled.

Examples

container

→ Main article : Container (computer science)

Containers such as lists , sets , multisets represent monads whose binding operation uses the passed function to all elements and combines the results obtained. The union operation is list chaining, union set formation or formation of the multi-set union. The unit function gives sets and lists of units.

Here as an example the monad for linked lists. The concept of the instance for lists is to read in a list, then pass each element to the function and combine the results. Here is an example implementation in Haskell:

-- Hier nochmal zur Erinnerung, der Listentyp ist folgendermaßen definiert:
data [a] = [] | a:[a]
-- Als syntaktischer Zucker kann [a,b,c] für a:b:c:[] verwendet werden.

instance Monad [] where
--return :: a -> [a]
  return a = [a] -- Per Definition eine Liste mit einem Element zurückgeben
--(>>=) :: [a] -> (a -> [b]) -> [b]
  liste >>= f  = concat zwischenergebnis where -- Die einzelnen Teillisten zusammenfügen
    zwischenergebnis :: [[b]]
    zwischenergebnis = map f liste -- Die Funktion auf die Liste abbilden

Vectors and linear maps

The type constructor here maps a type to a vector space , which serves as a (name giver for a) base and whose elements are modeled as functions , for example . The bind operation is of the type . By swapping the arguments one gets the type by which one can recognize the semantics: the given function, which is defined on the basic elements, is extended to a full linear mapping. The unit function maps the basic element (which is not yet a “correct” vector in this modeling ) onto the corresponding basic vector. ${\displaystyle T}$ ${\displaystyle V(T)}$ ${\displaystyle T}$ ${\displaystyle T\to \mathbb {R} }$ ${\displaystyle V(T)\to (T\to V(U))\to V(U)}$ ${\displaystyle (T\to V(U))\to (V(T)\to V(U))}$

State, I / O

In the case of stateful actions, the bind operation is used to implement sequential execution. The unit function creates an action that does nothing and returns a fixed result.

The concept is quite natural. If you want to transfer a changeable status in a purely functional programming language, you usually do it in the following way, here using the example of a counter function:

-- Den Zähler hochzählen und den alten Zähler zurückgeben
hochzählen :: Int -> Int -> (Int,Int)
hochzählen schrittweite zählerstand = (zählerstand,neuerZählerstand) where ...

The basic principle is to append the old status as a parameter and to return the new one together with the return value. To save yourself work, you can simply pack this pattern in a new type, the parameter of sthe type is the type of the status, ais the parameter of the return value:

data Status s a = Status (s -> (a,s))

-- Beispiel:
hochzählen :: Int -> Status Int Int
hochzählen schrittweite = Status $ \zählerstand -> (zählerstand,zählerstand+schrittweite)

What you still need now are a few functions that can manipulate the status. For example, here is a function that sets the status to a new one and one that reads it out:

setStatus :: s -> Status s ()
setStatus s = Status $ \_ -> ((),s) -- Der alte Status wird ignoriert und durch den neuen ersetzt. Rückgabewert, da unnötig, ().

getStatus :: Status s s
getStatus = Status $ \s -> (s,s) -- Dupliziere den Status in den Rückgabewert.

This is almost all that is needed. The only thing missing is the ability to combine several status-changing actions, here monads are the tool of choice:

instance Monad (Status s) where -- Die Typvariable  s ist irrelevant für die Definition
--return :: a -> Status s a
  return a = Status $ \s -> (a,s) -- Status bleibt unverändert
--(>>=)  :: Status s a -> (a -> Status s b) -> Status s b
  (Status aktion1) >>= f = Status $ \s -> aktion2 zwischenstatus where -- Status aus aktion1 in aktion2 einspeisen.
    (rückgabe1,zwischenstatus) = aktion1 s   -- aktion1 ausführen
    Status aktion2              = f rückgabe1 -- Rückgabewert aus aktion1 in f einspeisen

With these functions and the syntactic sugar of the do notation (which hides the monadic operations from us) the example can then be formulated as follows:

hochzählen :: Int -> Status (Int,Int)
hochzählen schrittweite = do zählerstand <- getStatus -- Zählerstand ermitteln
                             setStatus (zählerstand + schrittweite) -- Zähler setzen
                             return zählerstand -- alten Zählerstand zurückgeben

-- Hier entzuckert
hochzählen schrittweite = getStatus >>= \zählerstand ->
                          setStatus (zählerstand + schrittweite) >>= \_ ->
                          return zählerstand

Other languages

LINQ query expressions in C # are directly inspired by Haskell's donotation. However, an analogue to the type class Monadcannot be expressed in C #; the compiler blindly translates LINQ query expressions into calls to methods with fixed names. These are Selectand SelectMany. User-defined classes can also be addressed using LINQ query expressions, if these methods provide them with appropriate names.

Scala follows the same strategy in the case of forComprehensions. The methods are called there mapand flatMap.

There are at least two monads in the Java 8 standard library that obey the same naming convention: the interfaces Optionaland Streamdefine methods named map, flatMapand of.

Web links

• Papers by Philip Wadler
• You Could Have Invented Monads! (And Maybe You Already Have.)
• What a Monad is not
• Brent Yorgey: Typeclassopedia (PDF; 722 kB) in: The Monad.Reader Issue 13

Monads in other programming languages

Groovy

• Monads in Groovy

Ruby

• Monads in Ruby

python

• Monads in Python

Scala

• Monads in Scala

Clojure

• Monads in Clojure

JavaScript

• Monads in JavaScript ( Memento from December 22, 2010 in the Internet Archive )

C #

• Wes Dyer: The Marvels of Monads. In: Yet Another Language Geek. MSDN Blogs, Microsoft , January 10, 2008, accessed March 21, 2013 . 
• Mike Hadlow: Monads in C #. In: Code Rant. January 9, 2011, accessed March 21, 2013 . 
• LINQ
• Muraad Nofal: Monads-CSharp. In: GitHub. March 10, 2014, accessed March 21, 2013 . 

Individual evidence

1. ^ 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 SC 1993
2. ↑ https://downloads.haskell.org/~ghc/7.10.1/docs/html/users_guide/release-7-10-1.html
3. ↑ Erik Meijer: The World According to LINQ . ( acm.org ).
4. ↑ http://www.scala-lang.org/files/archive/spec/2.11/06-expressions.html