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:
- 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.
- 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 .
- 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:
- The unit function
return :: a -> m a
- The bind operator 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.
(>>=) :: m a -> (a -> m b) -> m b
- The Kleisli operator realizes a composition (execution one after the other) for functions that return a monadic type, but only use the respective underlying type.
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
- The functor 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 .
fmap :: (a -> b) -> m a -> m b
- A natural transformation which allows the monadic type to be “flattened” by one nesting level (stands
join :: m (m a) -> m a
m
for the type constructor).
These operations must obey the following laws:
- "Associativity" of
>>=
(ma >>= f) >>= g == ma >>= ( \a -> ((f a) >>= g) )
- Associativity of
>=>
(f >=> g) >=> h == f >=> (g >=> h)
- Chaining and
fmap
fmap (f . g) == (fmap f) . (fmap g)
-
join
is a natural transformation fromfmap . fmap
onfmap
(fmap f) . join == join . ((fmap . fmap) f)
- Commutativity of
fmap
andjoin
join . join == join . (fmap join) -- das zweite join hat den typ m (m (m a)) -> m (m a)
-
return
is a natural transformation fromid
onfmap
(fmap f) . return == return . f
- Neutrality from
return
under>>=
1 ma >>= return == ma 2 (return a) >>= f == f a
- Neutrality from
return
under>=>
f >=> return == return >=> f == f
- Neutrality of
return
under>=>
, infmap
/join
notationjoin . return == join . (fmap return) == id
Based on Haskell
In Haskell, a monad is defined through operations return
and (>>=)
:
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
fmap
The compatibility condition with the composition ( .
) must also be fulfilled.
Examples
container
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.
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 s
the type is the type of the status, a
is 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 do
notation. However, an analogue to the type class Monad
cannot be expressed in C #; the compiler blindly translates LINQ query expressions into calls to methods with fixed names. These are Select
and 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 for
Comprehensions. The methods are called there map
and flatMap
.
There are at least two monads in the Java 8 standard library that obey the same naming convention: the interfaces Optional
and Stream
define methods named map
, flatMap
and 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
- Monads in JavaScript ( Memento from December 22, 2010 in the Internet Archive )
- 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
- ^ 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
- ↑ https://downloads.haskell.org/~ghc/7.10.1/docs/html/users_guide/release-7-10-1.html
- ↑ Erik Meijer: The World According to LINQ . ( acm.org ).
- ↑ http://www.scala-lang.org/files/archive/spec/2.11/06-expressions.html