Haskell Language
पुनरावर्तन योजनाएँ

टिप्पणियों

निश्चित अंक

Fix एक "टेम्पलेट" प्रकार लेता है और पुनरावर्ती गाँठ को बांधता है, टेम्पलेट को लेसेगैन की तरह लेटाता है।

newtype Fix f = Fix { unFix :: f (Fix f) }

एक Fix f अंदर हम टेम्पलेट f की एक परत पाते हैं। f के पैरामीटर को भरने के लिए, अपने आप में Fix f प्लग को Fix f । इसलिए जब आप टेम्पलेट f अंदर देखते हैं तो आपको Fix f की पुनरावर्ती घटना का पता चलता है।

यहाँ बताया गया है कि कैसे एक विशिष्ट पुनरावर्ती डेटाटाइप को टेम्प्लेट और निश्चित बिंदुओं के हमारे ढांचे में अनुवाद किया जा सकता है। हम प्रकार के पुनरावर्ती घटनाओं को हटाते हैं और r पैरामीटर का उपयोग करके उनकी स्थिति को चिह्नित करते हैं।

{-# LANGUAGE DeriveFunctor #-}

-- natural numbers
-- data Nat = Zero | Suc Nat
data NatF r = Zero_ | Suc_ r deriving Functor
type Nat = Fix NatF

zero :: Nat
zero = Fix Zero_
suc :: Nat -> Nat
suc n = Fix (Suc_ n)


-- lists: note the additional type parameter a
-- data List a = Nil | Cons a (List a)
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

nil :: List a
nil = Fix Nil_
cons :: a -> List a -> List a
cons x xs = Fix (Cons_ x xs)


-- binary trees: note two recursive occurrences
-- data Tree a = Leaf | Node (Tree a) a (Tree a)
data TreeF a r = Leaf_ | Node_ r a r deriving Functor
type Tree a = Fix (TreeF a)

leaf :: Tree a
leaf = Fix Leaf_
node :: Tree a -> a -> Tree a -> Tree a
node l x r = Fix (Node_ l x r)

एक समय में एक परत एक संरचना को मोड़ना

कायापलट , या सिलवटों , मॉडल आदिम पुनरावृत्ति। cata परत से एक fixpoint परत नीचे आँसू, एक बीजगणित समारोह (समारोह या तह) का उपयोग कर प्रत्येक परत पर कार्रवाई करने के। cata को टेम्प्लेट टाइप f लिए Functor इंस्टेंस की आवश्यकता होती है।

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

-- list example
foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z = cata alg
    where alg Nil_ = z
          alg (Cons_ x acc) = f x acc

एक समय में एक परत एक संरचना को खोलना

Anamorphisms, या करेंगी, मॉडल आदिम corecursion। ana प्रत्येक नई परत का उत्पादन करने के लिए एक कोलजब्रा फ़ंक्शन (या अनफॉलोिंग फ़ंक्शन ) का उपयोग करके परत द्वारा एक फिक्स पॉइंट परत बनाता है। ana को टेम्पलेट प्रकार f लिए एक Functor इंस्टेंस की आवश्यकता होती है।

ana :: Functor f => (a -> f a) -> a -> Fix f
ana f = Fix . fmap (ana f) . f

-- list example
unfoldr :: (b -> Maybe (a, b)) -> b -> List a
unfoldr f = ana coalg
    where coalg x = case f x of
                         Nothing -> Nil_
                         Just (x, y) -> Cons_ x y

ध्यान दें कि ana और cata दोहरे हैं । प्रकार और कार्यान्वयन एक दूसरे के दर्पण चित्र हैं।

अनफॉलो करना और फिर फोल्ड करना, फ्यूज्ड

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

hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f  -- no mention of Fix!

व्युत्पत्ति:

hylo f g = cata g . ana f
         = g . fmap (cata g) . unFix . Fix . fmap (ana f) . f  -- definition of cata and ana
         = g . fmap (cata g) . fmap (ana f) . f  -- unfix . Fix = id
         = g . fmap (cata g . ana f) . f  -- Functor law
         = g . fmap (hylo f g) . f  -- definition of hylo

आदिम पुनरावृत्ति

पैराओमफ़िज़म आदिम पुनरावर्तन मॉडल। तह के प्रत्येक पुनरावृत्ति पर, तह फ़ंक्शन आगे की प्रक्रिया के लिए सबट्री प्राप्त करता है।

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix

प्रेल्यूड्स की tails को एक प्रतिमान के रूप में चित्रित किया जा सकता है।

tails :: List a -> List (List a)
tails = para alg
    where alg Nil_ = cons nil nil  -- [[]]
          alg (Cons_ x (xs, xss)) = cons (cons x xs) xss  -- (x:xs):xss

आदिम शव

एपोमोर्फ़िज्म आदिम corecursion मॉडल। अनफॉल्ड के प्रत्येक पुनरावृत्ति पर, एक्सफोल्डिंग फ़ंक्शन या तो एक नया बीज या पूरे उपट्री वापस कर सकता है।

apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f

ध्यान दें कि apo और para दोहरे हैं । प्रकार में तीर फ़्लिप हैं; para में ट्यूपल apo में apo Either दोहरी है, और कार्यान्वयन एक दूसरे के दर्पण चित्र हैं।