Следующий код из репозитория Pathikrit Dynamic Programming. Меня поражает как его красота, так и своеобразие.
def subsetSum(s: List[Int], t: Int) = {
type DP = Memo[(List[Int], Int), (Int, Int), Seq[Seq[Int]]]
implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)
lazy val f: DP = Memo {
case (Nil, 0) => Seq(Nil)
case (Nil, _) => Nil
case (a :: as, x) => (f(as, x - a) map {_ :+ a}) ++ f(as, x)
}
f(s, t)
}
Тип Memo
реализуется в другом файле:
case class Memo[I <% K, K, O](f: I => O) extends (I => O) {
import collection.mutable.{Map => Dict}
val cache = Dict.empty[K, O]
override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}
Мои вопросы:
-
Почему
type K
объявлен как(Int, Int)
в subsetSum? -
Что означает
int
in(Int, Int)
соответственно?
3. Как (List[Int], Int)
неявно конвертировать в (Int, Int)
?
Я не вижу implicit def foo(x:(List[Int],Int)) = (x._1.toInt,x._2)
. (даже в файле Implicits.scala
, который он импортирует.
* Редактировать: Ну, я пропустил это:
implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)
Мне очень нравится библиотека Pathikrit scalgos. В нем много жемчуга Scala. Пожалуйста, помогите мне в этом, чтобы я мог оценить остроумие Патикрита. Спасибо. (