如何使用 Scala 中的给定函数或属性定义无限惰性列表？

Question

我最近在 Rock the JVM 中看到了一门高级 Scala 课程，在一节课中，Daniel 打算使用属性（从 A 到布尔值的函数）创建一个集合，该集合的实现 可以找到在这里。

例如，他能够通过这样做创建一个“包含”所有自然数的集合：

val naturals = PBSet[Int](_ => true)

然后他可以通过执行 naturals.contains(input) 来验证输入是否包含在该集合内。

我的问题是，有没有办法使用惰性列表甚至更好的惰性向量或惰性映射来完成此任务？

例如，给定一个返回第 n 个斐波那契数的 fibonacci(n) 函数，包含该函数所有可能输出的惰性列表将如下所示：

val allFibonacciNumbers: LazyList[Long] = LazyList.generate(n => fibonacci(n))

我知道可以通过以下方式完成类似的操作这样做：

val allFibonacciNumbersV2: LazyList[Long] = LazyList.iterate(0L)(n => n + 1).map(n => fibonacci(n))

该实现的问题是迭代函数的起始值：它不会给出任何函数的所有可能输出，而只会给出之后的输出。

那么，如何使用基于 Porperty 的 Set 和 Lazy List 的组合来完成这样的任务呢？或者甚至更好，使用惰性向量或惰性映射？

我找不到类似的东西，我能找到的最接近的是基于属性的测试，但仅此而已。

感谢您的巨大帮助和阅读我的问题。祝你有美好的一天！

Answer 1

好吧，没有开箱即用的“LazyMap”，但是自行推出是相当简单的。

您的评论听起来好像您已经知道如何使用 LazyList 计算斐波那契，从那里，您只需要记住结果：

object FF { 
   val fm = mutable.Map.empty[Int, BigInt] 
   val fib: LazyList[BigInt] = BigInt(0) #:: BigInt(1) #:: 
       fib.zip(fib.tail).map(p => p._1 + p._2)
   def apply(n: Int) = fm.getOrElseUpdate(n, fib(n))
}

现在，像 FF(100) 这样的东西第一次是线性的，并且时间恒定在那之后。
如果先执行 FF(100)，然后执行 FF(99)，则第二次调用第一次仍然是线性的。从技术上讲，它也可以优化为恒定时间，因为 fib(99) 已经可用，但我认为不值得这么麻烦……以及额外的存储空间。