У меня есть проблема сделать рабочую версию задачи проекта Эйлера 31 с использованием признака состояния (вдохновленный scalaz)
Во-первых, у меня есть решение с изменяемым HashMap для мемоизации. Это работает, но я хотел бы использовать монаду State, чтобы понять ее и улучшить свои навыки.
Я использовал его с примером Фибоначчи, но когда я пытаюсь применить ту же технику к своему случаю, у меня возникает ошибка компилятора, которую я не понимаю.
Я использую эту реализацию для State :
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?
И, если можно, у меня есть необязательный вопрос: является ли мой способ запоминания с помощью State Monad хорошим выбором, или моя первая реализация с изменяемой картой все равно лучше?