scala - 如何建模递归函数类型？

Question

我很好奇这段代码将如何在 Scala 中建模。

这是在 golang 中，它是一个递归函数类型:

type walkFn func(*int) walkFn

所以上面只是对类型的定义，walk 函数是一个函数，它接受一个指向整数的指针，并返回一个walk 函数。

一个示例实现是:

func walkForward(i *int) walkFn {
    *i += rand.Intn(6)
    return pickRandom(walkEqual, walkBackward)
}

func walkBackward(i *int) walkFn {
    *i += -rand.Intn(6)
    return pickRandom(walkEqual, walkForward)
}

你可以在这里运行这样的代码: http://play.golang.org/p/621lCnySmy

是否可以在 Scala 中编写类似这种模式的内容？

Answer 1

这是可能的。您可以使用存在类型来“欺骗”scala 的循环引用限制:

type A[T <: A[_]] = Int => (Int, T)

lazy val walkEqual: A[A[_]] = (i: Int) => 
  (i + Random.nextInt(7) - 3, if (Random.nextBoolean) walkForward else walkBackward)

lazy val walkForward: A[A[_]] = (i: Int) =>  
  (i + Random.nextInt(6), if (Random.nextBoolean) walkEqual else walkBackward)

lazy val walkBackward: A[A[_]] = (i: Int) => 
  (i - Random.nextInt(6), if (Random.nextBoolean) walkEqual else walkForward)

def doWalk(count: Int, walkFn: A[_] = walkEqual, progress: Int = 0): Unit =
  if (count > 0) {
    val (nextProgress, nextStep: A[_] @unchecked) = walkFn(progress)
    println(nextProgress)
    doWalk(count - 1, nextStep, nextProgress)
  }

结果:

scala> doWalk(10)
2
5
2
0
-3
-5
-4
-8
-8
-11

或者像在@Travis Brown 中添加:

val locations = Stream.iterate[(Int,A[_] @unchecked)](walkEqual(0)) {
   case (x: Int, f: A[_]) => f(x)
}.map(_._1)

scala> locations.take(20).toList
res151: List[Int] = List(-1, 1, 1, 4, 1, -2, 0, 1, 0, 1, 4, -1, -2, -4, -2, -1, 2, 1, -1, -2)