How to define a type: infinite function?

Viewed 99

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]
1 Answers

Use a trait instead of a type alias to resolve the problem with the cyclic reference:

trait Inf extends (Unit => Inf)

Also Unit is the type of ()

Related