Monad (functional programming)
In functional programming, monads are an abstract data type. An important property of monads is the ability of the transmission of values and calculations in a " simpler" type for calculations in a "higher type", who proceeds by means of a Typkonstruktors from the simpler type, and the interconnection of several such transfers into one.
- 4.1 container
- 4.2 vectors and linear maps
- 4.3 State, I / O
- 5.1 Monads in other programming languages
Background
The main benefit of monads is ( interpreted as iteration over collections and their combinations ) express input and output operations, stateful computations and nondeterminism, and more. This should not introduce any side effects the language.
The name monad comes from category theory. This is a branch of mathematics which compares mathematical objects using functors and morphisms.
The Haskell programming language is a functional language that uses monads strong and tried to simplify monadic compositions, for example, by syntactic sugar (including the so-called do- notation).
Definitions
The usual formulation of a monad in programming has the following components:
The following operations are typical of monads and can be used for their definition:
Return :: a - > m a The bind operator (>> =) :: M a -> (a -> m b ) -> m b allowed to pass a monadic type to a function that uses only the underlying type. His first argument is a value from 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 Monadentyp. The Kleisli operator ( > => ) :: (A -> m b ) -> ( b -> m c ) -> ( a - > m c ) realized a composition ( sequential execution ) for functions that return a monadic type, but only use the relevant underlying type. The functor fmap :: (a -> b ) -> m a -> m b allowed to pass a monadic type to a function that uses only the underlying type. His first argument is a function that maps from the underlying type of the first argument to another, usually not monadic type. His second argument is a value from monadic type. The return value is of Monadentyp the underlying type of the return value of the function. A natural transformation join :: m (m a) -> m a which a " flattening " of the monadic type allows a nesting. (where m is the type constructor )
Allowed to pass a monadic type to a function that uses only the underlying type. His first argument is a value from 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 Monadentyp.
These operations must obey the following laws:
(ma >> = f) >> = g == ma >> = ( \ a -> ( ( fa) >> = g) ) Associativity of> => ( f > => g) > => h == f > => ( g> => h) Compatibility of concatenation and fmap fmap ( f. g ) == ( fmap f). ( fmap g) join is a natural transformation of fmap. fmap fmap on ( fmap f). join == join. ( ( fmap fmap. ) f) Commutativity of fmap and join join. join == join. ( fmap join) - the second join has the type m (m ( ma) ) -> m ( ma) return is a natural transformation from id to fmap ( fmap f). return == return. f Neutrality of return are >> = ma >> = return == ma (return a) >> = f == f a Neutrality of return are > => f > => return == return> => f == f Neutrality of return are > => in fmap / join notation join. return == join. ( fmap return) == id Based on Haskell
In Haskell a monad will return on the operations and defined (>> =):
Class Monad m where return :: a - > m a (>> =) :: M a -> (a -> m b ) -> m b The other operations can then be defined over these two:
( f > => g ) a = f a >> = g ( fmap f) ma = ma >> = (return. f) join mma mma = >> = id About the Kleisli operator
A monad can also be about their Kleisli category define:
Class Monad m where return :: a - > m a ( > => ) :: (A -> m b ) -> ( b -> m c ) -> ( a - > m c ) The remaining operations are then obtained 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 remaining operations can then be implemented as follows:
Ma >> = f = (join. ( fmap f)) ma f > => g = join. ( fmap g). f Relations with other type classes
Every monad is also an applicative functor and hence a functor. Conversely, this does not apply. This property can be found, however, for historical reasons not explicitly in Haskell's standard library.
Particularly clear, this relationship is also one compares the category theoretical definition with the functor class in Haskell:
Class Functor f where fmap :: (a -> b ) -> f a -> f b It must also meet the fmap compatibility condition with the composition (. ).
Examples
Container
Containers such as lists, sets, multisets represent monads whose bind operation applies the given function to all elements and combines the results obtained. The union operation is in each list concatenation, union formation or formation of the multiset union. The unit function returns singletons and lists.
Here as an example, the monad for linked lists. The concept of the instance for lists is to read a list, then pass each element to the function and to link the results. Here is an example implementation in Haskell:
- Here again a reminder of the list type is defined as follows: data [ A] = [] | a: [a] - As syntactic sugar can [a, b, c] for a: b: c: [ ] are used. instance Monad [ ] where - return :: a - > [ a] return a = [ a] - By definition, return a list with an element - (>> =) :: [A] - > (A -> [B ]) -> [b] list >> = f = concat between income where - Seat the sublists between results :: [ [b ] ] between results = map f list - reflect the function to the list Vectors and linear maps
The type constructor forms one type to a vector space, which keep serves as a ( named for a ) base, and its elements are modeled as functions, for example. The bind operation has the type. Swapping the arguments one obtains the type on which you can see the semantics: the given function, defined on the basis elements, is extended to a full linear mapping. The unit function is the base element ( which in this modeling still not a "real " vector ) onto the corresponding basis vector.
State I / O
In stateful actions the bind operation in achieving the sequential execution serves. The unit function creates an action that does nothing and returns a solid result.
The concept is quite natural. If you want to pass a variable status in a purely functional programming language, then you do it as a rule in the following way, here the example of a counter function:
- Increment the counter and return the old counter high count :: Int -> Int -> (Int, Int) increment step size was counter = ( counter reading, new counter reading ) where ... The basic principle is that you attach the old status as a parameter and the new with the return value returns together. To save work, this pattern can be easily packed in a new types, the parameter s of the type is the type of state, a is the parameter of the return value:
Data state s a = status ( s -> ( a, s) ) - Example: high count :: Int -> Int Int Status increment step size = $ status \ counter reading -> ( counter reading, counter stand increMent ) What we now need is a couple of functions that can manipulate the status. Here, for example, a function that sets the status to a new, and one that reads it:
SetStatus :: s - > State s ( ) setStatus s = State $ \ _ -> ( (), s) - The old status is ignored and replaced by the new one. Return value as unnecessary (). getStatus status :: s s getStatus = State $ \ s -> (s, s ) - Duplicate the status in the return value. This is almost all that is necessary. The only thing missing is the ability to combine multiple status changing actions, here are monads the tool of choice:
Instance Monad ( Status s ) where - The type variable s is irrelevant to the definition - return :: a - > a state s return a = State $ \ s -> ( a, s) - status remains unchanged - (>> =) :: Status sa - > (a - > State sb) - > Status sb (Status action1 ) >> = f = State $ \ s - feeding status of action1 in action2 -> action2 between status where. ( rückgabe1 between status) action1 = s - execute Action1 Status action2 = f rückgabe1 - feed return value from action1 in f With these functions and the syntactic sugar of the do- notation ( the monadic operations hidden from us ) can be the example then formulated as follows:
High count :: Int -> status ( int, int ) increment step size = do counter reading <- getStatus - determine counter status Set counter - setStatus ( counter reading increMent ) return counter reading - return old count is - Sugared Here increment step size = getStatus >> = \ counter reading -> setStatus ( counter reading increMent ) >> = \ _ -> return counter reading