How to model recursive function types?

Question

I'm curious how this code will be modeled in Scala.

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

type walkFn func(*int) walkFn 

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

Implementation Example:

 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 the code as follows: http://play.golang.org/p/621lCnySmy

Can I write something like this template in Scala?

Answer 1

It is possible. You can use existential types to "scam" scala to cyclically restrict links:

 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 the @Travis Brown add-on:

 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) 

Answer 2

One of the sad facts of Scala is that recursive type aliases are not supported. Performing the following in REPL results in the following:

 scala> type WalkFn = Function[Int, WalkFn] <console>:7: error: illegal cyclic reference involving type WalkFn type WalkFn = Function[Int, WalkFn] ^ 

Another remark is that Scala does not allow changing values ​​by reference (as a rule, frowning, no, completely hates the functional programming paradigm).

However, do not be embarrassed! There are other options. Traits can be self-referential, and functions are just classes in Scala. In this way, we can model a common recursive WalkFn with traits. In addition, we can use immutable values, and our function returns the next progress, and does not mutate the parameter by reference.

Since the following contains circular references (WalkForward → WalkBackward, WalkBackward → WalkForward, etc.), you need to enter :paste in Scala REPL before starting the next example (so that the Scala Compiler will compile all 3 Walk{Forward,Backward,Equal} implementations in one step.

At first:

 $ scala Welcome to Scala version 2.11.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_05). Type in expressions to have them evaluated. Type :help for more information. scala> :paste // Entering paste mode (ctrl-D to finish) 

Now paste the code:

 import scala.util.Random object Helpers { def pickRandom[A](items: A*) = items(Random.nextInt(items.length)) } trait WalkFn extends (Int => (Int, WalkFn)) {} object WalkForward extends WalkFn { def apply(i: Int) = ( i + Random.nextInt(6), Helpers.pickRandom(WalkEqual, WalkBackward) ) } object WalkEqual extends WalkFn { def apply(i: Int) = ( i + (Random.nextInt(7) - 3), Helpers.pickRandom(WalkForward, WalkBackward) ) } object WalkBackward extends WalkFn { def apply(i: Int) = ( Random.nextInt(6) - 3, Helpers.pickRandom(WalkEqual, WalkForward) ) } def doWalk(count: Int, walkFn: WalkFn = WalkEqual, progress: Int = 0): Unit = if (count > 0) { val (nextProgress, nextStep) = walkFn(progress) println(nextProgress) doWalk(count - 1, nextStep, nextProgress) } doWalk(20) 

Then, as instructed, press ctrl-D .

Enjoy a functional drunk step!

Answer 3

I would say that it is more idiomatic in Scala to separate the iterative part. So, for example, we can define a finite state machine:

 import scala.util.Random sealed trait Walker { def i: Int def advance: Walker } case class WalkEqual(i: Int) extends Walker { def advance = { val next = i + Random.nextInt(7) - 3 if (Random.nextBoolean) WalkForward(next) else WalkBackward(next) } } case class WalkForward(i: Int) extends Walker { def advance = { val next = i + Random.nextInt(6) if (Random.nextBoolean) WalkEqual(next) else WalkBackward(next) } } case class WalkBackward(i: Int) extends Walker { def advance = { val next = i - Random.nextInt(6) if (Random.nextBoolean) WalkEqual(next) else WalkForward(next) } } 

And then we can write the following:

 val locations = Stream.iterate[Walker](WalkEqual(0))(_.advance).map(_.i) 

This is an endless stream of places that our walker visits. We can use it as follows:

 scala> locations.take(10).foreach(println) 0 0 -1 2 1 0 -5 -5 -10 -6 

We could also take their finite number and collect them in a specific collection (for example, in the form of a list) by writing locations.take(100).toList .