How to model recursive function types?

Question

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

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

type walkFn func(*int) walkFn

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.

An example implementation would be:

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)
}

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

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

Answer 1

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)
  }

Result:

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

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)