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?
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)
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)
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)
Monada to struktura rozbijająca wykonanie obliczeń na etapy (akcje).
- Wzorzec programowy
- Programowalny średnik
- Endofunktor (teoria kategorii)
- Horror + magia (HP Lovecraft?)
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
I return(x) >>= f ≡ f(x)
II monad >>= return ≡ monad
III monad >>= f >>= g ≡ monad >>= (x) => f(x) >>= g
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)
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)
Biblioteka Scalaz dodaje implementacje monadów, funkcje pomocnicze, itp.
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
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).
Monady pozwalają na posługiwanie się grupami efektów ubocznych.
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()
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).
- List
- Option
def multiply (x: Int) : List[Int] = List.tabulate(x){e => x} List(1,2,3,4) flatMap multiply
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)))
val l = List(1, 2, 3, 0, 4, 1) l flatMap {e => List.tabulate(e){case _ => e}}
Space | Forward |
---|---|
Right, Down, Page Down | Next slide |
Left, Up, Page Up | Previous slide |
P | Open presenter console |
H | Toggle this help |