使用 State monad 进行记忆时的编译器错误消息

Question

我在使用 State trait（灵感来自 scalaz）制作 Euler 项目问题 31 的工作版本时遇到问题

首先，我有一个带有用于记忆的可变 HashMap 的解决方案。它有效，但我想使用 State monad 来理解它并提高我的技能。

我在斐波那契示例中使用了它，但是当我尝试将相同的技术应用于我的案例时，我遇到了一个我不理解的编译器错误。

我将此实现用于状态：

trait State[S, A] {
  val run: S => (S, A)
  def apply(s: S): (S, A) = run(s)
  def eval(s: S): A = run(s)._2

  def map[B](f: A => B): State[S, B] =
    State { s: S =>
      val (s1, a) = run(s)
      (s1, f(a))
    }

  def flatMap[B](f: A => State[S, B]): State[S, B] =
    State { s: S =>
      val (s1, a) = run(s)
      f(a)(s1)
    }

}

object State {
  def apply[S, A](f: S => (S, A)): State[S, A] = new State[S, A] {
    final val run = f
  }

  def init[S, A](a: A) = State { s: S => (s, a) }
  def update[S, A](f: S => S): State[S, Unit] = State { s: S => (f(s), ()) }
  def gets[S, A](f: S => A): State[S, A] = State { s: S => (s, f(s)) }

}

我在这里尝试使用它：

val coins = List(1, 2, 5, 10, 20, 50, 100, 200)
type MemoKey = (List[Int], Int)
type MemoType = Map[MemoKey, Int]

def ways(listCoins: List[Int], amount: Int): Int = {

  def ways_impl(coins: List[Int], sum: Int): State[MemoType, Int] = (coins, sum) match {
    case (Nil, 0) => State.init(1)
    case (Nil, _) => State.init(0)
    case (c :: cs, _) =>
      for {
        memoed <- State.gets { m: MemoType => m.get((coins, sum)) }
        res <- memoed match {
          case Some(way) => State.init[MemoType, Int](way)
          case None =>
            (for {
              i <- 0 to sum / c
              r <- ways_impl(cs, sum - i * c)
              _ <- State.update { m: MemoType => m + ((coins, sum) -> r) }
            } yield r).sum
        }
      } yield res
  }
  ways_impl(listCoins, amount) eval (Map())

我在这一行有一个编译器错误：

              r <- ways_impl(cs, sum - i * c)

编译器说：

type mismatch; found : State[MemoType,Int] (which expands to) State[scala.collection.immutable.Map[(List[Int], Int),Int],Int] required: scala.collection.GenTraversableOnce[?]

有关信息，这是我的第一个带有可变映射的版本：

import scala.collection.mutable._
val memo = HashMap[(List[Int], Int), Int]()

val coins = List(1, 2, 5, 10, 20, 50, 100, 200)

def memoWays(coins: List[Int], sum: Int): Int = {
  memo.getOrElse((coins, sum), {
    val y = ways(coins, sum)
    memo += ((coins, sum) -> y)
    y
  })
}

// brute force method with memoization
def ways(coins: List[Int], sum: Int): Int = (coins, sum) match {
  case (Nil, 0) => 1
  case (Nil, _) => 0
  case (c :: cs, n) =>
    (for {
      i <- 0 to n / c
      r = memoWays(cs, n - i * c)
    } yield r).sum
}

println(s"result=${Mesure(ways(coins, 200))}")

这个错误是什么意思？为什么编译器需要 GenTraversableOnce 而不是 State ？我对 State monad 有什么不明白的地方？

而且，如果可以的话，我有一个可选问题：我使用 State Monad 进行记忆的方式是一个不错的选择，还是我的第一个可变映射实现更好？

Answer 1

问题是您的 for 理解试图 flatMap 两个不相关的类型：Range 和 State。您将不得不进行重构，虽然超出了我的脑海，但我不清楚您将如何能够以简单的方式利用 State。我可能会使用不可变的 Map 作为备忘录，使用 List 来表示要尝试的未来迭代，并使用简单的递归来迭代。

使用 State monad 进行记忆时的编译器错误消息

compiler error message when using State monad for memoization

scala

state-monad