Monady¶

Slajdy: http://www.cs.put.poznan.pl/ksiek/fp/monads/

Memoizacja¶

Problem: funkcje które obliczają wynik tylko wtedy, jeśli nie był on obliczony wcześniej.

val add : (Int, Int) => Int = (x, y) => x + y
val mul : (Int, Int) => Int = (x, y) => x * y

add(2,2)
mul(2,2)

Pomysły?

Rozwiazanie stanowe¶

Wprowadzamy mapę która pamięta wyniki.

type Key = (Symbol, Int, Int)
type Memory = Map[Key, Int]
def  Memory = Map[Key, Int]()
var  memory = Memory

Podczas wykonywania obliczeń sprawdzamy i uaktualniamy mapę:

val add : (Int, Int) => Int = (x, y) => {
  val key = ('add, x, y)
  if (memory contains key) memory(key)
  else {
    val result = x + y
    memory += (key -> result)
    result
  }
}

val mul : (Int, Int) => Int = (x, y) => {
  val key = ('mul, x, y)
  if (memory contains key) memory(key)
  else {
    val result = x * y
    memory += (key -> result)
    result
  }
}

Wykonanie:

add(2,2)
mul(2,2)

Rozwiazanie bezstanowe¶

Wyrzucenie zmiennego stanu:

type Key = (Symbol, Int, Int)
type Memory = Map[Key, Int]
def  Memory = Map[Key, Int]()

Zmiana typu funkcji:

val add : (Int, Int) => Int = ???
val add : (Int, Int, Memory) => (Memory, Int) = ???
val add : (Int, Int) => Memory => (Memory, Int) = ???

Implementacja:

val add : (Int, Int) => Memory => (Memory, Int) = (x, y) => memory => {
  val key = ('add, x, y)
  if (memory contains key) (memory, memory(key))
  else {
    val result = x + y
    val newMemory = memory + (key -> result)
    (newMemory, result)
  }
}

val mul : (Int, Int) => Memory => (Memory, Int) = (x, y) => memory => {
  val key = ('mul, x, y)
  if (memory contains key) (memory, memory(key))
  else {
    val result = x * y
    val newMemory = memory + (key -> result)
    (newMemory, result)
  }
}

Wywołanie:

val state1 = Memory
val (state2, result1) = add(2,2)(state1)
val (state3, result2) = mul(2,2)(state2)

Ręczne przekazywanie stanu między funkcjami: nieestetyczne i łatwo popełnić błąd.

val state1 = Memory
val (state2, result1) = add(2,2)(state1)
val (state3, result2) = mul(2,2)(state1)

Obiekty w celu uporządkowania obliczeń¶

class State(memory: Memory, result: Int) {
  def >>= (f : (Memory => (Memory, Int))) : State = {
    val (newMemory, result) = f(memory)
    new State(newMemory, result)
  }
  def get = result
}

val state = new State(Memory, 0)
state >>= add(2,2) >>= mul(2,2)

Monady¶

Monada to struktura rozbijająca wykonanie obliczeń na etapy (akcje).

Wzorzec programowy

Programowalny średnik

Endofunktor (teoria kategorii)

Horror + magia (HP Lovecraft?)

Teoria¶

Monada M to obiekt który jest kontenerem dla jakiegoś obiektu (lub kolekcji obiektów) typu T (t.j. M[T]). Monada posiada:

konstruktor typu M[T]

operację return (aka unit) typu T => M[T]:

wstrzykuje obiekt typu podstawowego do monady

operację bind (aka >>= lub flatMap) typu M[T] => (T => M[T2]) => M[T2]:

mapuje monadę wejściową na monadę wyjściową za pomocą podanej funkcji:

wyciąga obiekt typu podstawowego z monadu

aplikuje przekazaną funkcje dla obiektu typu podstawowego (dla każdego z obiektów typu podstawowego)

opcjonalnie, w szczególności dla kolekcji obiektów: wyciągnięcie obiektów typu podstawowego z monad uzyskanych z wykonania funkcji

złożenie obiektów z 3 i opakowanie w monadę, która jest wynikiem operacji

Aksiomaty:

return(x) >>= f ≡ f(x)

monad >>= return ≡ monad

monad >>= f >>= g ≡ monad >>= (x) => f(x) >>= g

Monada Stanowa¶

type Key = (Symbol, Int, Int)
type Memory = Map[Key, Int]
def  Memory = Map[Key, Int]()

object State {
  def unit(memory: Memory, result: Int) = new State(memory, result)
}

class State(memory: Memory, result: Int) {
  def >>= (f : (Memory => State)) : State = f(memory)
  def get = result
}

val add : (Int, Int) => Memory => State = (x, y) => memory => {
  val key = ('add, x, y)
  if (memory contains key) State.unit(memory, memory(key))
  else {
    val result = x + y
    val newMemory = memory + (key -> result)
    State.unit(newMemory, result)
  }
}

val mul : (Int, Int) => Memory => State = (x, y) => memory => {
  val key = ('mul, x, y)
  if (memory contains key) State.unit(memory, memory(key))
  else {
    val result = x * y
    val newMemory = memory + (key -> result)
    State.unit(newMemory, result)
  }
}

val state = State.unit(Memory, 0)
state >>= add(2,2) >>= mul(2,2)

Generyczna Monada Stanowa¶

type Key = (Symbol, Int, Int)
type Memory = Map[Key, Int]
def  Memory = Map[Key, Int]()

object State {
  def unit[A, B](memory: A, result: B) = new State(memory, result)
}

class State[A, B](memory: A, result: B) {
  def >>= (f : (A => State[A, B])) : State[A, B] = f(memory)
  def get = result
}

val add : (Int, Int) => Memory => State[Memory, Int] = (x, y) => memory => {
  val key = ('add, x, y)
  if (memory contains key) State.unit(memory, memory(key))
  else {
    val result = x + y
    val newMemory = memory + (key -> result)
    State.unit(newMemory, result)
  }
}

val mul : (Int, Int) => Memory => State[Memory, Int] = (x, y) => memory => {
  val key = ('mul, x, y)
  if (memory contains key) State.unit(memory, memory(key))
  else {
    val result = x * y
    val newMemory = memory + (key -> result)
    State.unit(newMemory, result)
  }
}

val state = State.unit(Memory, 0)
state >>= add(2,2) >>= mul(2,2)

Scalaz¶

Biblioteka Scalaz dodaje implementacje monadów, funkcje pomocnicze, itp.

https://github.com/scalaz/scalaz

Scalaz State Monad¶

Monada State[S, A] (klasa i companion object)

Konstrukcja:

State[S, A] : (S => (S, A)) => State[S, A]

Funkcje:

flatMap – operator bind – wykonuje operacje na monadzie i zwraca nową monadę

run, – typ S => (S, A) wykonuje operacje na monadzie i zwraca wynik + stan

eval, – typ S => A wykonuje operacje na monadzie i zwraca tylko wynik

exec, apply S => S wykonuje operacje na monadzie i zwraca tylko nowy stan

Przykład:

type Key = (Symbol, Int, Int)
type Memory = Map[Key, Int]
def Memory = Map[Key, Int]()

val add: (Int, Int) => State[Memory, Int] = (x, y) =>
  State[Memory, Int] { memory =>
    val key = ('add, x, y)
    if (memory contains key) (memory, memory(key))
    else {
      val result = x + y
      val newMemory = memory + (key -> result)
      (newMemory, result)
    }
  }

val mul: (Int, Int) => State[Memory, Int] = (x, y) =>
  State[Memory, Int] { memory =>
    val key = ('mul, x, y)
    if (memory contains key) (memory, memory(key))
    else {
      val result = x * y
      val newMemory = memory + (key -> result)
      (newMemory, result)
    }
  }

val state = add(1,1) flatMap { result1 => mul(2,2) } flatMap { result2 => mul(2,2) }
val state = add(1,1) flatMap { _ => mul(2,2) } flatMap { _ => mul(2,2) }

state run Memory
state eval Memory
state exec Memory

Idiomatyczne wywołanie:

val state = for {
  result1 <- add(1,1)
  result2 <- mul(2,2)
  result3 <- mul(2,2)
} yield result3

val state = for {
  _      <- add(1,1)
  _      <- mul(2,2)
  result <- mul(2,2)
} yield result

state run Memory
state eval Memory
state exec Memory

Monada IO¶

Monady pierwotnie służyły do rozwiązania problemu efektów ubocznych w Haskelu (pure + lazy).

Założenie: efekty uboczne to obliczenia które działają na specjalnym obiekcie: świecie rzeczywistym. Zamykamy je w minimalne osobne funkcje.

var RealWorld = List[String]()
def println(string : String) {
  RealWorld += string
}

val RealWorld = List[String]()
def println(realWorld: RealWorld, string : String) : RealWorld =
  RealWorld + string

def println(string : String) : RealWorld =
  RealWorld.unit(println(string))

Obudowanie efektów ubocznych w monady pozwala kontrolować efekty uboczne: wyizolować i opóźnić, wykonać w sposób który nie psuje referential transparency. Zaznacza, że efekty uboczne występują wewnątrz funkcji. Pozwala je zamodelować w sposób matematyczny (za pomocą teori kategorii).

def println(string : String) : RealWorld {
  RealWorld.unit(println(string))
}

Monady pozwalają na posługiwanie się grupami efektów ubocznych.

Przykład:

type Action[A] = () => A
class IO[+A](action: Action[A]){
  val performAction : Action[A] = action
  def >>= [B](f: A => IO[B]) : IO[B] = IO.unit { f(action()).performAction }
}
object IO {
  def unit[A](action : Action[A]) = new IO(action)
}

val monadicPrint = (string : String) => IO.unit { () => println(string) }
val monadicRead = () => IO.unit { () => readLine() }

(monadicPrint("Password") >>=
  { r => monadicRead() } >>=
  { r => monadicPrint("Password: " + r) }).performAction()

Scalaz IO Monad¶

Dostępna monada IO i funkcje:

scalaz.effect.IO
def getChar: IO[Char]
def putChar(c: Char): IO[Unit]
def putStr(s: String): IO[Unit]
def putStrLn(s: String): IO[Unit]
def readLn: IO[String]
def putOut[A](a: A): IO[Unit]

Użycie:

import scalaz.effect.IO.readLn
import scalaz.effect.IO.putStrLn

val program = putStrLn ("Password") flatMap {r => readLn} flatMap {r => putStrLn("Password: " + r)}
program.unsafePerformIO()

val program = for {
  _ <- putStrLn ("Password")
  r <- readLn
  p <- putStrLn("Password: " + r)
} yield p
program.unsafePerformIO()

Wykonanie opóźnione do unsafePerformIO (lazy).

Monady w Scali¶

List

Option

Listy¶

def multiply (x: Int) : List[Int] = List.tabulate(x){e => x}
List(1,2,3,4) flatMap multiply

Option/Maybe¶

val x = None
x flatMap {e => e * 2 + 1}

def inc(x: Option[Int], y: Option[Int]) =
    (x flatMap {e => Some(e + 1)}, y flatMap {e => Some(e + 1)})

def inc(x: Option[Int], y: Option[Int]) =
    (for { e <- x; r <- Some(e + 1) } yield r,
     for { e <- y; r <- Some(e + 1) } yield r)

inc(Some(1), None)

inc _ tupled (inc _ tupled (inc _ tupled (Some(1), None)))

List¶

val l = List(1, 2, 3, 0, 4, 1)

l flatMap {e => List.tabulate(e){case _  => e}}

Zadania¶

Za pomocą monady Option napisz funkjcę która oblicza miejsca zerowe równania kwadratowego.
Stosując monady, napisz program grający w kółko i krzyżyk.
Skonstruuj monadę Random, która generuje liczby pseudolosowe.
Skonstruuj monadę Error, która wykonuje dowolne obliczenia tylko wtedy, gdy poprzednie obliczenia się wykonały (à la try-catch).
Modyfikuj monadę State pokazaną jako przykład tak, zeby można było jej użyć za pomocą for comprehension.

Konrad Siek

Monady

Monady¶

Memoizacja¶

Rozwiazanie stanowe¶

Rozwiazanie bezstanowe¶

Obiekty w celu uporządkowania obliczeń¶

Monady¶

Teoria¶

Monada Stanowa¶

Generyczna Monada Stanowa¶

Scalaz¶

Scalaz State Monad¶

Monada IO¶

Scalaz IO Monad¶

Monady w Scali¶

Listy¶

Option/Maybe¶

List¶

Zadania¶

Materiały¶

Tekst¶

Wideo¶