Ist die Anwendungsfunktion rekursiv?

Question

folgende Merkmal Definition vor:

sealed trait Stream[+A] 
case object Empty extends Stream[Nothing] 
case class Cons[+A](h:() => A, t:() => Stream[A]) extends Stream[A] 

object Stream { 

    def cons[A](hd: => A, t1: => Stream[A]): Stream[A] = { 
    lazy val head = hd 
    lazy val tail = t1 
    Cons(() => head,() => tail) 
    } 

    def empty[A]: Stream[A] = Empty 

    def apply[A](as: A*): Stream[A] = 
    if (as.isEmpty) empty else cons(as.head, apply(as.tail: _*)) 

} 

Da applyvarargs als Argument erwarte ich eine neue Stream wie erstellen:

val s = Stream(2,3,4,5) 

ich einige Fragen über ADTStream

1. Do die apply functi bei einem rekursiven Aufruf? Ich habe versucht, den Code zu debuggen, aber es geht nur einmal durch.

2. Wenn ich eine Definition val s = Stream(2,3,4,5) habe, wie kann ich den Kopf davon nennen? Ich habe versucht s.h, aber ich habe Compiler-Fehler.

Answer 1

Ja, es ist rekursiv, da es apply auf den Schwanz as nennt. Da jedoch h und t in Cons Funktionen sind, die nur bei Bedarf ausgewertet werden, haben Sie die Methode im Debugger nur einmal eingegeben, da der Tail noch nicht ausgewertet wurde.

Sie können den Kopf des s mit Muster erhalten

val h = s match { 
    case Cons(h,t) => h 
} 

Die Art der h passend ist () => Integer so die ganze Zahl Sie sie bewerten haben zu erhalten.

h() 

Answer 2

Stream ist eine Implementierung von faulen Kollektionen: der Kopf und Schwanz werden nur ausgewertet, wenn es aufgerufen wird.

Deshalb sind die Eigenschaften von Cons vom Typ () => T, dh Funktionen von Nullelementen.

Die apply Funktion definiert ihren Kopf als das erste Element der varargs, und ihr Schwanz als die gleiche Funktion auf den Schwanz der varags angewendet. Da sie jedoch nur bei Bedarf ausgewertet werden, ruft Ihr Aufruf unter apply(1, 2, 3) nicht die Tail-Funktion auf, sodass Sie die rekursiven Aufrufe nicht sehen.

Da Argumente von Cons keine Argumentfunktionen sind, müssen Sie sie aufrufen, um ihren Wert zu erhalten. So, um den Kopf Ihrer Stream zu erhalten, rufen Sie s.h().

Answer 3

nur auf der Suche Methode Signatur anwenden man denken könnte, dass wir hier mit regelmäßiger Rekursion handeln:

def cons[A](hd: => A, t1: => Stream[A]): Stream[A] 

Wie Sie beiden Parameter Aufruf sind sehen“:

def apply[A](as: A*): Stream[A] = 
    if (as.isEmpty) empty else cons(as.head, apply(as.tail: _*)) 

Nachteile Signatur analysieren lassen -namentlich". Dies bedeutet, dass der übergebene Ausdruck nicht sofort ausgewertet wird. Unter der Haube erweitert Scala-Compiler sie, um ohne Argumente zu funktionieren. Diese Funktion kann an beliebiger Stelle in einem Programm aufgerufen werden.

Im Hinblick auf die Nachteile Methode, betrachten diese beiden Zeilen:

lazy val head = hd 
lazy val tail = t1 

Keine Bewertung hier entweder durchgeführt wird. Lassen Sie uns gerade gehen wir davon aus memoization nicht ausführen, auf diese Weise wir Nachteile Argumente explizit Cons Konstruktor Aufruf substitue kann, führt dies zu den folgenden:

Cons(h:() => hd, t:() => t1) 

nun dank der Natur der „Call-by-name“ wir können schreiben:

Cons(h:() => as.head, t:() => apply(as.tail:_*)) 

Das Folgende ist kein gültiger Scala-Code, sondern erklärt, was passiert. Jetzt ist es klar, dass rekursiver Aufruf zur Methode anwenden nur ausgeführt wird, wenn jemand explizit t() Funktion auf Cons Instanz aufruft. Es gibt viele Vorteile dieses Ansatzes, der größte ist, dass wir Stack-Overflow vermeiden. Siehst du warum?