Monads en zo

Wat ik er nu van begrijp

(Opmerkingen / aanvullingen dus welkom.)

Het gaat om operaties op elementen (waarden of functies), vaak (ingekapseld) binnen een structuur, een context.
List en Maybe/Option bijvoorbeeld hebben een samengesteld "kind" (metatype): ze hebben een ander type nodig voor de constructie. Ze zijn daarmee de context van dat andere type.
Die operaties gaan goed als die elementen of structuren aan een aantal laws voldoen.
Die laws monden vaak uit in primitives, typeclass-methoden.
Er zijn vijf groepen (type-classes) elementen of structuren. Die voldoen aan een oplopend aantal laws, waar
- steeds minder elementen aan voldoen.
- steeds meer operaties op zijn toegestaan.
Er is een cesuur tussen Monoid en Functor (Functor is geen stricte subclass van Monoid). Sommige Monads of Functors kunnen optreden als Monoid.
Het laatste klopt niet in stricte zin: een Monoid betreft altijd concrete types (vereist geen typeparameter, zoals bij Int, of die parameters zijn ingevuld, zoals bij List Char).
Een Functor (en dus ook een Monad) vereist een parameter (is een context).

Laws

Het gaat steeds om een set S met bijbehorende binary operatie O.
Sommige "synoniemen" betreffen weliswaar dezelfde operatie, maar horen bij verschillende niveaus. Zo is Ap de Monad-versie van <*> (Applicative Functor-versie).

Closure: Toepassen van O op twee elementen van S levert weer een element van S op.
Associativity: Bij het paarsgewijs combineren van elementen doet de volgorde er niet toe.
(Soms wel van de elementen, zoals bij string-concatenatie, maar niet van de operaties, de plaats van de haakjes.
Aftrekken is zodoende niet associatief, (5 - 3) - 4 != 5 - (3 - 4))
Identity of zero: er bestaat een identityelement met een identity operatie die het uitgangselement oplevert.
(Bij optellen is dit bijvoorbeeld 0, bij vermenigvuldigen 1, bij het bepalen van een maximum -∞.)
Compose: f(g(a)) = f•g(a)
Pure, unit of return: def pure[A] (a:A) : F[A]
<*> of ap: def ap[A, B] (fa:F[A]) (fab: F[ A=>B ]) : F[B]
override def map [A,B] (fa: F[A]) (fab: A => B): F[B]=ap(fa)(pure(fab))
flatMap (of bind, >>=)

Het nut van Monads voor de programmeur

Ik spreek hier alleen over Monads. Het zal duidelijk zijn dat voor sommige toepassingen het zijn van bijvoorbeeld Functor toereikend is.

Veel standaardtypen, zoals Lists in Haskell en Scala, zijn bulkcontainers, en ze zijn ook vaak Monads. Dat geldt soms ook voor zelf gedefinieerde typen zoals een Tree.
Bewerkingen op de componenten daarvan zijn vaak gemakkelijk te combineren of aaneen te schakelen (composing of chaining).
Andere bulkbewerkingen leveren een totaalresultaat op (reducing of folding).
"Kleinere" standaardtypen (zoals Maybe/Option van respectievelijk Haskell/Scala) kunnen gebruikt worden om uitzonderingsgevallen elegant af te handelen.
Als een component niet bestaat of een fout oplevert kan die worden genegeerd, of kan de totale bulkoperatie worden afgeblazen zonder eindeloze if-then-else, case of try-catch constructies.
Monads worden ook gebruikt om operaties met zij-effecten af te handelen. Het kan daarbij gaan om het rapporteren van tussenresultaten (logging), IO-operaties, random-input of het bijhouden van state.
In puur functionele code is dit allemaal onmogelijk (functies leveren eenduidig resultaat op basis van hun input en veranderen niets aan de buitenwereld). Met Monads echter is hier een mouw aan te passen, doordat het bijeffect in de context wordt meegenomen en in de implementatie van >>= wordt verdisconteerd. Vooral in Haskell is dit soort code duidelijk te onderscheiden van de puur functionele code. (In Scala valt te smokkelen, maar in Haskell zijn bijeffecten beperkt tot dit soort Monads.) In Scala is de for-expression de ideale syntax om met Monads om te gaan.
Functionele talen kenmerken zich door een focus op data-flow i.p.v. control-flow, en daarbij ook op het gebruik van zeer uitgebreide standaardbibliotheken met geoptimaliseerde standaardfuncties voor standaard-datastructuren (vaak Monads). Dit i.t.t. de OOP (Object Oriented Programming) benadering van het bouwen van custom datastructuren met custom operaties.
Het puur functionele deel van de code bestaat eerder uit een verzameling definities of vergelijkingen zonder invloed op de buitenwereld (zoals dat gebruikelijk is in de wiskunde), dan uit een seriële opeenvolging van instructies (met aanpassing van veranderlijke variabelen) zoals bij vooral imperatieve, maar ook OOP-code het geval is. De code is nog steeds sequentieel, maar de nadruk ligt toch minder op de volgorde van de instructies, want definities, eenmaal gedefiniëerd, sprokkelt de compiler zelf wel bij elkaar. Bij lazy evaluatie wordt die volgorde zelfs irrelevant.
Zodoende wordt vaak gezegd dat een functionele programmeur zich meer bezighoudt met beschrijving van het wat dan van het hoe.

