Wie modelliert man rekursive Funktionstypen?

Question

Ich bin gespannt, wie dieser Code in Scala modelliert werden würde.

Das in golang ist, und es ist eine rekursive Funktion Typ:

type walkFn func(*int) walkFn 

So ist die oben nur eine Defintion des Typs, ist ein Spaziergang Funktion eine Funktion, die einen Zeiger auf eine ganze Zahl nimmt, und Gibt eine Walk-Funktion zurück.

Eine Implementierung Beispiel wäre:

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

Sie können diesen Code wie hier ausgeführt: http://play.golang.org/p/621lCnySmy

Ist es möglich, so etwas wie dieses Muster in Scala zu schreiben?

Answer 1

Eine der traurigen Fakten von Scala ist, dass Aliase vom rekursiven Typ nicht unterstützt werden. die folgenden Aktionen ausführen in der REPL ergibt folgendes:

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

Ein weiterer Hinweis ist, dass Scala ermöglicht es Ihnen nicht Werte, die durch Bezugnahme zu ändern (in der Regel verpönt, ja verabscheut ganz in der funktionalen Programmierung-Paradigma).

Allerdings nicht bestürzt! Es gibt andere Möglichkeiten. Eigenschaften können selbstreferentiell sein und Funktionen sind einfach Klassen in Scala. So können wir das generische rekursive WalkFn mit Merkmalen modellieren. Außerdem können wir unveränderliche Werte annehmen und unsere Funktion den nächsten Fortschritt zurückgeben, anstatt einen Parameter durch Referenz zu verändern.

Da der folgenden enthält zyklische Referenzen (WalkForward -> WalkBackward, WalkBackward -> WalkForward, etc.), müssen Sie :paste in das scala REPL vor dem Ausführen des folgenden Beispiels (so der Scala-Compiler alle kompiliert eingeben 3 Walk{Forward,Backward,Equal} Implementierungen in einem Schritt

Erstens:.

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

Nun fügen Sie den 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) 

Dann, per Anweisungen, drücken Sie ctrl-D.

Genießen Sie die funktionale betrunkene Staffelung!

Answer 2

Ich würde sagen, dass es in Scala idiomatischer ist, den Iterationsteil herauszufiltern. So zum Beispiel können wir eine Zustandsmaschine definieren:

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

Und dann können wir folgende schreiben:

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

Dies ist ein unendlicher Strom von Orten, die unsere Wanderer besucht. Wir können es wie folgt verwenden:

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

Wir könnten auch eine endliche Anzahl von ihnen nehmen und sammeln sie in einer konkret realisierten Sammlung (wie eine Liste) von locations.take(100).toList zu schreiben.

Answer 3

Es ist möglich.Sie können existentielle Typen verwenden, um "zu betrügen" Scalas zyklischen Referenz Einschränkung:

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

Ergebnis:

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

Oder wie in @Travis Brown Zusatz:

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)