如何建模递归函数类型? [英] How to model recursive function types?

问题描述

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

I'm curious how this code would be modelled in Scala.

这是在golang中，并且是递归函数类型:

This is in golang, and it is a recursive function type:

type walkFn func(*int) walkFn

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

So the above is just a defintion of the type, a walk function is a function that takes a pointer to an integer, and returns a walk function.

一个示例实现是:

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

You can run code like this here: http://play.golang.org/p/621lCnySmy

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

Is it possible to write something like this pattern in Scala?

推荐答案

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

It's possible. You can use existential types to "cheat" scala's cyclic reference restriction:

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 一样:

Or like in @Travis Brown addition:

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)

这篇关于如何建模递归函数类型?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！