Monade ... was ist das?

Es geht um: Syntax

C#

IEnumerable<Outfit> Outfits()
{
    return
        from schuhe in Schuhe
        from hose in Hosen
        from hemd in Hemden
        select new Outfit {Schuhe = schuhe, Hose = hose, Hemd = hemd};
}

Es geht um: DSLs

F#

let fetchAsync(url:string) : Async<string> =
    async { 
        try
            let uri = new System.Uri(url)
            let webClient = new WebClient()
            return! webClient.AsyncDownloadString(uri)
        with
            | ex -> printfn "Fehler: %s" ex.Message
    }

Es geht um: Kapselung

Haskell

main :: IO ()
main = putStrLn "Hello, World!"

Motivation

NullReferenceException

I call it my billion-dollar mistake.

Guards

var customer = GetCustomer(5);
if (customer != null) 
{
  var orders = GetOrdersFor(customer);
  if (orders != null) 
  {
    // ...
  }
}
return null;

ein Muster...

var customer = GetCustomer(5);
if (customer != null) 
{
  var orders = GetOrdersFor(customer);
  if (orders != null) 
  { /* ... */ } 
  else 
    return null;
} 
else 
  return null; 

refactor

public tR Guard<tS, tR>(tS source, Func<tS, tR> f)
  where tS : class
  where tR : class
{
  if (source != null) return f(source);
  else return null;
}

return Guard(GetCustomer(5), customer =>
  Guard(GetOrdersFor(customer), order => {
    // ...
  }));

syntactic sugar

public static tR Guard<tS, tR>(this tS source, Func<tS, tR> f)
  where tS : class
  where tR : class
{
  if (source != null) return f(source);
  else return null;
}

return GetCustomer(5).Guard(customer =>
  GetOrdersFor(customer).Guard(order => {
    // ...
  }));

können wir das eleganter lösen?

GetCustomer(5)?.Orders()?. ...

Maybe

Customer GetCustomer(int customerNumber)

Wenn eine Funktion partiell ist, dann sollte sie es auch zugeben

Sag es im Namen

Customer TryGetCustomer(int customerNumber)

Try/Can Pattern

bool TryGetCustomer(int customerNumber, out Customer customer)

Typen - was sonst?

Maybe<Customer> TryGetCustomer(int customerNumber)

type Maybe<'a> =
  | Just of 'a
  | Nothing

Hinweis: tatsächlich würde man F# Option<'a> verwenden

für C# gibt es schöne Hilfsmittel in FSharpx.Core

don't look so different

var customer = TryGetCustomer(5);
if (customer.IsJust)
{
    var orders = TryGetOrdersFor(customer.Value);
    if (orders.IsJust)
    { /* ... berechne irgendwas vom Typ Rückgabe */ }
    else
        return Maybe.Nothing<Rückgabe>();
}
else
    return Maybe.Nothing<Rückgabe>();

refactor (again)

return Bind(TryGetCustomer(5), customer =>
  Bind(TryGetOrdersFor(customer), order => {
    // ...
  }));

Bind

Maybe<tR> Bind<tS, tR>(Maybe<tS> source, Func<tS, Maybe<tR>> f)

{
  if (source.IsNothing) return Maybe.Nothing<tR>();

  else return f(source.Value);
}

Sugar ... more Sugar

C#: LINQ

return
from customer in TryGetCustomer(5)
from orders in TryGetOrdersFor(customer)
select ...

F#: Computation Expressions

maybe {
    let! customer = tryGetCustomer 5
    let! orders   = tryGetOrders customer
    return ...
}

Haskell: Do-Notation

beispiel :: Maybe Orders
beispiel = do
  customer <- tryGetCustomer 5
  orders   <- tryGetOrdersFor customer
  return orders

was müssen wir dafür tun?

LINQ

SelectMany implementieren:

public static Maybe<tR> SelectMany<tS, tR>
  (this Maybe<tS> source, Func<tS, Maybe<tR>> selector)
{
    return Bind(source, selector);
}

LINQ

nochmal SelectMany:

public static Maybe<tR> SelectMany<tS, tCol, tR>
  (this Maybe<tS> source, 
   Func<tS, Maybe<tCol>> collectionSelector, 
   Func<tS, tCol, tR> resultSelector)
{
    if (source.IsNothing) return Nothing<tR>();
    var col = collectionSelector(source.Value);
    if (col.IsNothing) return Nothing<tR>();
    return resultSelector(source.Value, col.Value);
}

