Программирование монады состояний в Scala - PullRequest
Новая
       33

Программирование монады состояний в Scala

2 голосов
/ 11 июля 2020

Теория того, как выглядит монада состояния, я позаимствовал из книги Филипа Вадлера «Монады функционального программирования»: 

type M a = State → (a, State) 
type State = Int
unit :: a → M a
unit a = λx. (a, x)
(*) :: M a → (a → M b) → M b
m * k = λx. 
         let (a, y) = m x in 
         let (b, z) = k a y in 
         (b, z)

Учитывая список L, я хочу, чтобы разные части моего кода получали этот список и обновляли этот список, добавляя новые элементы в его конец.

Я предполагаю, что приведенное выше будет изменено как: 

type M = State → (List[Data], State) 
type State = List[Data]
def unit(a: List[Data]) = (x: State) => (a,x)
def star(m: M, k: List[Data] => M): M = {
 (x: M) => 
   val (a,y) = m(x)
   val (b,z) = k(a)(y)
   (b,z)
} 
def get = ???
def update = ???

Как мне заполнить детали, например?

  1. Как мне создать экземпляр моей иерархии для работы с конкретным списком?
  2. Как реализовать get и обновить в соответствии с приведенным выше?

Наконец, как мне сделать это, используя синтаксис Scala с flatMap и unit?

1 Ответ

2 голосов
/ 11 июля 2020

Ваш M определен неверно. Он должен принимать a / A в качестве параметра, например: 

type M[A] = State => (A, State)

Вы также пропустили этот параметр типа в другом месте.

unit должен иметь подпись вроде это: 

def unit[A](a: A): M[A]

star должно иметь такую ​​подпись: 

def star[A, B](m: M[A], k: A => M[B]): M[B]

Надеюсь, это сделает функции более понятными.

Ваша реализация unit был почти таким же: 

def unit[A](a: A): M[A] = x => (a, x)

Однако в star параметр вашей лямбды (x) имеет тип State, а не M, потому что M[B] в основном State => (A, State). В остальном вы правильно поняли: 

def star[A, B](m: M[A])(k: A => M[B]): M[B] = 
  (x: State) => {
    val (a, y) = m(x)
    val (b, z) = k(a)(y)
    (b, z)
  }

Редактировать: Согласно @Luis Miguel Mejia Suarez:

Вероятно, было бы проще реализовать, если бы вы сделали ваше состояние классом и определите внутри него flatMap. И вы можете определить единицу измерения в сопутствующем объекте.

Он предложил final class State[S, A](val run: S => (A, S)), что также позволит вам использовать инфиксные функции, такие как >>=.

Другой способ сделать это означало бы определить State как псевдоним типа для функции S => (A, S) и расширить его с помощью неявного класса. 

type State[S, A] = S => (A, S)
object State {
  //This is basically "return"
  def unit[S, A](a: A): State[S, A] = s => (a, s)
}

implicit class StateOps[S, A](private runState: S => (A, S)) {
  //You can rename this to ">>=" or "flatMap"
  def *[B](k: A => State[S, B]): State[S, B] = s => {
    val (a, s2) = runState(s)
    k(a)(s2)
  }
}

Если ваше определение get равно

установите значение результата в состояние и оставьте состояние неизменным (заимствовано из Haskell Wiki ), тогда вы можете реализовать это так: 

def get[S]: State[S, S] = s => (s, s)

Если вы означает, что вы хотите извлечь состояние (в данном случае List[Data]), вы можете использовать execState (определите его в StateOps): 

def execState(s: S): S = runState(s)._2

Вот ужасный пример того, как вы можете добавлять элементы в List. 

def addToList(n: Int)(list: List[Int]): ((), List[Int]) = ((), n :: list)

def fillList(n: Int): State[List[Int], ()] =
  n match {
    case 0 => s => ((), s)
    case n => fillList(n - 1) * (_ => addToList(n))
  }

println(fillList(10)(List.empty)) дает нам это (второй элемент может быть извлечен с помощью execState): 

((),List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))
...