1. घर
  2. सवाल और जवाब
  3. एक ग्रिड

एक ग्रिड

2016-03-06 6 views
17 
{-# LANGUAGE DeriveFoldable #-} 
{-# LANGUAGE DeriveFunctor #-} 
{-# LANGUAGE DeriveTraversable #-} 
import Control.Comonad 
import Data.Functor.Reverse 
import Data.List (unfoldr)

पहले कुछ संदर्भ (हा हा) पर ध्यान केंद्रित करने के सभी तरीकों को खोजना। मेरे पास zipper गैर-खाली सूचियों पर है।एक ग्रिड

data LZipper a = LZipper (Reverse [] a) a [a] 
    deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable) 

mkZipper :: a -> [a] -> LZipper a 
mkZipper = LZipper (Reverse [])

आप जिपर के साथ किसी भी दिशा में कदम उठा सकते हैं, लेकिन आप अंत से गिर सकते हैं।

fwd, bwd :: LZipper a -> Maybe (LZipper a) 
fwd (LZipper _ _ []) = Nothing 
fwd (LZipper (Reverse xs) e (y:ys)) = Just $ LZipper (Reverse (e:xs)) y ys 
bwd (LZipper (Reverse []) _ _) = Nothing 
bwd (LZipper (Reverse (x:xs)) e ys) = Just $ LZipper (Reverse xs) x (e:ys)

एक ज़िपर नकल आप सभी तरीकों से आप इसे देख सकते हैं, जिस तरह से आप इसे वर्तमान में देख रहे हैं पर ध्यान देने के साथ दिखाता है।

instance Comonad LZipper where 
    extract (LZipper _ x _) = x 
    duplicate z = LZipper (Reverse $ unfoldr (step bwd) z) z (unfoldr (step fwd) z) 
     where step move = fmap (\y -> (y, y)) . move

उदाहरण के लिए:

ghci> duplicate (mkZipper 'a' "bc") 
LZipper (Reverse []) 
     (LZipper (Reverse "") 'a' "bc") 
     [LZipper (Reverse "a") 'b' "c",LZipper (Reverse "ba") 'c' ""] 
-- Abc -> *Abc* aBc abC 

ghci> fmap duplicate (fwd $ mkZipper 'a' "bc") 
Just (LZipper (Reverse [LZipper (Reverse "") 'a' "bc"]) 
       (LZipper (Reverse "a") 'b' "c") 
       [LZipper (Reverse "ba") 'c' ""]) 
-- aBc -> Abc *aBc* abC

(मैं ज़िपर का केन्द्र बिन्दु इंगित करने के लिए की राजधानियों और तारक उपयोग कर रहा हूँ।)

मैं दो के साथ काम करने की कोशिश कर रहा हूँ

फोकस के साथ आयामी ग्रिड, ज़िप्पर के एक जिपर के रूप में प्रतिनिधित्व किया। प्रत्येक आंतरिक जिपर ग्रिड की एक पंक्ति है। मेरा अंतिम लक्ष्य पड़ोसी से पड़ोसी से छिपकर ग्रिड के माध्यम से पथ ढूंढना है।

ग्रिड के माध्यम से चलना इनवेरिएंट को बनाए रखता है कि सभी पंक्तियों को एक ही इंडेक्स पर केंद्रित किया जाता है। यह आपके पड़ोसियों पर ध्यान केंद्रित करना आसान बनाता है।

type Grid a = LZipper (LZipper a) 

up, down, left, right :: Grid a -> Maybe (Grid a) 
up = bwd 
down = fwd 
left = traverse bwd 
right = traverse fwd 

extractGrid :: Grid a -> a 
extractGrid = extract . extract 
mkGrid :: (a, [a]) -> [(a, [a])] -> Grid a 
mkGrid (x, xs) xss = mkZipper (mkZipper x xs) $ map (uncurry mkZipper) xss

उदाहरण: एक समारोह है कि एक ग्रिड लेता है और सभी तरह से आप ग्रिड पर दिखाई दे सकता है की एक ग्रिड का उत्पादन:

ghci> let myGrid = mkGrid ('a', "bc") [('d', "ef"), ('g', "hi")] 
ghci> myGrid 
LZipper (Reverse []) 
     (LZipper (Reverse "") 'a' "bc") 
     [LZipper (Reverse "") 'd' "ef",LZipper (Reverse "") 'g' "hi"] 
-- +-------+ 
-- | A b c | 
-- | d e f | 
-- | g h i | 
-- +-------+ 

ghci> return myGrid >>= right >>= down 
Just (LZipper (Reverse [LZipper (Reverse "a") 'b' "c"]) 
       (LZipper (Reverse "d") 'e' "f") 
       [LZipper (Reverse "g") 'h' "i"]) 
-- +-------+ 
-- | a b c | 
-- | d E f | 
-- | g h i | 
-- +-------+

क्या मैं चाहता हूँ ग्रिड के लिए LZipper के duplicate के बराबर है , वर्तमान पर ध्यान केंद्रित करने के साथ आप इसे देख रहे हैं।

duplicateGrid :: Grid a -> Grid (Grid a)

मैं क्या उम्मीद कर रहा हूँ:

duplicateGrid myGrid 
+-------------------------------+ 
| ********* +-------+ +-------+ | 
| * A b c * | a B c | | a b C | | 
| * d e f * | d e f | | d e f | | 
| * g h i * | g h i | | g h i | | 
| ********* +-------+ +-------+ | 
| +-------+ +-------+ +-------+ | 
| | a b c | | a b c | | a b c | | 
| | D e f | | d E f | | d e F | | 
| | g h i | | g h i | | g h i | | 
| +-------+ +-------+ +-------+ | 
| +-------+ +-------+ +-------+ | 
| | a b c | | a b c | | a b c | | 
| | d e f | | d e f | | d e f | | 
| | G h i | | g H i | | g h I | | 
| +-------+ +-------+ +-------+ | 
+-------------------------------+

मैं duplicateGrid = duplicate . duplicate की कोशिश की। यह सही प्रकार है, लेकिन (यह मानते हुए कि मैं show उत्पादन सही ढंग से व्याख्या की है, जो मैं शायद नहीं था) यह केवल देता है मुझे कहीं प्रथम स्तंभ पर ध्यान केंद्रित ग्रिड:

(duplicate . duplicate) myGrid 
+-------------------------------+ 
| ********* +-------+ +-------+ | 
| * A b c * | a b c | | a b c | | 
| * d e f * | D e f | | d e f | | 
| * g h i * | g h i | | G h i | | 
| ********* +-------+ +-------+ | 
| +-------+ +-------+ +-------+ | 
| | A b c | | a b c | | a b c | | 
| | d e f | | D e f | | d e f | | 
| | g h i | | g h i | | G h i | | 
| +-------+ +-------+ +-------+ | 
| +-------+ +-------+ +-------+ | 
| | A b c | | a b c | | a b c | | 
| | d e f | | D e f | | d e f | | 
| | g h i | | g h i | | G h i | | 
| +-------+ +-------+ +-------+ | 
+-------------------------------+

मैं भी duplicateGrid = duplicate . fmap duplicate की कोशिश की। एक बार फिर से यह मानते हुए कि मैं show उत्पादन व्याख्या करने में सक्षम हूँ, यह मुझे कुछ है कि दोनों गलत ग्रिड निहित दिया और गलत संरेखित पंक्तियों की केंद्रित, ऐसी है कि नीचे जा भी साथ आप ले होता था:

(duplicate . fmap duplicate) myGrid 
+-------------------------------+ 
| ********* +-------+ +-------+ | 
| * A b c * | D e f | | G h i | | 
| * a B c * | d E f | | g H i | | 
| * a b C * | d e F | | g h I | | 
| ********* +-------+ +-------+ | 
| +-------+ ********* +-------+ | 
| | A b c | * D e f * | G h i | | 
| | a B c | * d E f * | g H i | | 
| | a b C | * d e F * | g h I | | 
| +-------+ ********* +-------+ | 
| +-------+ +-------+ ********* | 
| | A b c | | D e f | * G h i * | 
| | a B c | | d E f | * g H i * | 
| | a b C | | d e F | * g h I * | 
| +-------+ +-------+ ********* | 
+-------------------------------+

ऐसा लगता है कि यह जानने वालों के लिए एक आसान सवाल होगा, लेकिन यह मेरा सिर स्पिन कर रहा है। मुझे लगता है कि मैं एक समारोह को हाथ-क्रैंक कर सकता हूं जो up, down, left और right पर कॉल करता है, लेकिन मुझे लगता है कि कॉमोनैडिक मशीनरी को मेरे लिए ऐसा करने में सक्षम होना चाहिए। duplicateGrid का सही कार्यान्वयन क्या है?

स्रोत

2016-03-06 Benjamin Hodgson

+2

एफवाईआई, आपको अन्य बिट्स में रुचि हो सकती है। Http: // stackoverflow देखें।कॉम/ए/25572148/1477667 – dfeuer

+2

और [यह एक] (http://stackoverflow.com/questions/12963733/writing-cojoin-or-cobind-for-n-dimensional-grid-type/13100857#13100857) कौन से पते आपका प्रश्न विशेष रूप से। मैंने किसी भी तरह इसे याद किया, और मेरा जवाब इसकी रोशनी में अनावश्यक है, लेकिन कम से कम मुझे अपने लिए इसका हिस्सा समझने का अवसर मिला। –

+0

@ AndrásKovács डी ओह, मेरा सवाल उस का सटीक डुप्लिकेट प्रतीत होता है। पता नहीं जब मैं खोज रहा था मुझे यह क्यों नहीं मिला। मैं सही काम करूंगा और इसे बंद कर दूंगा। –

उत्तर

9

यह एक मुद्दा है कि हम Grid लिखने की कोशिश कर रहे हैं, क्योंकि यह सेटअप हमें duplicate को सही प्रकार के साथ लागू करने के कई तरीके हैं। सामान्य मामले पर विचार करना उपयोगी होता है जहां रचित कॉमोनैड जरूरी नहीं होते हैं।

मान लें कि हमारे पास f और g कॉमोनैड हैं। duplicate के प्रकार के हो जाता है:

duplicate :: f (g a) -> f (g (f (g a)))

हम निम्नलिखित केवल Comonad उदाहरणों का प्रयोग करते प्राप्त कर सकते हैं:

duplicate . fmap duplicate :: f (g a) -> f (f (g (g a)))
इस से

यह स्पष्ट हो जाता है कि हम बीच में f और g स्वैप करने के लिए की जरूरत है।

Distributive नामक एक प्रकार की कक्षा है जिसमें हमारी इच्छित विधि है।

class Functor g => Distributive g where 
    distribute :: Functor f => f (g a) -> g (f a)

विशेष रूप से, हम Distributive g लागू करने की आवश्यकता है, और फिर बना comonad के लिए duplicate रूप में लागू किया जा सकता है:

duplicate = fmap distribute . duplicate . fmap duplicate

हालांकि, Distributive में प्रलेखन का कहना है कि g के मूल्यों सटीक होना आवश्यक है एक ही आकार, इसलिए हम जानकारी के नुकसान के बिना प्रतियों की मनमानी संख्या को एक साथ जोड़ सकते हैं।

यह उदाहरण के लिए, Vec n an-आकार वाले वेक्टर है, तो distribute :: [Vec n a] -> Vec n [a] सिर्फ मैट्रिक्स ट्रांसपोजिशन है। पहले से ही आंतरिक वेक्टर के नीचे आकार को पिन करना जरूरी है, क्योंकि "ragged" मैट्रिक्स पर पारदर्शिता को कुछ तत्व छोड़ना चाहिए, और यह वैध व्यवहार नहीं है। अनंत धाराएं और ज़िप्पर भी ठीक वितरित करते हैं, क्योंकि उनके पास भी एक संभव आकार होता है।

Zipper एक वैध Distributive नहीं है क्योंकि Zipper में विभिन्न आकार के संदर्भों वाले मान हैं। फिर भी, हम अनुचित वितरण को कार्यान्वित कर सकते हैं जो समान संदर्भ आकार का अनुमान लगाता है।

नीचे अंतर्निहित सूचियों के अनुचित वितरण के संदर्भ में Grid के लिए duplicate लागू किया जाएगा।

वैकल्पिक रूप से, कोई भी अपनी आस्तीन को रोल कर सकता है और सीधे Zipper (Zipper a) पर एक पारदर्शिता फ़ंक्शन लागू कर सकता है। मैंने वास्तव में यह किया, लेकिन यह मुझे सिरदर्द देता है और मुझे विश्वास है कि यह सही है। संभावित कार्यान्वयन की जगह को कम करने के लिए, जितना संभव हो उतना सामान्य बनाना बेहतर है, इसलिए त्रुटियों के लिए कम जगह है।

मैं वाक्य रचनात्मक शोर को कम करने के लिए Reverse को छोड़ने जा रहा हूं; मुझे आशा है कि आप मुझे क्षमा करें।

{-# language DeriveFunctor #-} 

import Control.Comonad 
import Data.List 
import Control.Monad 

data Zipper a = Zipper [a] a [a] deriving (Eq, Show, Functor) 

lefts, rights :: Zipper a -> [a] 
lefts (Zipper ls _ _) = ls 
rights (Zipper _ _ rs) = rs 

bwd :: Zipper a -> Maybe (Zipper a) 
bwd (Zipper [] _ _) = Nothing 
bwd (Zipper (l:ls) a rs) = Just $ Zipper ls l (a:rs) 

fwd :: Zipper a -> Maybe (Zipper a) 
fwd (Zipper _ _ []) = Nothing 
fwd (Zipper ls a (r:rs)) = Just $ Zipper (a:ls) r rs 

instance Comonad Zipper where 
    extract (Zipper _ a _) = a 
    duplicate z = 
    Zipper (unfoldr (fmap (join (,)) . bwd) z) z (unfoldr (fmap (join (,)) . fwd) z)

हम सूचियों वितरित कर सकते हैं अगर हम उनकी लंबाई पहले से पता है। चूंकि हास्केल सूचियां अनंत हो सकती हैं, इसलिए हमें संभवतः अनंत आलसी प्राकृतिकों के साथ लंबाई मापनी चाहिए। लंबाई मापने का एक वैकल्पिक समाधान "गाइड" सूची का उपयोग करेगा जिसके साथ हम अन्य सूचियों को ज़िप कर सकते हैं। हालांकि, मैं वितरण कार्यों में नहीं मानूंगा कि ऐसी डमी सूची हमेशा उपलब्ध है।

data Nat = Z | S Nat 

length' :: [a] -> Nat 
length' = foldr (const S) Z 

distList :: Functor f => Nat -> f [a] -> [f a] 
distList Z  fas = [] 
distList (S n) fas = (head <$> fas) : distList n (tail <$> fas)

बेशक, यह हमारी लंबाई धारणा गलत होने पर रनटाइम अपवादों में विफल रहता है।

distZipper :: Functor f => Nat -> Nat -> f (Zipper a) -> Zipper (f a) 
distZipper l r fz = Zipper 
    (distList l (lefts <$> fz)) (extract <$> fz) (distList r (rights <$> fz))

अंत में हम, हम जिस तरह से हम पहले देखा था में Grid रों नकल कर सकते हैं, लेकिन पहले:

हम Zipper उनके केंद्रित और संदर्भों के वितरण के द्वारा, बशर्ते कि हम संदर्भों की लंबाई पता वितरित कर सकते हैं आंतरिक Zipper एस के आकार को निर्धारित करना होगा। जब से हम मान लेते हैं कि सभी आंतरिक Zipper रों एक ही आकार है, हम केवल ध्यान में Zipper को देखो:

duplicateGrid :: Grid a -> Grid (Grid a) 
duplicateGrid [email protected](Zipper _ (Zipper ls _ rs) _) = 
    fmap (distZipper (length' ls) (length' rs)) $ duplicate $ fmap duplicate grid

परीक्षण इस (के रूप में आप पहले से ही अनुभवी होना आवश्यक है) बहुत भयंकर है, और मैं अभी तक नहीं है हाथ से दो-दो-दो मामले भी जांचने के लिए चारों ओर मिल गया।

फिर भी, मैं उपर्युक्त कार्यान्वयन में काफी भरोसा करता हूं, क्योंकि परिभाषाएं प्रकारों से अत्यधिक बाधित होती हैं।

स्रोत

2016-03-06 19:01:14

+0

क्यों नहीं मानते कि "डमी सूची" उपलब्ध है? मेरा मानना ​​है कि आप उन लोगों में से एक प्राप्त करते हैं जब आप एक सामान्यीकृत 'प्रतिकृति' लिख सकते हैं, और मुझे नहीं लगता कि आप जो कर रहे हैं वह उस संदर्भ के बाहर समझ में आएगा। – dfeuer

+2

मैंने इसके बारे में बहुत कुछ नहीं सोचा था, मैं आदत के रूप में सबसे कमजोर परिकल्पनाओं तक पहुंचने लगता हूं। अब जब आप इसे इंगित करते हैं, तो मुझे घुलनशील गिनती के साथ थोड़ा सा सोचना पड़ा। अब तक मैं इस के साथ आया हूं: यदि 'एफ' निरंतर मज़ेदार है, तो हमें किसी भी लंबाई के साथ 'वितरण' करने में सक्षम होना चाहिए। लेकिन यदि 'एफ' ए 'में' ए 'नीचे है, तो हम केवल' [] 'को डमी सूची (कुल भाषा में) के रूप में उत्पादित कर सकते हैं। –

+0

कॉमोनैड को अलग करने की इजाजत देने की आपकी चाल रोशनी थी; मैं 'ग्रिड' के बारे में 'जिपर' के _composition_ के रूप में नहीं सोच रहा था (और संबंधित 'कॉमोनैड' उदाहरण)। दो बार डुप्लिकेट करने का आपका समाधान और फिर वितरित करना [@ pigworker का उत्तर] (http://stackoverflow.com/a/13100857/1523776) के साथ मेल खाता है, यह देखते हुए कि यदि आपके पास मजबूत 'आवेदक' और 'ट्रैवर्सबल' बाधाओं तक पहुंच है - जो हम करते हैं - फिर 'वितरण' 'अनुक्रम ए' है। –

5

तो एक करीबी से संबंधित कॉमोनैड है जो आपको मार्गदर्शन करने में मदद कर सकता है।हम:

newtype MC m a = MC { unMC :: m -> a } 

instance Monoid m => Comonad (MC m) where 
    extract (MC f) = f mempty 
    duplicate (MC f) = MC (\x -> MC (\y -> f (x <> y))) 

instance Functor (MC m) where 
    fmap f (MC g) = MC (f . g)

तो एक दोनों ओर अनंत सरणी MC (Sum Integer) a हो सकता है और एक दोनों ओर अनंत ग्रिड MC (Sum Integer, Sum Integer) a होगा। और निश्चित रूप से, MC m (MC n a) घुमाव के माध्यम से MC (m,n) a पर isomorphic है।

किसी भी हाल में अपने वांछित डुप्लिकेट ग्रिड समारोह के अनुरूप (अनदेखी newtype रैपर और currying) होगा: 1 डी सरणी के लिए

duplicateGrid g x y dx dy = g (x + dx) (y + dy)

duplicate लगता है:

duplicate f x y = f (x+y)

तो duplicate . duplicate है :

(duplicate . duplicate) f x y z 
    = duplicate (duplicate f) x y z 
    = duplicate f (x+y) z 
    = f (x + y + z)

जो नहीं चाहता था। क्या की तरह fmap duplicate नज़र करता है:

fmap duplicate f x y z = f x (y + z)

यह स्पष्ट कर रहा है duplicate फिर हमें duplicate . duplicate के रूप में एक ही बात दे देंगे (जो यह होना चाहिए क्योंकि यह एक comonad कानून है)। फिर भी, यह थोड़ा और आशाजनक है। अगर हम दोfmap रों ...

fmap (fmap duplicate) f x y z w 
    = fmap duplicate (f x) y z w 
    = f x y (z + w)

किया अब अगर हम duplicate किया हम

(duplicate . fmap (fmap duplicate)) f x y z w = f (x+y) (z+w)

मिलता था लेकिन यह अभी भी गलत है। परिवर्तनीय नाम बदलना, इसकी f (x+y) (dx + dy)। तो हमें दो आंतरिक चरों को स्वैप करने के लिए कुछ चाहिए ... श्रेणी सिद्धांत सिद्धांत जो हम चाहते हैं वह एक वितरण कानून है। हास्केल नाम Traversable है। sequenceA फ़ंक्शंस की तरह दिखता है (फ़ंक्शंस Applicative फ़ंक्शनक्टर और वास्तव में Monad, Reader मोनड) जैसा दिखता है? प्रकार सब कहते हैं।

sequenceA :: (a -> b -> c) -> (b -> a -> c) 
sequenceA f x y = f y x

तो अंत में:

fmap sequenceA g x y z = g x z y 

(duplicate . fmap (fmap duplicate) . fmap sequenceA) g x y dx dy 
    = (duplicate . fmap (fmap duplicate)) g x dx y dy 
    = g (x + dx) (y + dy)

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

स्रोत

2016-03-06 17:39:07

7

आप जिस मौलिक समस्या में भाग रहे हैं वह zippers don't natively support 2-d structures है। जवाब बहुत अच्छा है (दूसरा जवाब मूल रूप से Grid की आपकी परिभाषा है) और मैं आपको इसे पढ़ने के लिए प्रोत्साहित करता हूं, लेकिन यह बात यह है कि ज़िप्पर वहां पहुंचने के लिए पथों के साथ तत्वों की पहचान करते हैं और 2-डी स्पेस में ऐसी पहचान होती है समस्याग्रस्त क्योंकि एक बिंदु पर जाने के लिए कई पथ हैं।

इसलिए आप देखेंगे कि जबकि Grid रों के लिए अपने up और down कार्यों पूरी तरह से जिपर है के रूप में परिभाषित किया गया था, आप Traversable मशीनरी का उपयोग करने left और right परिभाषित करने के लिए की जरूरत है। इसका मतलब यह भी है कि left और rightup और down के समान प्रदर्शन गुणों का आनंद न लें क्योंकि आप "अनाज के खिलाफ जा रहे हैं" ताकि आप बोल सकें।

के बाद से अपने Comonad उदाहरण केवल अपने ज़िपर कार्यों का उपयोग कर परिभाषित किया गया था, यह केवल duplicate दिशा है कि आपके ज़िपर, अर्थात् fwd और bwd (और विस्तार के up द्वारा और down) द्वारा परिभाषित किया गया है में कर सकते हैं।

संपादित करें: कुछ और विचारों के बाद मुझे लगता है कि आपका दृष्टिकोण मौलिक रूप से समस्याग्रस्त होने वाला है। मैंने नीचे अपना मूल पाठ संरक्षित किया है, लेकिन एक और चमकदार समस्या है।

यदि आप अपने ज़िप्परों को पार करने की कोशिश कर रहे हैं जैसे कि वे किसी भी 2-डी अन्य संरचना की तरह थे, तो आप Nothing को अपने duplicate के साथ प्राप्त करने जा रहे हैं। आइए ध्यान दें कि क्या होता है यदि आप वास्तव में अपने up, down, left, right कार्यों को स्पष्ट रूप से गैर-समस्याग्रस्त duplicate (mkZipper 'a' "bc") पर उपयोग करने का प्रयास करते हैं।

*Main> let allRows = duplicate $ mkZipper 'a' "bc" 
*Main> down allRows -- This is fine since we're following the zipper normally 
Just (LZipper (Backwards [LZipper (Backwards "") 'a' "bc"]) (LZipper (Backwards "a") 'b' "c") [LZipper (Backwards "ba") 'c' ""]) 
*Main> right allRows 
Nothing -- That's bad... 
*Main> down allRows >>= right 
Nothing -- Still nothing

right और left चलती आवश्यक है कि आपकी उप ज़िपर में से हर एक संरचना में सजातीय है (जैसा कि आप विधिवत अपरिवर्तनीय के अपने उल्लेख के साथ ध्यान दें), अन्यथा traverse बाहर समय से पहले ही असफल हो जायेगी। इसका अर्थ यह है कि यदि आप वास्तव में left और right का उपयोग करना चाहते हैं, तो duplicate के साथ यह अच्छा खेलने वाला एकमात्र तरीका यह है कि यदि आप सबसे अधिक duplicate संभवतः उपयोग करते हैं।

duplicate z @ (LZipper left focus right) = 
    LZipper (fmap (const z) left) z (fmap (const z) right)

विकल्प केवल जिपर के साथ आने वाले कार्यों का उपयोग करना है। इसका मतलब केवल fwd और bwd का उपयोग करना है, और फिर extract फोकस में fwd और bwd का उपयोग करना जारी रखने के लिए left और right जैसी चीज़ों का उपयोग करना है। बेशक इसका मतलब है कि "दाएं तो नीचे" और "नीचे दाएं" दोनों कहने की क्षमता छोड़ना, लेकिन जैसा कि हमने पहले ही देखा है, ज़िप्पर कई पथों के साथ अच्छी तरह से नहीं खेलते हैं।

अब duplicate . duplicate $ myGrid के साथ क्या चल रहा था, इसकी व्याख्या करने के तरीके के बारे में अपनी अंतर्ज्ञानों को दोबारा जांचें। एक अच्छा वर्ग वास्तव में क्या हो रहा है इसके बारे में सोचने का सबसे अच्छा तरीका नहीं है (और आप देखेंगे कि अगर आप खुद को extract और fwd और bwd पर सीमित क्यों करते हैं)।

*Main> let allRows = duplicate . duplicate $ myGrid 
*Main> fwd $ extract allRows -- Makes sense 
Just ... 
-- This *should* be the bottom-left of the grid 
*Main> let bottomLeft = extract <$> fwd allRows >>= fwd 
*Main> bottomLeft >>= fwd 
Nothing -- Nope! 
*Main> bottomLeft >>= bwd 
Just ... -- Wait a minute...

हमें वास्तव में एक कठोर संरचना मिली है।

+---------------------------------------------------+ 
|      ********* +-------+ +-------+ | 
|      * A b c * | a b c | | a b c | | 
|      * d e f * | D e f | | d e f | | 
|      * g h i * | g h i | | G h i | | 
|      ********* +-------+ +-------+ | 
|   +-------+ +-------+ +-------+   | 
|   | A b c | | a b c | | a b c |   | 
|   | d e f | | D e f | | d e f |   | 
|   | g h i | | g h i | | G h i |   | 
|   +-------+ +-------+ +-------+   | 
| +-------+ +-------+ +-------+      | 
| | A b c | | a b c | | a b c |      | 
| | d e f | | D e f | | d e f |      | 
| | g h i | | g h i | | G h i |      | 
| +-------+ +-------+ +-------+      | 
+---------------------------------------------------+

इस रैग किए गए ढांचे के अंदर के वर्ग वास्तव में वर्ग नहीं हैं, वे भी घबराएंगे। समान रूप से आप fwd को तिरछे जाने के बारे में सोच सकते हैं। या बस 2-डी संरचनाओं के लिए ज़िप्पर ड्रॉप करें।

मेरे अनुभव में, पेपर जैसी चीज़ों के साथ जोड़े जाने पर ज़िप्पर वास्तव में सबसे अच्छा काम करते हैं। मुझे आश्चर्य नहीं होगा अगर एक हास्केल विशेषज्ञ ज़िप्पर का उपयोग करने और चक्रीय ग्राफ या यहां तक ​​कि केवल सादे पुराने डीएजी जैसी चीजों के लिए उनके साथ आने वाले सभी अपडेट/एक्सेस भलाई के साथ आ सकता है, लेकिन मैं नहीं सोच सकता मेरे छोटे सिर के शीर्ष से कोई भी :)।

तो कहानी के नैतिक, ज़िप्पर 2-डी संरचनाओं के लिए सिरदर्द का थोड़ा सा हिस्सा हैं। (निष्क्रिय विचार: शायद लेंस दिलचस्प हो सकता है?)

उत्सुकता के लिए, नीचे मेरा दृष्टिकोण केवल तभी काम करता है जब आप उस संरचना की कठोरता को ध्यान में रखते हैं जो हम कर रहे हैं; यह fwd आईएनजी दो बार है और फिर निकालने से आप अपने ग्रिड के निचले-दाएं कोने में ओपी चाहता है, जो नीचे बाएं हाथ की तरफ नहीं है।

मूल:

तो क्या आप की जरूरत किसी तरह के बीच स्विच करने के लिए है अपने विशुद्ध रूप से ज़िपर आधारित duplicate और अपने Traversable आधारित डुप्लिकेट। सबसे आसान तरीका है कि आप duplicate फ़ंक्शन को पहले से लिखे गए हैं और बस बीच में traverse जोड़ें।

duplicateT :: Traversable t => t (LZipper a) -> LZipper (t (LZipper a)) 
duplicateT z = LZipper (Backwards $ unfoldr (step bwd) z) z (unfoldr (step fwd) z) 
    -- Everything's the exact same except for that extra traverse 
    where step move = fmap (\y -> (y, y)) . (traverse move)

अब हम अपने Comonad उदाहरण में duplicate को पुनर्परिभाषित होने के लिए द्वारा एक अधिक सामान्य duplicateT हम कुछ बुरा कोड दोहराव से छुटकारा पा सकते है:

-- requires import Data.Functor.Identity 
duplicate = fmap runIdentity (duplicate' (Identity z))

तो निम्नलिखित आप हो जाता है कि आप क्या चाहते हैं

duplicateGrid = duplicate . duplicateT

या यदि आप कॉलम और पंक्तियों के क्रम को स्विच करना चाहते हैं, तो आप विपरीत कर सकते हैं।

नोट: यह भी अच्छा हो सकता है अगर हास्केल आप मूल रूप से typeclasses पर प्रकार की कमी को परिभाषित ताकि आप Comonad की अलग-अलग विविधताएं सकता है आपके LZipper कि आपके duplicate की दिशा बदलने के लिए (सभी newtype शायद एस के साथ मध्यस्थता) करते हैं। समस्या यह है कि आप instance Comonad LZipper (LZipper a) where ... या समकक्ष newtype जैसे कुछ चाहते हैं जिसे आप बस हास्केल में नहीं लिख सकते हैं। आप this जैसे कुछ परिवारों के साथ कल्पना कर सकते हैं, लेकिन मुझे संदेह है कि यह शायद इस विशेष उदाहरण के लिए अधिक है।

संपादित: वास्तव में तुम भी duplicateT की जरूरत नहीं है अगर आप LZipper के लिए उपयुक्त Applicative उदाहरण देते हैं।

instance Applicative LZipper where 
    pure x = LZipper (Backwards (repeat x)) x (repeat x) 
    (LZipper leftF f rightF) <*> (LZipper left x right) = LZipper newLeft (f x) newRight 
     where 
     newLeft = (Backwards (zipWith ($) (forwards leftF) (forwards left))) 
     newRight = (zipWith ($) rightF right)

अब बस मूल duplicate आप पहले था लेने के लिए और traverse का उपयोग करें।

duplicateGrid = duplicate . (traverse duplicate)

स्रोत

2016-03-06 20:34:47 badcook

संबंधित मुद्दे

 संबंधित मुद्दे