👨‍✈️ ✍🏾 😲 सेलुलर ऑटोमेटा का उपयोग कोमनाड 👨‍🏭 〰️ 💅🏼

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

life_anim

जगत

Universe

डेटा प्रकार पर विचार करें:

 data Universe a = Universe [a] a [a]

यह दोनों पक्षों की एक अंतहीन सूची है, लेकिन एक तत्व पर ध्यान देने के साथ जिसे हम फ़ंक्शन का उपयोग करके स्थानांतरित कर सकते हैं:

 left, right :: Universe a -> Universe a left (Universe (a:as) x bs) = Universe as a (x:bs) right (Universe as x (b:bs)) = Universe (x:as) b bs

संक्षेप में, यह एक ज़िप प्रकार है, लेकिन हम इसे अनंत स्मृति क्षेत्र के लिए एक निरंतर सी-पॉइंटर के रूप में मान सकते हैं: वेतन वृद्धि और क्षरण संचालन इसके लिए लागू होते हैं। लेकिन इसे कैसे रोकें? ऐसा करने के लिए, हम एक फ़ंक्शन को परिभाषित करते हैं जो एक केंद्रित मूल्य निकालता है:

 extract :: Universe a -> a extract (Universe _ x _) = x

उदाहरण के लिए, Universe [-1, -2..] 0 [1, 2..]

सभी पूर्णांक हैं। हालांकि, Universe [0, -1..] 1 [2, 3..]

एक ही पूर्णांक हैं, लेकिन थोड़े बदले हुए संदर्भ (हम दूसरे तत्व की ओर इशारा करते हैं) के साथ।

integres_figure

यदि हम सभी डिग्री 2 प्राप्त करना चाहते हैं, तो हमें पूर्णांक के Universe

फ़ंक्शन (2**)

को लागू करने का एक तरीका चाहिए। सभी कानूनों का पालन करने वाले फ़ंक्टर वर्ग के उदाहरण को परिभाषित करना काफी आसान है:

 instance Functor Universe where fmap f (Universe as x bs) = Universe (fmap f as) (fx) (fmap f bs) --  powersOf2 = fmap (2**) (Universe [-1, -2..] 0 [1, 2..]) -- ..0.25, 0.5, 1, 2, 4..

एक सेल्यूलर ऑटोमेटन में, कोशिकाओं के मान पिछले चरण में अन्य सभी कोशिकाओं के मूल्यों पर निर्भर करते हैं। इसलिए, हम सभी शिफ्टों के Universe

और उनके दृढ़ीकरण के लिए नियम बना सकते हैं:

 duplicate :: Universe a -> Universe (Universe a) duplicate u = Universe (tail $ iterate left u) u (tail $ iterate right u)

कनविक्शन रूल Universe a -> a

का होना चाहिए Universe a -> a

, इसलिए Universe Bool

लिए, एक नियम का एक उदाहरण होगा:

 rule :: Universe Bool -> Bool rule u = lx /= cx where lx = extract $ left u cx = extract u

सभी शिफ्टों के यूनिवर्स के लिए नियम को लागू करते हुए, हम ऑटोमेटन की निम्नलिखित स्थिति प्राप्त करते हैं:

 next :: Universe a -> (Universe a -> a) -> Universe a next ur = fmap r (duplicate u) --  un = Universe (repeat False) True (repeat False) `next` rule

comonad

हम देख सकते हैं कि हमारे कार्य निम्नलिखित कानूनों का पालन करते हैं:

 extract . duplicate = id fmap extract . duplicate = id duplicate . duplicate = fmap duplicate . duplicate

इसलिए, Universe

एक कोमोनड बनाता है, और next

फ़ंक्शन ऑपरेटर (=>>)

मेल खाता है । कोमोनडा मोनड का एक दोहराव है, जिसके संबंध में कोई भी अपने कार्यों के बीच कुछ उपमाओं का पता लगा सकता है। उदाहरण के लिए, सम्मिलित हों नेस्टेड संदर्भों को जोड़ते हैं, जबकि duplicate

, इसके विपरीत, संदर्भ को दोगुना करता है; return

एक संदर्भ में डालता है, और extract

- इससे अर्क, आदि।

comonad_laws

दो आयामी सेलुलर automaton

अब, हम सिर्फ दो-आयामी सेलुलर ऑटोमेटन को लागू कर सकते हैं। सबसे पहले, दो प्रकार के Universe

की घोषणा करें:

 newtype Universe2 a = Universe2 { getUniverse2 :: Universe (Universe a) }

हास्केल में, fmap

रचना का उपयोग करके नेस्टेड कंटेनरों में एक फ़ंक्शन लागू करना बहुत आसान है, इसलिए Universe2

लिए Functor

वर्ग का एक उदाहरण लिखना एक समस्या नहीं होगी:

 instance Functor Universe2 where fmap f = Universe2 . (fmap . fmap) f . getUniverse2

कोमोनॉड इंस्टेंसेस को नियमित यूनिवर्स की तरह ही किया जाता है, और चूंकि यूनिवर्स 2 सिर्फ एक आवरण है, इसलिए हम मौजूदा तरीकों के संदर्भ में तरीकों को परिभाषित कर सकते हैं। उदाहरण के लिए, extract

लिए दो बार निष्पादित करना काफी सरल है। हालांकि, duplicate

