एक डीएलआईस्ट क्या है?

Question

मैंने इसके लिए गुगल करने की कोशिश की लेकिन मुझे जो कुछ मिला वह मामूली हस्तियों के बारे में कहानियां थीं। दस्तावेज की कमी को देखते हुए, DList क्या है?

Answer 1

यह एक अलग सूची है, "Difference List as functions"

scala> val (l1, l2, l3) = (List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)) 
l1: List[Int] = List(1, 2, 3) 
l2: List[Int] = List(4, 5, 6) 
l3: List[Int] = List(7, 8, 9) 

कुशल prepending की तर्ज पर:

scala> l1 ::: l2 ::: l3 
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

अकुशल appending। यह एक मध्यवर्ती सूची (एल 1 ++ l2), तो ((एल 1 ++ l2) ++ L3)

scala> l1 ++ l2 ++ l3 // inefficient 
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

DList भंडार अप संलग्न कर देता है बनाता है, और केवल एक पूरी सूची बनाने के लिए की जरूरत है, प्रभावी ढंग से लागू:

scala> List(l1, l2, l3) reduceRight (_ ::: _) 
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

Answer 2

यह गैर-कैननिकल scalaz पैकेज में डेटा प्रकार है, जो दोनों सिरों पर निरंतर-समय पहुंच के साथ टाइप की गई सूचियों के लिए उपयोगी है। (चाल "स्केला" और "dlist" के लिए गूगल के लिए है।)

Answer 3

project page of scalaz से:

DList, निरंतर समय संलग्न/बढ़ाएँ संचालन के साथ एक ही प्रकार के तत्वों का प्रतिनिधित्व करने के लिए एक डेटा प्रकार।

Answer 4

अंतर सूचियों एक सूची की तरह डेटा संरचना है कि हे (1) संलग्न आपरेशन का समर्थन करता है कर रहे हैं।

संलग्न करें, और सूची को संशोधित करने वाले अन्य संचालन को सीधे सूची की प्रतिलिपि बनाने के बजाय संशोधन कार्यों की फ़ंक्शन संरचना के माध्यम से दर्शाया जाता है।

एक उदाहरण है, Haskell's dlist library से:

-- Lists as functions 
newtype DList a = DL { unDL :: [a] -> [a] } 

-- The empty list 
empty  = DL id 

-- The append case: composition, a la Hughes 
append xs ys = DL (unDL xs . unDL ys) 

-- Converting to a regular list, linear time. 
toList  = ($[]) . unDL 

तकनीक कम से कम Hughes 84, सूचियों में से एक उपन्यास प्रतिनिधित्व और कार्य करने के लिए अपने आवेदन करने के लिए, आर जॉन ह्यूजेस, 1984 "रिवर्स" वापस चला जाता है। , जहां, वह कार्यों के रूप में सूचियों का प्रतिनिधित्व करने का प्रस्ताव करता है, और फ़ंक्शन संरचना के रूप में संलग्न करता है, उदाहरण के लिए अनुमति देता है रैखिक समय में चलाने के लिए विपरीत। कागज से:

---

---