如何在递归上下文中进行惰性解释？

Question

下面是FPIS

object test2 { 

    //a naive IO monad 
    sealed trait IO[A] { self => 
    def run: A 
    def map[B](f: A => B): IO[B] = new IO[B] { def run = f(self.run) } 
    def flatMap[B](f: A => IO[B]): IO[B] = { 
     println("calling IO.flatMap") 
     new IO[B] { 
     def run = { 
      println("calling run from flatMap result") 
      f(self.run).run 
     } 
    } 
    } 
    } 

    object IO { 
    def unit[A](a: => A): IO[A] = new IO[A] { def run = a } 
    def apply[A](a: => A): IO[A] = unit(a) // syntax for IO { .. } 
    } 

    //composer in question 
    def forever[A,B](a: IO[A]): IO[B] = { 
    lazy val t: IO[B] = a flatMap (_ => t) 
    t 
    } 

    def PrintLine(msg: String) = IO { println(msg) } 

    def say = forever(PrintLine("Still Going..")).run 
} 

test2.say代码将堆栈溢出之前打印数千“仍在继续”。但我不知道到底发生了什么。

输出看起来是这样的：
斯卡拉> test2.say
调用IO.flatMap //只有一次
从flatMap结果调用运行
仍在继续..
从flatMap结果
调用运行 还在..

... //重复直到堆栈溢出

当乐趣ction 永远返回，是完全计算（缓存）的懒惰值？ 而且，flatMap方法似乎只被调用一次（我添加了打印语句），这反映了永远的递归定义。为什么？

===========
我觉得有趣的另一件事是永远的B型可以是任何东西。实际上斯卡拉可以运行它不透明。

我手动尝试永远[单位，双]，永远[单位，字符串]等，这一切工作。这感觉很聪明。

Answer 1

我想知道当函数永远返回，是完全计算（缓存）的懒惰值？

是

如果是这样，那么为什么需要懒惰的关键字？

你的情况没用。它可以像情况是有用的：

def repeat(n: Int): Seq[Int] { 
    lazy val expensive = "some expensive computation" 
    Seq.fill(n)(expensive) 
    // when n == 0, the 'expensive' computation will be skipped 
    // when n > 1, the 'expensive' computation will only be computed once 
} 

其他的事情，我不明白的是，flatMap方法似乎 被调用一次哪些计数器的 递归定义（我添加打印语句）永远。为什么？

无法发表评论，直到你可以提供一个最小的，完整的，并且可验证的例子，像@Yuval Itzchakov说

更新19/04/2017

好吧，我需要纠正自己:-)在你的情况下，lazy val是必需的，因为递归引用本身。

来解释你的观察，让我们尝试了forever(a).run呼叫扩大：

1. forever(a)扩展到

2. { lazy val t = a flatMap(_ => t) }扩展到

3. { lazy val t = new IO[B] { def run() = { ... t.run } }

因为t是懒惰的，所以2和3中的flatMap和new IO[B]只被调用一次，然后'缓存'以供重用。

在3上调用run()时，您开始在t.run上进行递归，从而得到您观察到的结果。

不完全确定自己的需求，但forever非堆栈吹版本可以等来实现：

def forever[A, B](a: IO[A]): IO[B] = { 
    new IO[B] { 
     @tailrec 
     override def run: B = { 
     a.run 
     run 
     } 
    } 
    } 

Answer 2

什么forever方法确实是，顾名思义，使单子实例a运行永远。更确切地说，它给了我们无限的一元操作链。

其值t递归定义为：

t = a flatMap (_ => t) 

它将扩展为

t = a flatMap (_ => a flatMap (_ => t)) 

它将扩展为

t = a flatMap (_ => a flatMap (_ => a flatMap (_ => t))) 

等。

Lazy使我们能够定义像这样的东西。如果我们删除了懒惰的部分，我们会得到一个“前向引用”错误（如果递归值包含在某个方法中），或者它将被初始化为一个默认值，而不是递归地使用（如果包含在一个类中，使其成为一个带有幕后获取者和二传手的职业场）。

演示：

val rec: Int = 1 + rec 
println(rec) // prints 1, "rec" in the body is initialized to default value 0 


def foo() = { 
    val rec: Int = 1 + rec // ERROR: forward reference extends over definition of value rec 
    println(rec) 
} 

然而，仅此是为什么整个堆栈溢出的事情发生的原因。有另一个递归部分，而这一个实际上是负责堆栈溢出。这是隐藏在这里：

def run = { 
    println("calling run from flatMap result") 
    f(self.run).run 
} 

方法run自称是（看到self.run）。当我们像这样定义它时，我们不会当场评估self.run，因为f尚未被调用;我们只是说它会在调用run（）后被调用。

但是，当我们在forever中创建值t时，我们正在创建一个flatmaps到自身的IO monad（它提供给flatMap的函数是“评估自己”）。这将触发run，因此会触发f的评估和调用。我们从来没有真正离开flatMap上下文（因此只有一个打印语句是为flatMap部分），因为一旦我们尝试flatMap，run开始评估函数f，该函数返回我们调用run的IO，调用函数f返回IO上，我们称之为运行其调用函数f返回上我们称之为运行IO ...

Answer 3

new IO[B] { 
    def run = { 
     println("calling run from flatMap result") 
     f(self.run).run 
    } 
} 

我明白了为什么现在四溢在运行方法时发生：在外运行调用运行高清实际上指向def run本身。

调用堆栈看起来像这样：

 
f(self.run).run 
     |-----|--- println 
      |--- f(self.run).run 
         |-----|------println 
           |------f(self.run).run 
              |------ (repeating) 

F（self.run）总是指向同一评估/高速缓存懒惰VAL吨对象
因为F：_ =>吨简单地返回t IS UNIQUE新创建的 IO [B]托管我们正在调用的run方法，并将立即递归调用。

这就是我们在堆栈溢出之前可以看到打印语句的方式。

但是仍然不清楚在这种情况下，懒惰的val如何做到正确。