How do I write recursive anonymous functions?

问题:

In my continued effort to learn scala, I'm working through 'Scala by example' by Odersky and on the chapter on first class functions, the section on anonymous function avoids a situation of recursive anonymous function. I have a solution that seems to work. I'm curious if there is a better answer out there.

From the pdf: Code to showcase higher order functions

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f, a + 1, b)

def id(x: Int): Int = x
def square(x: Int): Int = x * x
def powerOfTwo(x: Int): Int = if (x == 0) 1 else 2 * powerOfTwo(x-1)

def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumSquares(a: Int, b: Int): Int = sum(square, a, b)
def sumPowersOfTwo(a: Int, b: Int): Int = sum(powerOfTwo, a, b)

scala> sumPowersOfTwo(2,3)
res0: Int = 12

from the pdf: Code to showcase anonymous functions

def sum(f: Int => Int, a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f, a + 1, b)

def sumInts(a: Int, b: Int): Int = sum((x: Int) => x, a, b)
def sumSquares(a: Int, b: Int): Int = sum((x: Int) => x * x, a, b)
// no sumPowersOfTwo

My code:

def sumPowersOfTwo(a: Int, b: Int): Int = sum((x: Int) => {
   def f(y:Int):Int = if (y==0) 1 else 2 * f(y-1); f(x) }, a, b)

scala> sumPowersOfTwo(2,3)
res0: Int = 12

回答1:

For what it's worth... (the title and "real question" don't quite agree)

Recursive anonymous function-objects can be created through the "long hand" extending of FunctionN and then using this(...) inside apply.

(new Function1[Int,Unit] {
  def apply(x: Int) {
    println("" + x)
    if (x > 1) this(x - 1)
  }
})(10)

However, the amount of icky-ness this generally introduces makes the approach generally less than ideal. Best just use a "name" and have some more descriptive, modular code -- not that the following is a very good argument for such ;-)

val printingCounter: (Int) => Unit = (x: Int) => {
    println("" + x)
    if (x > 1) printingCounter(x - 1)
}
printingCounter(10)

Happy coding.

回答2:

You can generalize this indirect recursion to:

case class Rec[I, O](fn : (I => O, I) => O) extends (I => O) {
  def apply(v : I) = fn(this, v)
}

Now sum can be written using indirect recursion as:

val sum = Rec[Int, Int]((f, v) => if (v == 0) 0 else v + f(v - 1))

The same solution can be used to implement memoization for example.