在 Scala 中编写状态 monad
Programming a state monad in Scala
我从 Philip Wadler 的 Monads for Functional Programming 借来的关于状态 monad 的理论:
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)
我想使用状态 monad 的方式如下:
Given a list L I want different parts of my code to get this list and update this list by adding new elements at its end.
我猜上面会被修改为:
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 = ???
如何填写详细信息,即?
- 如何实例化我的层次结构以处理具体列表?
- 如何实现上面的get和update?
最后,我如何使用 Scala 的 flatMap 和 unit 语法来做到这一点?
您的 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
中,你的lambda(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 的说法:
It would probably be easier to implement if you make your State a class and define flatMap inside it. And you can define unit in the companion object.
他建议 final class State[S, A](val run: S => (A, S))
,这也允许您使用像 >>=
.
这样的中缀函数
另一种方法是将 State
定义为函数 S => (A, S)
的类型别名,并使用隐式 class.
对其进行扩展
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
的定义是
set the result value to the state and leave the state unchanged
(borrowed from Haskell Wiki), then you can implement it like this:
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))
我从 Philip Wadler 的 Monads for Functional Programming 借来的关于状态 monad 的理论:
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)
我想使用状态 monad 的方式如下:
Given a list L I want different parts of my code to get this list and update this list by adding new elements at its end.
我猜上面会被修改为:
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 = ???
如何填写详细信息,即?
- 如何实例化我的层次结构以处理具体列表?
- 如何实现上面的get和update?
最后,我如何使用 Scala 的 flatMap 和 unit 语法来做到这一点?
您的 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
中,你的lambda(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 的说法:
It would probably be easier to implement if you make your State a class and define flatMap inside it. And you can define unit in the companion object.
他建议 final class State[S, A](val run: S => (A, S))
,这也允许您使用像 >>=
.
另一种方法是将 State
定义为函数 S => (A, S)
的类型别名,并使用隐式 class.
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
的定义是
set the result value to the state and leave the state unchanged (borrowed from Haskell Wiki), then you can implement it like this:
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))