I. Semigroep
Voorbeelden Constructor: *	Set gehele getallen met + of * operatie: (4 + 10) + 2 = 4 + (10 +2) Voorbeelden zonder identity: positieve gehele getallen met + operator, of niet-lege sequenties.
Laws	Closure en Associativity
Operatie	append

II. Monoid
Voorbeelden	Set gehele getallen met + of * operatie: a+0=a, a*1=a Lists, Bool, Ordering, Maybe, zelfgedefinieerde Tree. Verzameling met operatie, die je (recursief) kunt uitbreiden.
Laws	Als Semigroep, met Identity mempty `mappend` x = x x `mappend` mempty = x (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z) mempty vertegenwoordigt het identity-element voor een bepaalde monoid met operatie, mappend is de binaire functie. mconcat is een secundaire functie die een lijst monoids via een fold-operatie reduceert tot een enkele waarde. (mconcat is een ongelukkige naam, bij een optelling bijvoorbeeld wordt er niets aan elkaar geplakt.)
Operaties	Als Semigroep, aangevuld met de zero-operatie.

III. Functor
Voorbeelden Unary type constructor: -> Binary type constructor: ->->* Functor[F[_]]	Scala: List, Option, Set, Either, Try, Future... Haskell: List, Maybe, eigen Tree, Either, Function ... "Alles waarover gemapt kan worden", het toepassen van een functie op waarde[n] in een context. Mapping over een functie is functie-composition (Nicholas, zie ook LYAH Functor)
Laws	Identity en Compose 1. Indentity fmap id = id 2. Compose fmap (f . g) = fmap f . fmap g , oftewel fmap (f . g) F = fmap f (fmap g F)
Operatie	Eén typeclass-methode: fmap :: (a -> b) -> f a -> f b (map is de List-implementatie van fmap) Map, Either, Function1 zijn binary, daarbij moet de operatie partieel, in stappen worden toegepast.

IV. Applicative (-Functor)
Voorbeelden	Voorlopig: De toegepaste functie kan zich zelf ook binnen een context bevinden
Laws	pure f <> x == fmap f x pure id <> v == v pure (.) <> u <> v <> w = u <> (v <> w) pure f <> pure x = pure (f x) u <> pure y = pure ($ y) <> u
Operaties	Als Functor, met Pure (Wrapt value in applicative), en ap of *<>**(Neemt een applicative met een functie er in en een andere applicative, extraheert de functie(s) uit de eerste en mapt die over de tweede). Applicatives zijn composable, wat niet voor elke Monad zo is.

V. Monad
Voorbeelden Higher order type operator: (->)->* Monad[M[_]] M[_] staat voor een unary type-constructor als List of Option	Scala: List, Option, Set, Either, Try, Future... Haskell: List, Maybe, Tree?, Either, ... "Informeel is een Monad alles met een constructor en een flatMap methode."
Laws	Left identity return x >>= f is het zelfde als f x Right identity m >>= return is gelijk aan m Associativity Het resultaat van (m >>= f) >>= g is gelijk aan dat van m >>= (\x -> f x >>= g)
Operaties `class Applicative m => Monad m where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b fail :: String -> m a`	Als Applicative, met bind, >>= of do-notation. (In Scala: flatMap.) Naast bind dient return voor het wrappen van een waarde in de monad (een "lift"-functie, zoals pure bij de applicative), en >> ("then") voor het chainen van monadische acties die het resultaat van de voorganger niet nodig hebben. fail is alleen intern nodig voor pattern-match failures in do-notation.

Net als de Applicative (-Functor) is ook Arrow een superclass van Monad, maar deze past niet helemaal in dit rijtje. Arrows missen een andere law en hebben een ander toepassingsgebied (o.a. parsers).