Kiselyov के ज़िप्पर के Idiomatic Scala अनुवाद?

Question

ओलेग Kiselyov showed how to make a zipper from any traversable सीमित निरंतरता का उपयोग करके। उसका हास्केल कोड काफी छोटा है:

module ZipperTraversable where 

import qualified Data.Traversable as T 
import qualified Data.Map as M 


-- In the variant Z a k, a is the current, focused value 
-- evaluate (k Nothing) to move forward 
-- evaluate (k v)  to replace the current value with v and move forward. 

data Zipper t a = ZDone (t a) 
       | Z a (Maybe a -> Zipper t a) 

make_zipper :: T.Traversable t => t a -> Zipper t a 
make_zipper t = reset $ T.mapM f t >>= return . ZDone 
where 
f a = shift (\k -> return $ Z a (k . maybe a id)) 

-- The Cont monad for delimited continuations, implemented here to avoid 
-- importing conflicting monad transformer libraries 

newtype Cont r a = Cont{runCont :: (a -> r) -> r} 

instance Monad (Cont r) where 
    return x = Cont $ \k -> k x 
    m >>= f = Cont $ \k -> runCont m (\v -> runCont (f v) k) 

-- Two delimited control operators, 
-- without answer-type polymorphism or modification 
-- These features are not needed for the application at hand 

reset :: Cont r r -> r 
reset m = runCont m id 

shift :: ((a -> r) -> Cont r r) -> Cont r a 
shift e = Cont (\k -> reset (e k)) 

मैंने स्कैला में इसे लागू करने की कोशिश करने वाली कुछ समस्याओं में भाग लिया है। मैंने स्कैला के सीमित निरंतरता पैकेज का उपयोग करने की कोशिश करना शुरू कर दिया, लेकिन रोमपैफ़ के richIterable का उपयोग @spspendable के बजाय @cps [X] को सामान्यीकृत करने के लिए भी किया गया है, रीसेट करने के लिए प्रदान किए गए फ़ंक्शन की तुलना में बदलाव को अलग-अलग प्रकार में बदलने के लिए फ़ंक्शन प्रदान करना असंभव है।

मैंने Kiselyov की परिभाषा के बाद निरंतरता मोनैड को कार्यान्वित करने का प्रयास किया, लेकिन स्कैला ने टाइप पैरामीटर को करी करना मुश्किल बना दिया और मैं समझ नहीं पाया कि कंट्रोल [आर] को एक मोनैड में कैसे बदलना है जिससे स्केलज़ की ट्रैवर्स विधि खुश थी ।

मैं हास्केल और स्कैला दोनों में एक नौसिखिया हूं, और वास्तव में इसके साथ मदद की सराहना करता हूं।

Answer 1

आप निरंतरता प्लगइन का उपयोग कर सकते हैं। प्लगइन के अनुवाद के बाद, इसमें Cont मोनैड और shift और reset ओलेग से समानताएं होती हैं। मुश्किल हिस्सा प्रकारों को समझना है। तो यहाँ मेरी अनुवाद है:

import util.continuations._ 
import collection.mutable.ListBuffer 

sealed trait Zipper[A] { def zipUp: Seq[A] } 
case class ZDone[A](val zipUp: Seq[A]) extends Zipper[A] 
case class Z[A](current: A, forward: Option[A] => Zipper[A]) extends Zipper[A] { 
    def zipUp = forward(None).zipUp 
} 

object Zipper { 
    def apply[A](seq: Seq[A]): Zipper[A] = reset[Zipper[A], Zipper[A]] { 
    val coll = ListBuffer[A]() 
    val iter = seq.iterator 
    while (iter.hasNext) { 
     val a = iter.next() 
     coll += shift { (k: A=>Zipper[A]) => 
     Z(a, (a1: Option[A]) => k(a1.getOrElse(a))) 
     } 
    } 
    ZDone(coll.toList) 
    } 
} 

