क्या एक अपरिवर्तनीय लिंक्ड सूची में एक चक्र बनाना संभव है?

Question

मान लीजिए कि हमें जावा में निम्नलिखित संरचना है:

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

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

स्काला में निर्मित अपरिवर्तनीय अकेले लिंक्ड सूची के लिए समर्थन किया है। यह होगा:

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

तो, यह संभव सूचियों के इस प्रकार (अपरिवर्तनीय अकेले लिंक्ड सूची) में एक चक्र बनाने के लिए है। चक्र से, मेरा मतलब है निम्नलिखित:

Answer 1

आप lazy संग्रह का उपयोग करना चाहिए अनंत संग्रह बनाने के लिए। आप 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

यह संभव नहीं है बस डिजाइन द्वारा। स्कैला की सूची अपरिवर्तनीय है, और आप मौजूदा सूची में जो कुछ भी कर सकते हैं वह मूल रूप से अपने सिर को हटा देता है (जो पूंछ पैदा करता है, दूसरे शब्दों में एक सूची जो खुद को अपरिवर्तनीय है) या एक तत्व को पूर्ववत करता है, जो एक नई अपरिवर्तनीय सूची प्रदान करता है। आप एक सूची का एक तत्व ले सकते हैं और इसे फिर से प्रस्तुत कर सकते हैं, लेकिन यह केवल एक लंबी सूची बनायेगा जहां दो तत्व एक ही उदाहरण हैं, यह चक्र नहीं बनाता है।

आपके पास दो सूचियां भी हो सकती हैं जो उनकी पूंछ का हिस्सा (या सभी) साझा करती हैं, लेकिन आप अभी भी लूप नहीं बना सकते हैं। क्योंकि एक लंबी सूची बनाने के लिए यह केवल है, तुम सब कर सकते हैं एक पहले से मौजूद सूची, जिसका अर्थ है कि एक सूची सिर में नोड्स (डिजाइन द्वारा) कर रहे हैं पुराने उदाहरणों से जोड़ें है कि पूंछ नोड्स। यह हमेशा मामला है। इससे यह चलता है कि लूप होने से एक विरोधाभास होगा।

तो संक्षिप्त उत्तर नहीं है, आप स्कैला (अपरिवर्तनीय) सूची के साथ चक्र नहीं बना सकते हैं।

एक के रूप में अलग रूप में, कारण है कि यह (के रूप में Senia के जवाब से दिखाया गया है) और Stream रों के साथ संभव है List रों (भले ही दोनों अपरिवर्तनीय संग्रह हैं) है कि Stream रों एक महत्वपूर्ण घटक जोड़ने के साथ नहीं: lazyness। स्ट्रीम नोड्स आलसी रूप से निर्मित होते हैं (एक नोड मूल रूप से अंगूठे को वास्तविक नोड की सामग्री में संग्रहीत करता है), जो बाद में नोड को पहले (और अभी तक कंस्ट्रक्शन नहीं) नोड को संदर्भित करने की अनुमति देता है, इस प्रकार लूप को अनुमति देता है।

Answer 3

ऐसा करने का एक और तरीका इस तथ्य का उपयोग करना है कि 'यह' सूचक पहले से ही कन्स्ट्रक्टर निष्पादित करने से पहले मौजूद है, और कन्स्ट्रक्टर के हिस्से के रूप में आप एक फ़ंक्शन को कॉल कर सकते हैं जो पैरामीटर के रूप में पारित किया गया था (इसके बजाए 'अगले' नोड के प्रत्यक्ष संदर्भ में गुजरना) उस समारोह में 'इस' सूचक को गुजर रहा है। यह कार्य अगले नोड के संदर्भ को उत्पन्न करने के लिए ज़िम्मेदार है, संभवतः पास-इन नोड मान पर आधारित है। एक किसी न किसी उदाहरण इस प्रकार है:

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 

बेशक

, यदि आपने इस निर्माता कहा जाता हो जाता है तो बकवास के सभी प्रकार के नई पीढ़ी समारोह के रूप में में पारित किया जा सकता है पर हुई पर्याप्त नियंत्रण में डाल नहीं है ...

Answer 4

जैसा कि पहले से ही उल्लेख किया गया है, आप किसी प्रकार की आलस्य के बिना एक अपरिवर्तनीय, चक्रीय संरचना नहीं बना सकते हैं। हालांकि, आप स्कालज़ के Name का लाभ उठा सकते हैं। इसमें कई कार्यान्वयन हैं, जिनमें से Need आलसी मूल्यांकन मूल्य प्रदान करता है।

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

यह हमें cycle की तरह काम करता है, जो पिछले चक्रीय संदर्भ Need का उपयोग कर के मूल्यांकन स्थगित परिभाषित करने के लिए अनुमति देता है: यह हमें एक लिंक्ड सूची जिसका next आस्थगित किया जा सकता है परिभाषित करने के लिए अनुमति देता है। अन्य सभी संदर्भों को आलसी होने की आवश्यकता नहीं है, इसलिए हम उन्हें Value में लपेटें (जो कुछ भी स्थगित नहीं करता है)।

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