im wesentlichen Bind + Tranformation/Select

F#

Builder implementieren:

type MaybeBuilder() =
    member x.Bind(m, f)    = bind m f
    member x.Return(v)     = Just v

let maybe = MaybeBuilder()

Haskell

Monad Typklasse instanzieren:

instance Monad Maybe where
  return = Just
  Nothing >>= _ = Nothing
  Just a  >>= f = f a

List Monad

Ziel

nicht-deterministische Ergebnise repräsentieren

was ist zu tun?

Listen [a] sollen zum Monaden werden

(>>=) :: [a] -> (a -> [b]) -> [b]

return :: a -> [a]

Return

return :: a -> [a]

Intuition: einen Wert in eine Liste packen

Return

Haskell:

return :: a -> [a]
return x = [x]

F#:

let return (x : 'a) : 'a list = [x]

Bind

(>>=) :: [a] -> (a -> [b]) -> [b]

Intuition:

• jedes Element gibt wieder eine Liste
• zusammen also eine Liste von Listen
• diese gilt es plattzumachen

Bind

Haskell:

(>>=) :: [a] -> (a -> [b]) -> [b]
xs (>>=) f = concatMap f xs

F#:

let bind (xs : 'a list) (f : 'a -> 'b list) : 'b list =
  xs |> List.collect f

Beispiel

Permutation einer Liste/Aufzählung

Rezept:

• Nimm ein Element x heraus
• Nimm eine Permuation xs der restlichen Elemente
• x:xs ist eine Permutation
• Liste alle solchen Permuationen auf

F#

let ohne x =
    List.filter ((<>) x)

let rec permutationen = function
  | [] -> [[]]
  | xs -> [ for x in xs do
            let rest = xs |> ohne x
            for xs' in permutationen rest do
            yield (x::xs') ]

Haskell

import Data.List (delete)

perm :: (Eq a) => [a] -> [[a]]
perm [] = return []
perm xs = do
  x <- xs
  xs' <- perm $ delete x xs
  return $ x:xs'

C#/LINQ

IEnumerable<IEnumerable<T>> Permuationen<T>(IEnumerable<T> items)
{
    if (!items.Any()) return new[] {new T[] {}};

    return
        from h in items
        from t in Permuationen(items.Where(x => !Equals(x, h)))
        select h.Vor(t);
}

C#/LINQ

Hilfsfunktion

IEnumerable<T> Vor<T>(this T value, IEnumerable<T> rest)
{
    yield return value;
    foreach (var v in rest)
        yield return v;
}

Wahrscheinlichkeiten

inspieriert durch

Risiko

let ``Verluste beim Risiko (3 gegen 2)`` =
    vert {
        let! offensive = nWürfel 3
        let! defensive = nWürfel 2
        let defensivVerluste = 
            List.zip (offensive |> List.sort |> List.tail)
                     (defensive |> List.sort)
            |> List.sumBy (fun (o,d) -> if d >= o then 0 else 1)
        return sprintf "%d:%d" (2-defensivVerluste) defensivVerluste
    } |> printVerteilung

> 
"0:2": 37.17%
"1:1": 33.58%
"2:0": 29.26%

Darstellung

Eigentlich nur die List-Monade mit Wahrscheinlichkeiten

type Wahrscheinlichkeit = double
type Verteilung<'a> = ('a * Wahrscheinlichkeit) list

Return

Entspricht dem sicheren Ereignis

let sicher (a : 'a) : Verteilung<'a> =
    [a, 1.0]

let returnM (a : 'a) : Verteilung<'a> =
  sicher a

Bind

folge einem dynamisch erzeugten Baumdiagramm und multipliziere die Wahrscheinlichkeiten.

Beispiel

let ``Mensch ärgere dich (nicht?)`` =
    vert {
        let! w1 = würfel
        if w1 = 6 then return "ich komm raus" else
        let! w2 = würfel
        if w2 = 6 then return "ich komm raus" else
        let! w3 = würfel
        if w3 = 6 then return "ich komm raus" else
        return "grrr"
    }

val ( Mensch ärgere dich (nicht?) ) : Verteilung<string> =
  [("grrrr", 0.5787037037); ("ich komm raus", 0.4212962963)]

Baumdiagramm

Baumdiagramm

Baumdiagramm

Bind

let bind (v : Verteilung<'a>) (f : 'a -> Verteilung<'b>) 
         : Verteilung<'b> =
    [ for (a,p) in v do
      for (b,p') in f a do
      yield (b, p*p')
    ] |> normalize

Detail

normalize fasst nur die Ergebnise additiv zusammen

let normalize (v : Verteilung<'a>) =
    let dict = new System.Collections.Generic.Dictionary<_,_>()
    let get a = if dict.ContainsKey a then dict.[a] else 0.0
    let add (a,p) = dict.[a] <- get a + p
    v |> List.iter add
    dict |> Seq.map (fun kvp -> (kvp.Key, kvp.Value)) 
         |> List.ofSeq

FsCheck Generator

FsCheck?

• Testet Eigenschaften von Funktionen/Programmen automatisch.
• Eigenschaft: prop : 'input -> bool
• FsCheck generiert zufällige Eingaben und testet ob die Eigenschaft jeweils true liefert.

Doku/Info https://fsharp.github.io/FsCheck/QuickStart.html

Beispiel

let ``zweimal List.rev ist Identität``(xs : int list) =
    List.rev (List.rev xs) = xs

Check.Quick ``zweimal List.rev ist Identität``
> Ok, passed 100 tests.

let ``List.rev ist Identität``(xs : int list) =
    List.rev xs = xs

Check.Quick ``List.rev ist Identität``
> Falsifiable, after 3 tests (6 shrinks) (StdGen (1233601158,295877135)):
> [1; 0]

Generatoren

Um die Testfälle zu generieren verwendet FsCheck Generatoren

type Würfel = internal W of int
let würfel n = 
    if n < 1 || n > 6 
    then failwith "ungültiger Wert"
    else W n

let würfelGen =
    gen {
        let! n = Gen.choose (1,6)
        return würfel n
    }

Definition

vereinfacht: Generator ist eine Aktion, die einen zufälligen Wert liefert

type Gen<'a> = Gen of (unit -> 'a)

let sample (Gen g : Gen<'a>) : 'a =
    g()

make it monadic

Gesucht: Implementation von

bind : Gen<'a> -> ('a -> Gen<'b>) -> Gen<'b>

und

return : 'a -> Gen<'a>

Return

return : 'a -> Gen<'a> = 'a -> (unit -> 'a)

Intuition: zufällige Wahl aus einem Element ...

let returnM (a : 'a) : Gen<'a> =
    Gen <| fun () -> a

Bind

Gen<'a> -> ('a -> Gen<'b>) -> Gen<'b> =
(unit -> 'a) -> ('a -> (unit -> 'b)) -> (unit -> 'b)

let bind (m : Gen<'a>) (f : 'a -> Gen<'b>) : Gen<'b> =
    Gen <| fun () -> sample (sample m |> f)

Async

MSDN example

let fetchAsync(name, url:string) =
    async { 
        try
            let uri = new System.Uri(url)
            let webClient = new WebClient()
            let! html = webClient.AsyncDownloadString(uri)
            printfn "Read %d characters for %s" html.Length name
        with
            | ex -> printfn "%s" (ex.Message);
    }

simplify

verkettete Continuations/Callback

Continuation

type Cont<'a>  = 'a -> unit 

• Nebeneffekt behaftete Aktion
• wird mit dem Ergebnis einer (asynchronen) Berechnung aufgerufen

Continuation monad

type ContM<'a> = { run : Cont<'a> -> unit }

let mkCont (f : Cont<'a> -> unit) : ContM<'a> = 
    { run = f }    

• gib mir eine 'a Continution c
• ich berechne ein 'a und rufe c damit auf
• kann verzögert/asychron erfolgen

Beispiel

let delay (span : TimeSpan) : ContM<unit> =
fun f ->
    let timer = new Timer()
    timer.Interval <- int span.TotalMilliseconds
    timer.Tick.Add (fun _ -> timer.Dispose(); f())
    timer.Start()
|> mkCont

make it monadic

let returnM : 'a -> ContM<'a> = ...

let bind : ContM<'a> -> ('a -> ContM<'b>) -> ContM<'b> =

Return

let returnM (a : 'a) : ContM<'a> =
    mkCont (fun f -> f a)

rufe die übergebene Continuation sofort mit a auf

Bind

let bind : ContM<'a> -> ('a -> ContM<'b>) -> ContM<'b> =

=  (('a -> unit) -> unit) 
-> ('a -> (('b -> unit) -> unit)) 
-> (('b -> unit) -> unit)

let the TYPES guide you luke

Bind

let bind (f : 'a -> ContM<'b>) (m : ContM<'a>) : ContM<'b> =
  fun (c : Cont<'b>) ->
      m.run <| fun a -> (f a).run c
  |> mkCont

example

let runWith (f : 'a -> 'b) (m : ContM<'a>) = 
    m.run (f >> ignore)

let verzögertesHallo() =
    cont {
       do! delay <| TimeSpan.FromSeconds 2.0
       return "Hello, World!"
    } |> runWith MessageBox.Show

State

Motivation

Berechnungen mit Zustand:

f :: zustand -> a -> (b, zustand)
g :: zustand -> b -> (c, zustand)

let (b, z1) = f z0 a
let (c, _)  = g z1 b
c

to much freedom

f :: zustand -> a -> (b, zustand)

• Bisher: immer ein generischer Parameter im Monaden
• jetzt: drei: zustand, a und b

functional trickster

ein wenig umformen:

f :: a -> (zustand -> (b, zustand))

hier ist ein Monade versteckt

and the candiate is

Haskell:

data State s a = MkState { runState :: s -> (a, s) }

F#:

type State<'s,'a> = { runState : 's -> ('a*'s) }
let mkState f = { runState = f }

make it monadic

return :: a -> State s a
(>>=)  :: State s a -> (a -> State s b) -> State s b

Return

Haskell:

return :: a -> State s a
return a =  MkState $ \s -> (a, s)

F#

let return (a : 'a) : State<'s, 'a> =
  mkState <| fun s -> (a, s)

reiche den Zustand weiter und gib den Wert zurück

Bind

Haskell

(>>=)  :: State s a -> (a -> State s b) -> State s b
State f >>= g = 
    MkState $ \s -> let (a,s') = f s 
                    in runState (g a) s'

F#

let bind (g : 'a -> State<'s,'b>) (f : State<'s,'a>) : State<'s,'b> =
    fun s ->
        let (a,s') = f.runState s
        (g a).runState s'
    |> mkState

Komposition

Problem war ja:

f :: a -> (State s b)
g :: b -> (State s c)

gesucht Operator op mit

f `op` g :: a -> (State s c)

Implementation

Haskell:

op :: (a -> State s b) -> (b -> State s c) -> (a -> State s c)
op f g = \a -> f a >>= g

F#:

let op f g =
    fun a -> bind (f a) g

Übrigens...

HLint:

Error: Use >=>
Found:
  \ a -> f a >>= g
Why not:
  f Control.Monad.>=> g

das ist die Kleisli Komposition für Monaden ...

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

§ Gesetze §

Monade sollte erfüllen:

Warum?

rein mathematisch sind diese Gesetze unbedingt nötig um sich Monade zu nennen.

siehe etwa: Category Theory & Programming

Rechts-Identität

m >>= return === m

[ y | x <- xs; y <- [x] ] === xs

return
   from x in xs
   from y in new[]{x}
   select y;

return xs;

Links-Identität

return a >>= f === f a

return
   from x in new []{a}
   from y in f x
   select y;

return f(a);

Assoziativität (linke Seite)

(m >>= f) >>= g === m >>= (\x -> f x >>= g)

LINQ / C#

var zw1 =   
   from x in xs
   from y in f(x)
   select y;
return
   from y in zw1
   from z in g(y)
   select y;

Assoziativität (rechte Seite)

(m >>= f) >>= g === m >>= (\x -> f x >>= g)

LINQ / C#

Func<X,IEnumerable<Z>> zw1 =
  x => from y in f(x)
       from z in g(y)
       return z;
return
  from x in xs
  from z in zw1(x)
  select z;  

Assoziativität

oder einfach

LINQ / C#

return
  from x in xs
  from y in f(x)
  from z in g(y)
  select z;  

Assoziativität Kleisli

und mit Kleisli

(f >=> g) >=> h === f >=> (g >=> h)

sieht es sogar wie Assoziativität aus!