में, हमें नेस्टेड संदर्भों की शिफ्ट प्राप्त करने की आवश्यकता होती है, जिसके लिए एक सहायक फ़ंक्शन परिभाषित होता है

 instance Comonad Universe2 where extract = extract . extract . getUniverse2 duplicate = fmap Universe2 . Universe2 . shifted . shifted . getUniverse2 where shifted :: Universe (Universe a) -> Universe (Universe (Universe a)) shifted u = Universe (tail $ iterate (fmap left) u) u (tail $ iterate (fmap right) u)

यह लगभग सभी है! यह केवल नियम निर्धारित करने और (=>>)

का उपयोग करके इसे लागू करने के लिए बनी हुई है। गेम ऑफ लाइफ में, सेल की नई स्थिति पड़ोसी कोशिकाओं की स्थिति पर निर्भर करती है, इसलिए हम उनके स्थान के कार्य को परिभाषित करते हैं:

 nearest3 :: Universe a -> [a] nearest3 u = fmap extract [left u, u, right u] neighbours :: (Universe2 a) -> [a] neighbours u = [ nearest3 . extract . left , pure . extract . left . extract , pure . extract . right . extract , nearest3 . extract . right ] >>= ($ getUniverse2 u)

और यहाँ नियम ही है:

 data Cell = Dead | Alive deriving (Eq, Show) rule :: Universe2 Cell -> Cell rule u | nc == 2 = extract u | nc == 3 = Alive | otherwise = Dead where nc = length $ filter (==Alive) (neighbours u)

केवल एक उबाऊ निष्कर्ष बचता है, जिसे मैं अलग से नहीं मानूंगा।

निष्कर्ष

इस प्रकार, हम किसी भी सेलुलर ऑटोमेटोन को केवल एक rule

फ़ंक्शन को परिभाषित करके लागू कर सकते हैं। हमें उपहार के रूप में एक अनंत क्षेत्र मिलता है, आलसी गणनाओं के लिए धन्यवाद, हालांकि यह रैखिक स्मृति की खपत जैसी समस्या पैदा करता है।

तथ्य यह है कि चूंकि हम एक अनंत सूची के प्रत्येक तत्व पर नियम लागू करते हैं, उन कोशिकाओं की गणना करने के लिए जो अभी तक एक्सेस नहीं किए गए हैं, सभी पिछले चरणों से गुजरना आवश्यक होगा, जिसका अर्थ है कि उन्हें स्मृति में संग्रहीत किया जाना चाहिए।

दोनों फ़ाइलों के स्रोत कोड:

Universe.hs

 module Universe where import Control.Comonad data Universe a = Universe [a] a [a] newtype Universe2 a = Universe2 { getUniverse2 :: Universe (Universe a) } left :: Universe a -> Universe a left (Universe (a:as) x bs) = Universe as a (x:bs) right :: Universe a -> Universe a right (Universe as x (b:bs)) = Universe (x:as) b bs makeUniverse fl fr x = Universe (tail $ iterate fl x) x (tail $ iterate fr x) instance Functor Universe where fmap f (Universe as x bs) = Universe (fmap f as) (fx) (fmap f bs) instance Comonad Universe where duplicate = makeUniverse left right extract (Universe _ x _) = x takeRange :: (Int, Int) -> Universe a -> [a] takeRange (a, b) u = take (b-a+1) x where Universe _ _ x | a < 0 = iterate left u !! (-a+1) | otherwise = iterate right u !! (a-1) instance Functor Universe2 where fmap f = Universe2 . (fmap . fmap) f . getUniverse2 instance Comonad Universe2 where extract = extract . extract . getUniverse2 duplicate = fmap Universe2 . Universe2 . shifted . shifted . getUniverse2 where shifted :: Universe (Universe a) -> Universe (Universe (Universe a)) shifted = makeUniverse (fmap left) (fmap right) takeRange2 :: (Int, Int) -> (Int, Int) -> Universe2 a -> [[a]] takeRange2 (x0, y0) (x1, y1) = takeRange (y0, y1) . fmap (takeRange (x0, x1)) . getUniverse2

Life.hs

 import Control.Comonad import Control.Applicative import System.Process (rawSystem) import Universe data Cell = Dead | Alive deriving (Eq, Show) nearest3 :: Universe a -> [a] nearest3 u = fmap extract [left u, u, right u] neighbours :: (Universe2 a) -> [a] neighbours u = [ nearest3 . extract . left , pure . extract . left . extract , pure . extract . right . extract , nearest3 . extract . right ] >>= ($ getUniverse2 u) rule :: Universe2 Cell -> Cell rule u | nc == 2 = extract u | nc == 3 = Alive | otherwise = Dead where nc = length $ filter (==Alive) (neighbours u) renderLife :: Universe2 Cell -> String renderLife = unlines . map concat . map (map renderCell) . takeRange2 (-7, -7) (20, 20) where renderCell Alive = "██" renderCell Dead = " " fromList :: a -> [a] -> Universe a fromList d (x:xs) = Universe (repeat d) x (xs ++ repeat d) fromList2 :: a -> [[a]] -> Universe2 a fromList2 d = Universe2 . fromList ud . fmap (fromList d) where ud = Universe (repeat d) d (repeat d) cells = [ [ Dead, Alive, Dead] , [Alive, Dead, Dead] , [Alive, Alive, Alive] ] main = do gameLoop $ fromList2 Dead cells gameLoop :: Universe2 Cell -> IO a gameLoop u = do getLine rawSystem "clear" [] putStr $ renderLife u gameLoop (u =>> rule)

इस लेख के साथ मदद करने के लिए int_index का धन्यवाद।

सेलुलर ऑटोमेटा का उपयोग कोमनाड

जगत

comonad

दो आयामी सेलुलर automaton

निष्कर्ष

More articles: