How to define a type InfiniteFunction, which is a function and when called returns another InfiniteFunction
The type looks like:
() => () => () => ... // infinite
or recursive:
type InfiniteFunction = () => InfiniteFunction
And this doesn't work
scala> type InfiniteFunction = () => InfiniteFunction
<console>:11: error: illegal cyclic reference involving type InfiniteFunction
type InfiniteFunction = () => InfiniteFunction
Problem
I want to do cps transform on this function:
def travel(tree: TreeNode): Unit = {
if (tree != null) {
travel(tree.left)
println(tree.value)
travel(tree.right)
}
}
after 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()
}
}
Then I want to optimize the tail call by yielding them out, instead calling them:
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()
Here the type InfiniteFunction is needed, w/o the InfiniteFunction type, type conversion is needed:
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]