निरंतरता प्लगइन while पाश के लिए समर्थन हासिल है लेकिन map या flatMap के लिए नहीं है, इसलिए मैं while और एक परिवर्तनशील ListBuffer का उपयोग कर संभवतः अद्यतन तत्वों पर कब्जा करने का चुनाव किया है। make_zipper फ़ंक्शन का अनुवाद Zipper.apply - नए ऑब्जेक्ट्स या संग्रह बनाने के लिए एक विशिष्ट स्कैला स्थान में किया गया है। डेटा प्रकार का अनुवाद एक सीलबंद विशेषता में किया जाता है जिसमें दो केस वर्गों को विस्तारित किया जाता है। और मैंने प्रत्येक केस क्लास के लिए विभिन्न कार्यान्वयन के साथ zip_up फ़ंक्शन को Zipper की विधि के रूप में रखा है। यह भी बहुत विशिष्ट है।

यहाँ यह कार्रवाई में है:

object ZipperTest extends App { 
    val sample = for (v <- 1 to 5) yield (v, (1 to v).reduceLeft(_ * _)) 
    println(sample) // Vector((1,1), (2,2), (3,6), (4,24), (5,120)) 

    def extract134[A](seq: Seq[A]) = { 
    val Z(a1, k1) = Zipper(seq) 
    val Z(a2, k2) = k1(None) 
    val Z(a3, k3) = k2(None) 
    val Z(a4, k4) = k3(None) 
    List(a1, a3, a4) 
    } 
    println(extract134(sample)) // List((1,1), (3,6), (4,24)) 

    val updated34 = { 
    val Z(a1, k1) = Zipper(sample) 
    val Z(a2, k2) = k1(None) 
    val Z(a3, k3) = k2(None) 
    val Z(a4, k4) = k3(Some(42 -> 42)) 
    val z = k4(Some(88 -> 22)) 
    z.zipUp 
    } 
    println(updated34) // List((1,1), (2,2), (42,42), (88,22), (5,120)) 
} 

मैं shift, k और reset या कैसे T.mapM अनुवाद करने के लिए प्रकार कैसे समझ गए थे?

मैंने mapM पर देखा और मुझे पता है कि यह मुझे Cont प्राप्त करने की अनुमति देगा, लेकिन मुझे यकीन नहीं है कि Cont के अंदर क्या है क्योंकि यह शिफ्ट पर निर्भर करता है। तो मैं शिफ्ट के अंदर शुरू करता हूँ। Cont बनाने के लिए हैकेल return को अनदेखा करते हुए, शिफ्ट Zipper देता है। मुझे यह भी लगता है कि निर्माण के लिए मुझे अपने संग्रह में A का एक तत्व जोड़ने की आवश्यकता है। तो शिफ्ट "छेद" में होगी जहां A प्रकार का तत्व अपेक्षित है, इसलिए kA=>? फ़ंक्शन होगा। आइए मान लें। मैं उन प्रकारों के बाद प्रश्न चिह्न डाल रहा हूं जिनके बारे में मुझे इतना यकीन नहीं था। तो मैंने इसके साथ शुरू किया:

shift { (k: A?=>?) => 
    Z(a, ?) 
} 

अगला मैंने देखा (हार्ड) (k . maybe a id) पर। फंक्शन maybe a id एक A लौटाएगा, इसलिए यह k के साथ एक तर्क के रूप में आता है। यह a1.getOrElse(a) के बराबर है। इसके अलावा, मुझे Z(a, ?) भरने की आवश्यकता है, मुझे यह पता लगाने की आवश्यकता है कि विकल्प से जिपर तक फ़ंक्शन कैसे प्राप्त करें। सबसे आसान तरीका यह मानना ​​है कि kZipper देता है।इसके अलावा, जिपर का उपयोग k1(None) या k1(Some(a)) पर किया जाता है, मुझे पता है कि मुझे उपयोगकर्ता को वैकल्पिक रूप से तत्वों को प्रतिस्थापित करने का तरीका देना है, जो कि forward फ़ंक्शन करता है। यह मूल a या अद्यतन a के साथ जारी है। यह समझ में आता है। तो अब मेरे पास है:

