Co to jest monada w programowaniu funkcyjnym?

Co to jest monada? Czy jest to po prostu kontener?
Tzn zdaje sobie sprawę z dwóch obowiązkowych funkcji (return, bind czyli apply i flatMap) ale jest np takie zdanie na wikipedii:

Programy pisane w stylu funkcyjnym mogą korzystać z monad do strukturalizowania procedur zawierających operacje wykonywane sekwencyjnie, albo definiować pewne wymagane przepływy sterowania (takie jak współbieżność, kontynuacje, efekty uboczne tj. obsługa I/O lub wyjątki).

Jak to rozumieć?

Cytując klasyka: A monad is just a monoid in the category of endofunctors. (źródło)

Monady mogą być użyte do symulacji IO w językach funkcyjnych, ale wcale tak być nie musi. Monada to coś dużo bardziej ogólnego i wcale nie związanego jakoś specjalnie z IO. Monadę tworzą dwie operacje:

1. unit :: a -> m a - opakowanie "czystej" wartości w swoiste monadyczne pudełko.
2. bind :: m a -> (a -> m b) -> m b - otwieramy monadyczne pudełko, manipulujemy wartością, zamykamy pudełko (otrzymując nową wartość monadyczną).
   Które spełniają prawa monad
3. unit(a).bind(f) == f(a)
4. m.bind(unit) == m
5. m.bind(f).bind(g) == m.bind(λx -> f(x).bind(g))
   W praktyce prawa te zapewniają intuicyjne zachowanie. Dużo łatwiej zobaczyć dlaczego powinny być spełnione w haskellowej notacji do, która po kompilacji korzysta z return (unit) oraz >>= (bind).

do { y <- return x; f y } == do { f x } 

do { x <- m; return x } == do { m } 

do { y <- do { x <- m
               f x
             }
     g y
   }
==
do { x <- m
     do { y <- f x
          g y
        }
   }
==
do { x <- m
     y <- f x
     g y
   }

Z praktycznego punktu widzenia monady pozwalają na wygodne odseparowanie sposobu łączenia wyników w jedno od samych operacji, które chcemy przeprowadzić.

Przykład: monada Maybe; reprezentuje obliczenia, które mogą się nie powieść. Jest przydatna do kodu w rodzaju:

var x = findSomething(); // Może zwrócić null, jeśli nic nie znajdzie!
if (x === null) return null;
var y = findSomethingElse(x); // Znów może zwrócić null, gdy nie znajdzie.
if (y === null) return null;
var z = lookup(x,y); // Same story...
if (z === null) return null;
return z;

Taki kod jest nieelegancki. Cały czas musimy się powtarzać. Chcemy po prostu napisać:

var x = findSomething();
var y = findSomethingElse(x);
return lookup(x,y);

bez martwienia się o ciągłe sprawdzanie czy coś nie jest przypadkiem null-em. Monadycznie można by to zapisać jako:

var Maybe = function(x) {
    return {
        bind: function(f) {
            return (x === null) ? null : f(x);
        }
    };
};

var findSomething = function() { return Maybe(3); };
var someFailure = function() { return Maybe(null); };
var findSomethingElse = function(x) { return Maybe(x+5); };
var lookup = function(x,y) { return Maybe(x*y); };

findSomething().bind(function(x) {
    return findSomethingElse(x).bind(function(y) {
        return someFailure().bind(function() {
            return lookup(x,y).bind(function(z) {
                print('To sie nie wykona');
            });
        });
    });
});

findSomething().bind(function(x) {
    return findSomethingElse(x).bind(function(y) {
        return lookup(x,y).bind(function(z) {
            print('val = ' + z);
        });
    });
});

(ideone)
Oczywiście wygląda to okropnie, ale już np. w Haskellu wygląda dużo lepiej, dzięki notacji do, która pod spodem robi mniej więcej to samo co ten kod Javascript.

import Prelude hiding(Maybe(..), lookup)


data Maybe a = Just a | Nothing deriving (Show)
instance Monad Maybe where
  return x = Just x
  (Just x) >>= f = f x
  Nothing >>= _  = Nothing

findSomething :: Maybe Int
findSomething = return 3

findSomethingElse :: Int -> Maybe Int
findSomethingElse x = return (x+5)

lookup :: Int -> Int -> Maybe Int
lookup x y = return (x*y)

someFailure :: Maybe a
someFailure = Nothing

findThemAll :: Maybe Int
findThemAll = do
  x <- findSomething
  y <- findSomethingElse x
  lookup x y

findThemAllFail :: Maybe Int
findThemAllFail = do
  x <- findSomething
  someFailure
  y <- findSomethingElse x
  lookup x y
  
main = print findThemAll >> print findThemAllFail

(ideone)

Chyba pojąłem o co chodzi z monadami jako łączenie (łańcuchowanie - chaining) operacji na "stanie świata" i idee braku efektów ubocznych. W takim razie, jak mają się do tego kolekcje w Scali?

Każda kolekcja, w tym Option, jest monadą. Ale monadami są jeszcze inne rzeczy, np Either.
Monady można by zaklepać i w Javie, tylko kod byłby paskudny bez Haskellowego 'do' czy Scalowego 'spimpowanego for'.

Oprócz kolekcji jest jeszcze wiele innych monad. Dla przykładu kontynuacje: Kontynuacje

Opisanie czym jest monada na chłopski rozum jest tak trudne, że chyba nikt tego tak wprost nie wytłumaczył :P Dlatego szukanie takiego prostego opisu jest raczej antyproduktywne. Moim zdaniem lepiej po prostu porozpisywać sobie jak działają monady, tzn wziąć coś z Haskella w notacji 'do' albo w Scali z użyciem 'for' i rozpisać to na wywołania funkcji monadycznych.

Oak powyżej dał bardzo ładny przykład jak monada Maybe w Haskellu (ale tak samo byłoby z szeroko używaną monadą Option w Scali) ładnie upraszcza kod w przypadku gdy chcemy pozwolić by funkcje nic nie zwracały. W Javie od tego jest null oraz drabinki ifów sprawdzających czy coś jest nullem, co jest nieczytelne i rozwlekłe - dlatego się tak nie robi. Czasami się tylko dodaje adnotację @Nullable lub @NotNullable, ale to nie rozwiązuje tylu problemów co Maybe/ Option (ale przy okazji nie dodaje narzutu, więc jest coś za coś).