wiki:Monads2

Monad is just an ADT. Period.

The amount of nonsense repeated about monads is unimaginable. The famous meme Idiots, idiots everywhere.. comes to mind.

Monad is a parametrized type. This means that there is some type-constructor that takes a value of type a and returns a value of type m a.

The technical term "type-constructor" is misleading, because what it returns is data, not a type, which is mere an abstraction. So it should be called data-constructor.

Logically (and technically), it is equivalent to attaching of an additional type-tag to a value of some "primitive" type (already tagged).

Just having a new type tag attached is not enough. The tags (or similar "marking" mechanism) are used by type-checker.

To be a Monadic, an ADT must implement at least two procedures. So-called bind which is traditionally denoted in Haskell as >>= and return.

return is simple - it is just a data-constructor. It what they call it lifts a value in a world of Monads. Logically it just attaches an additional type-tag to a given value.

>>= is messy. Its type in Haskell is m a -> (a -> m b) -> m b. It is a binary operator which supposed to be written m >>= f which in Haskell means a curried procedure.

The function f must be of the type a -> m b which means, it must apply the return procedure to the result of computation as its last expression. This would be in turn a return value of >>= procedure.

This is an interface an ADT should implement to be Monadic.

Makes any sense? NO. Here is why.

In a lazy "pure-functional" languages such as Haskell (in contrast with, say, Erlang, which is also "pure-functional" but eager), the order of evaluation of an expression is undefined. This means that sub-expressions of a compound expression could be evaluated (reduced) in any order - not just left-to-right or right-to-left (sequentially) but out-of-order, even (in parallel).

What >>= does is "takes a value of type m a, strips Monad type-tag from a value, takes a procedure f to be applied to a value of type a, wraps an application of a procedure to the value into a thunk and returns it. (Technically, thunk is created implicitly by language runtime). This thunk, when evaluated, would produce a value of type m b.

Does it make sense? Little.

Here comes the realization. Monads makes no sense in strict languages. In these languages we don't have to create an implicit thunk (which is just a lambda expression) to ensure a sequential order of evaluation. There are special forms for that, like begin or progn or for-each.

So what is a Monad type really? It is an awkward way of what they call it "to abstracting a sequential computation" in a language without well-defined evaluation order. All these idioms and silly function names are mere accidents from some obscure "scientific" paper.

It is here not because it is some fundamental thing (why, it is just an awkward ADT), but because idiots everywhere copy-pasted pieces of code from each other without deep understanding what it really does and what it is for.

Now look, given that ma and mb are thunks of type m a and m b respectively (types are for a type-checker), the expression ma >> mb is nothing but (begin (force ma) mb) and ma >>= f is (f (force ma)) where f must apply (delay ...) as its last expression.

So, ma >> mb is force ma, return mb as is (unevaluated). This is for side-effects.

and ma >>= f is force ma, then make a new "thunk", which when evaluated, will apply f to a. This is for "serialization" in a non-strict language.

Note that >>= "forces" ma into a. Or we could say "strips m form m a".

Note that f must use return.

This "generator-like" do-notation

do 
   a <- ma
   b <- mb
   return (a+b)

is just a syntactic sugar for nested lambdas

ma >>= (\a ->
  mb >>= (\b ->
      return (a + b)))

For a nice visualization we could think of ma >> mb as a rough equivalent of $ cp xxx yyy ; sync and ma >>= f is a-la $ cat xxx | grep yyy or a pipe. The crucial difference that only the first (leftmost) parameter is fully evaluated, and a promise (a thunk to be "forced" later) is returned.

Notice that these expressions are made of nested lambdas and a "binding" procedure >>=, so x and y are lexical scoped bindings, used in return expression.

getChar >>= \x -> getChar >>= \y -> return (x,y)

which is rather an awkward way to pass a value from "effectful", "non-pure", "unsafe" (getChar) to a nested (lambda (x) ...

(>>= (getChar) (lambda (x)
                   (>>= (getChar) (lambda (y)
                                     (return (list x y))))))

Remember that >>= does "strict evaluation" of its first argument - a monad (in Scheme it would be (force m)) and "binds" (or captures) the value to a given procedure (creates a closure).

(define (>>= m f)
  (f (force m)))

In Haskell everything type-checks (ensures correct types of each binding and a valid structure of whole expressions. It does NOT guarantee correctness of execution or any kind of "safety").

Actually, in Haskell x and y are patterns. In this case they are unbound variables, so they match any value.

do
  x <- getChar
  y <- getChar
  return (x,y)

a Monad is mere an ADT - a construct to explicitly pass a value from in a non-strict language. To ensure the order of evaluation they are using "nested lambda expressions" or do notation as a syntactic sugar.

Why do we have this >>= procedure instead just nesting? To make a type-checker "happy", to annotate "passing of a value" from m a to a procedure that takes a and produces a new Monad m b.

That's all.


In a strict languages Monad is just a meaningless ADT:

constructor (add a type-tag)

(define (make-monad x)
  (cons 'monad x))

selectror (strip a type-tag)

(define (monad-get m)
  (cdr m))

predicate

(define (monad? x)
  (eqv? 'monad (car x)))

to be used in a -> m a procedures

(define return make-monad)

procedure application, f must use return

(define (>>= m f)
  (f (monad-get m)))

That is it. This is what your Monadic IO really does. >>= strips type information and applies a given procedure f to a value of type a. The f procedure itself must call return with the value it produces to stick the type-tag back. The result of the last expression will be the result of a whole procedure f.

eval a, return b

(define (>> a b)
  (>>= a (lambda (_) b)))

Show me, please, where the "safety" of Monadic IO comes from..


For each new type we have to >>= and return to be implemented.

For lists it would be

(define return (lambda (x) (cons x '())))
(define (>>= xs f)
   (map f xs))
Last modified 4 years ago Last modified on Nov 24, 2014, 8:54:16 PM