shift { (k: A=>Zipper[A]) => 
    Z(a, (a1: Option[A]) => k(a1.getOrElse(a))) 
} 

अगला मैं mapM फिर से देखता हूं। मुझे लगता है कि यह return . ZDone से बना है। return फिर से अनदेखा करें (क्योंकि यह केवल Cont मोनड के लिए है), मुझे लगता है कि ZDone परिणामस्वरूप संग्रह लेगा। तो यह सही है, मुझे बस इसमें coll डालना होगा और जब तक कार्यक्रम आ जाएगा, तब तक इसमें अपडेट किए गए तत्व होंगे। साथ ही, reset के अंदर अभिव्यक्ति का प्रकार अब k के रिटर्न प्रकार के साथ संगत है जो Zipper[A] है।

अंततः मैं रीसेट के लिए प्रकार भरता हूं जो संकलक अनुमान लगा सकता है, लेकिन जब मुझे सही लगता है, तो यह मुझे आत्मविश्वास की एक झूठी भावना देता है, मुझे पता है कि क्या हो रहा है।

मेरा अनुवाद सामान्य के रूप में सामान्य नहीं है या हास्केल के रूप में सुंदर है क्योंकि यह संग्रह से प्रकार को संरक्षित नहीं करता है और उत्परिवर्तन का उपयोग करता है लेकिन उम्मीद है कि यह समझना आसान है।

संपादित करें:

import util.continuations._ 
import collection.generic.CanBuild 
import collection.SeqLike 

sealed trait Zipper[A, Repr] { def zipUp: Repr } 
case class ZDone[A, Repr](val zipUp: Repr) extends Zipper[A, Repr] 
case class Z[A, Repr](current: A, 
    forward: Option[A] => Zipper[A, Repr]) extends Zipper[A, Repr] { 
    def zipUp = forward(None).zipUp 
} 

object Zipper { 
    def apply[A, Repr](seq: SeqLike[A, Repr]) 
        (implicit cb: CanBuild[A, Repr]): Zipper[A, Repr] = { 
    type ZAR = Zipper[A, Repr] 

    def traverse[B](s: Seq[A])(f: A => B@cps[ZAR]): List[B]@cps[ZAR] = 
     if (s.isEmpty) List() 
     else f(s.head) :: traverse(s.tail)(f) 

    reset { 
     val list = traverse(seq.toSeq)(a => shift { (k: A=>ZAR) => 
     Z(a, (a1: Option[A]) => k(a1.getOrElse(a))) 
     }) 
     val builder = cb() ++= list 
     ZDone(builder.result): ZAR 
    } 
    } 
} 

---

वैसे, यहाँ स्केला में निरंतरता इकाई पर अतिरिक्त संसाधन हैं: यहाँ संस्करण उस प्रकार को बरकरार रखता है और अपरिवर्तनीय सूची ताकि z.zipUp == z.zipUp का उपयोग करता है:

• http://blog.tmorris.net/continuation-monad-in-scala/
• क्या जब मैंने पहली बार कोशिश की तो मैंने खुद को रखा: https://gist.github.com/huynhjl/4077185; इसमें स्काला विभिन्न हास्केल निरंतरता उदाहरणों के साथ-साथ टियर के पेपर से कुछ उदाहरणों का अनुवाद भी शामिल है (लेकिन निरंतरता प्लगइन का उपयोग नहीं करना जो दृष्टिकोण के बीच समानता को स्पष्ट रूप से इंगित करता है)।
• यदि आप स्कालाज़ डाउनलोड करते हैं, तो आप टोनी मॉरिस के स्केलज़ मोनाड इंस्टेंस को बनाने में सक्षम हो सकते हैं और स्केलज़ traverse का उपयोग कर सकते हैं - फिर स्केल का अनुवाद और अधिक शाब्दिक होगा।