scala - 如何定义类型 : infinite function?

Question

如何定义类型 InfiniteFunction ，这是一个函数，调用时返回另一个 InfiniteFunction
类型看起来像:

() => () => () => ... // infinite

或递归:

type InfiniteFunction = () => InfiniteFunction

这不起作用

scala> type InfiniteFunction = () => InfiniteFunction
<console>:11: error: illegal cyclic reference involving type InfiniteFunction
       type InfiniteFunction = () => InfiniteFunction

问题

我想对这个函数做 cps 变换:

def travel(tree: TreeNode): Unit = {
  if (tree != null) {
    travel(tree.left)
    println(tree.value)
    travel(tree.right)
  }
}

cps后:

def r[T](f: => T): () => T = () => f
def travel(tree: TreeNode, cb: () => AnyRef): Unit = {
  if (tree != null) {
    travel(tree.left, r{
      println(tree.value)
      travel(tree.right, cb)
    })
  } else {
    cb()
  }
}

然后我想通过输出它们来优化尾调用，而不是调用它们:

def r[T](f: => T): () => T = () => f
def travel(tree: TreeNode, cb: () => InfiniteFunction): InfiniteFunction = {
  if (tree != null) {
    r(travel(tree.left, r{
      println(tree.value)
      r(travel(tree.right, cb))
    }))
  } else {
    r(cb())
  }
}

// demonstration how to use travel
var f: InfiniteFunction = r(
  travel(tree, r(throw new RuntimeException("it is over")))
)
// this will end by the exception "it is over"
while (true) f = f()

这里的类型 InfiniteFunction需要，没有 InfiniteFunction类型，需要类型转换:

def r[T](f: => T): () => T = () => f
def travel(tree: TreeNode, cb: () => AnyRef): () => AnyRef = {
  if (tree != null) {
    r(travel(tree.left, r {
      println(tree.value)
      r(travel(tree.right, cb))
    }))
  } else {
    r(cb())
  }
}

var f: () => AnyRef = r(
  travel(tree, r(throw new RuntimeException("it is over")))
)
while (true) f = f().asInstanceOf[() => AnyRef]

Answer 1

使用 trait 而不是类型别名来解决循环引用的问题:

trait Inf extends (Unit => Inf)

还有 Unit是 () 的类型