相关疑难解决方法(0)

以下代码来自Pathikrit的动态编程存储库.我的美丽和独特使我感到困惑.

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 => …

我正在寻找关于项目欧拉的问题三十一,请问,有多少不同的方法可以使用任意数量的1p,2p,5p,10p,20p,50p,£1(100p)和£的硬币赚2英镑2(200p).

有递归解决方案,例如Scala中的这个解决方案(由Pavel Fatin提供)

def f(ms: List[Int], n: Int): Int = ms match {
  case h :: t =>
    if (h > n) 0 else if (n == h) 1 else f(ms, n - h) + f(t, n)
  case _ => 0
} 
val r = f(List(1, 2, 5, 10, 20, 50, 100, 200), 200)

虽然运行速度足够快,但它的效率相对较低,调用f函数大约560万次.

我看到了其他用Java编写的动态编程解决方案(来自葡萄牙的wizeman)

final static int TOTAL = 200;

public static void main(String[] args) {
    int[] coins = {1, 2, 5, 10, 20, …

此页面描述了Map的getOrElseUpdate使用方法:

object WithCache{
  val cacheFun1 = collection.mutable.Map[Int, Int]()
  def fun1(i:Int) = i*i
  def catchedFun1(i:Int) = cacheFun1.getOrElseUpdate(i, fun1(i))
}

因此,您可以使用catchedFun1哪个将检查是否cacheFun1包含与之关联的键和返回值.否则,它将调用fun1,然后缓存fun1结果cacheFun1,然后返回fun1结果.

我可以看到一个潜在的危险 - cacheFun1可能变得很大.所以cacheFun1必须通过垃圾收集器以某种方式清理？

PS怎么样scala.collection.mutable.WeakHashMap and java.lang.ref.* ？

如何 在Scala中返回一个函数 副作用词法闭包 ¹？

例如,我在Go中查看此代码示例:

...    
// fib returns a function that returns
// successive Fibonacci numbers.
func fib() func() int {
    a, b := 0, 1
    return func() int {
        a, b = b, a+b
        return b
    }
}
...
println(f(), f(), f(), f(), f())

打印1 2 3 5 8

我无法弄清楚如何在Scala中编写相同的内容.

^{1.在Apocalisp评论后更正}

我想在scala中编写一个memoize函数,无论函数对象是什么,它都可以应用于任何函数对象.我希望以一种允许我使用memoize的单个实现的方式这样做.我对语法很灵活,但理想情况下,memoize出现在非常接近函数声明的地方,而不是函数之后.我还想避免首先声明原始函数,然后再为memoized版本声明第二个声明.

所以一些理想的语法可能是这样的:

def slowFunction(<some args left intentionally vague>) = memoize {
  // the original implementation of slow function
}

甚至这是可以接受的:

def slowFUnction = memoize { <some args left intentionally vague> => {
  // the original implementation of slow function
}}

我已经看到了这样做的方法,其中必须为每个arity函数重新定义memoize,但我想避免这种方法.原因是我需要实现几十个类似于memoize的函数(即其他装饰器),要求每个arity函数都要复制每个函数太多了.

一种做memoize的方法确实需要你重复memoize声明(所以它没有用)是什么类型用于在Scala中存储内存中的可变数据表？.

我想知道是否有一些通用方法来转换"正常"递归foo(...) + foo(...)作为最后一次调用尾递归.

例如(scala):

def pascal(c: Int, r: Int): Int = {
 if (c == 0 || c == r) 1
 else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

函数式语言的一般解决方案,用于将递归函数转换为尾部调用等效函数:

一种简单的方法是将非尾递归函数包装在Trampolinemonad中.

def pascalM(c: Int, r: Int): Trampoline[Int] = {
 if (c == 0 || c == r) Trampoline.done(1)
 else for {
     a <- Trampoline.suspend(pascal(c - 1, r - 1))
     b <- Trampoline.suspend(pascal(c, r - 1))
   } yield a + b
} …

我正在创建一个简单的缓存特征(轻松缓存我的函数):

trait Cache[A,B] {
  def _calc(v:A):B
  private var cache = Map[A,B]()
  def calc(v:A):B = {
    cache.get(v) match {
      case Some(x) => x
      case None => 
        val x = _calc(v)
        cache += (v -> x)
        x
    }
  }
}

用法:

object Sol extends Cache[Int,Int] {
  def _calc(v:Int):Int = { /* do something here */ }
}
Sol.calc(5)

它工作正常,但问题出现在我需要缓存具有更多参数的函数时 - 所以我需要开发特征Cache2,Cache3,来自第一个特征的所有复制粘贴代码.

可能的解决方法是将具有多个参数的函数转换为接受元组的函数,但这似乎不正确.

有没有办法更普遍地做到并避免干扰原则违规？

我可能想要使用昂贵的方法并根据副作用返回结果.例如,取决于一天/一周的时间和量子时间动力学的蒙特卡罗模拟.因为它很贵而我可能不需要它,我会使用Scalaslazy val

lazy val maybeUnusedValue = getDayOfWeek

现在我的程序仍在运行12个小时.我想重做计算,因为我的日子可能在此期间发生了变化.

是否有一种简单的方法可以强制Scala返回maybeUnusedValue到未初始化的状态,因此强制重新计算其下一次使用？

我正在尝试实现一个memoized Fibonacci数字函数,我遇到了一个我无法解决的编译错误.以下代码是我到目前为止的代码.

var fibs = Map.empty[Int, Int]
fibs += 0 -> 1
fibs += 1 -> 1
fibs += 2 -> 2
val fib = (n: Int) => {
  if (fibs.contains(n)) return fibs.apply(n)
  else{
    // Error here
    val result = fib(n - 1) + fib(n - 2)
    fibs+= n -> result
    return result
  }
}
println(fib(100))

错误是:

递归fib需求类型

我已经尝试在各个地方为闭包输入一个返回类型,但我似乎无法让它工作.

声明闭包会val fib = (n: Int): Int => {产生不同的编译错误.

你能帮我解决这个编译错误吗？