Ist es möglich, einen Zyklus in einer unveränderbaren verknüpften Liste zu machen?

Question

Angenommen, wir die folgende Struktur in Java haben:

class List { 
    // we're immutable 
    final List next; 
    final int value; 

    public List(int value, List next) { 
    this.next = next; 
    this.value = value; 
    } 
} 

Scala hat eine integrierte Unterstützung für unveränderliche einfach verknüpften Liste. Es wäre:

val l = List(1, 2, 3) // immutable 

So ist es möglich, einen Zyklus in dieser Art von Listen (unveränderliche einfach verknüpften Liste) zu machen. Mit dem Zyklus, meine ich folgendes:

Answer 1

Sie lazy Sammlung verwenden sollten unendliche Sammlung zu erstellen. Sie könnten verwenden Stream:

def loopStream: Stream[Int] = { 
    lazy val loop: Stream[Int] = 3 #:: 4 #:: 5 #:: 6 #:: 7 #:: 8 #:: loop 
    1 #:: 2 #:: loop 
} 

loopStream.take(22).toList 
// List(1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4) 

Answer 2

Es ist nicht möglich, einfach durch Design. Scalas Liste ist unveränderlich, und alles, was Sie mit einer bestehenden Liste tun können, ist im Grunde genommen den Kopf (der den Schwanz ergibt, mit anderen Worten eine Liste, die selbst unveränderlich ist) oder ein Element voranzustellen, was zu einer neuen unveränderlichen Liste führt. Sie können ein Element einer Liste nehmen und es erneut vor, aber dies wird nur eine längere Liste erstellen, wo zwei Elemente die gleiche Instanz sind, erstellt dies keinen Zyklus.

Sie könnten auch zwei Listen haben, die Teile (oder alle) ihrer Tails teilen, aber Sie können immer noch keine Loops erstellen. Dies ist einfach weil, um eine längere Liste zu erstellen, alles, was Sie tun können, an eine bereits vorhandene Liste vorangestellt ist, was bedeutet, dass in einem Listenkopf Knoten (von Entwurf) ältere Instanzen sind, die Knoten. Dies ist immer der Fall. Daraus folgt, dass das Vorhandensein von Schleifen ein Widerspruch wäre.

Also die kurze Antwort ist nein, Sie können keine Zyklen mit Scala (unveränderlich) Liste erstellen.

AS Nebenbei bemerkt, ist der Grund, warum es mit Stream s möglich ist (wie durch senia Antwort gezeigt) und nicht mit List s (obwohl beide unveränderlich Sammlungen sind) ist, dass Stream s einen kritischen Bestandteil hinzu: lazyness. Stream-Knoten sind träge konstruiert (ein Knoten speichert im Wesentlichen einen -Thumb--Wert zum Inhalt des tatsächlichen Knotens), der es einem späteren Knoten ermöglicht, einen früheren (und noch nicht erstellten) Knoten zu referenzieren und somit Schleifen zuzulassen.

Answer 3

Eine andere Möglichkeit, dies zu tun, ist die Tatsache, dass der Zeiger 'this' bereits existiert, bevor der Konstruktor fertig ist. Als Teil des Konstruktors können Sie eine Funktion aufrufen, die als Parameter übergeben wurde Übergabe des direkten Verweises auf den 'nächsten' Knoten, wobei der Zeiger 'this' an diese Funktion übergeben wird. Die Funktion ist verantwortlich für das Erzeugen des Verweises auf den nächsten Knoten, möglicherweise basierend auf dem übergebenen Knotenwert. Ein einfaches Beispiel ist wie folgt:

class ListNode(val value: Int, genNext: ListNode => ListNode) { 
    val next = genNext(this) 
} 

def gen3(prev: ListNode): ListNode = new ListNode(3, any => prev) 

def gen2(prev: ListNode): ListNode = new ListNode(2, gen3 _) 

val loopingList = new ListNode(1, gen2 _) // will have 1 -> 2 -> 3 -> (back to) 2 

Natürlich, wenn Sie angerufen nicht gestellt wird anstelle genug Kontrolle darüber, wann dieser Konstruktor dann alle Arten von Müll übergeben als die Funktion GenNext werden könnten ...

Answer 4

Wie bereits erwähnt, können Sie keine unveränderliche, zyklische Struktur ohne irgendeine Art von Faulheit erstellen. Sie können jedoch einen Vorteil von scalaz Name nehmen. Es hat mehrere Implementierungen, von denen Need faul ausgewertete Werte liefert.Dies ermöglicht es uns, eine verknüpfte Liste, deren next zu definieren, kann aufgeschoben werden:

import scalaz._ 
import scalaz.Scalaz._ 

final case class LList[T](value: T, next: Name[LList[T]]) 
    extends Traversable[T] 
{ 
    @annotation.tailrec 
    override def foreach[U](f: T => U) { 
    f(value); 
    next.value.foreach(f); 
    } 
} 

Dies erlaubt uns, Funktionen zu definieren, wie cycle, das die Bewertung der letzten zyklischen Referenz aufschieben mit Need. Alle anderen Referenzen müssen nicht faul sein, also wickeln wir sie einfach in Value (was nichts verzögert).

object LList { 
    def cycle[T](xs: T*): LList[T] = { 
    lazy val r: LList[T] = 
     xs.foldRight[Name[LList[T]]](Need(r))(
     (x, r) => Value(LList(x,r)) 
    ).value; 
    r; 
    } 
}