जॉन ह्यूजेस के 'फ़ोल्ड्री' के बारे में क्या मैं गलतफहमी कर रहा हूं?

Question

जॉन ह्यूजेस, अपने प्रसिद्ध Why Functional Programming Matters हकदार लेख में, डेटा प्रकार सूचियों और आदेश दिया लेबल पेड़ के लिए, का वर्णन करता है

listof * ::= Nil | Cons * (listof *) 
treeof * ::= Node * (listof (treeof *)) 

और एक समारोह foldtree कहा जाता है,

foldtree f g a (Node label subtrees) = 
     f label (foldtree f g a subtrees) 

foldtree f g a (Cons subtree rest) = 
     g (foldtree f g a subtree) (foldtree f g a rest) 

foldtree f g a Nil = a 

मैंने उन दो डेटा टाइप को लागू किया है हास्केल में तों और मैं वर्तमान में foldtree लागू करने के लिए,

data Listof a = Nil | Cons a (Listof a) 
    deriving (Read, Show, Eq) 

-- implementation of some list functions... (skipped) 

data Treeof a = Node a (Listof (Treeof a)) 
    deriving (Read, Show, Eq) 

foldtree f g a (Node label subtrees) = f label (foldtree f g a subtrees) 
foldtree f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldtree f g a rest) 
foldtree f g a Nil     = a 

कोशिश कर रहा हूँ, लेकिन मैं प्रकार बेमेल हो रही है: (

Couldn't match expected type ‘Treeof t’ 
      with actual type ‘Listof (Treeof t)’ 
Relevant bindings include 
    subtrees :: Listof (Treeof t) (bound at whyFunMatters.hs:27:28) 
    label :: t (bound at whyFunMatters.hs:27:22) 
    f :: t -> t1 -> t1 (bound at whyFunMatters.hs:27:10) 
    foldtree :: (t -> t1 -> t1) 
       -> (t1 -> t1 -> t1) -> t1 -> Treeof t -> t1 
    (bound at whyFunMatters.hs:27:1) 
In the fourth argument of ‘foldtree’, namely ‘subtrees’ 
In the second argument of ‘f’, namely ‘(foldtree f g a subtrees)’ 

(आदि)

ह्यूजेस बारे में कुछ और सोच के बाद छद्म) foldtree का कार्यान्वयन, मुझे यकीन नहीं है कि मैं इसे समझता हूं, और उन प्रकार के विसंगतियां अब मेरे लिए स्पष्ट प्रतीत होती हैं। विशेष रूप से, foldtree के चौथे तर्क के प्रकार के तीन पैटर्न पर एक जैसी प्रतीत नहीं होता:

पहले पैटर्न में
• , कि तर्क टाइप Treeof a है, जबकि
• पिछले दो पैटर्न में, यह है Listof (Treeof a) टाइप करें।

मुझे क्या याद आ रही है?

foldtree :: (a -> c -> b) -> (b -> c -> c) -> c -> Treeof a -> b 
foldtree f g a (Node label subtrees) = f label (foldforest f g a subtrees) 

foldforest :: (a -> c -> b) -> (b -> c -> c) -> c -> Listof (Treeof a) -> c 
foldforest f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldforest f g a rest) 
foldforest f g a Nil     = a 

मुझे लगता है कि लेखक को गलती से संयुक्त है:

Answer 1

एक उचित परिभाषा तह जंगलों (पेड़ों की सूची) के लिए पेड़ और एक तह के लिए पारस्परिक रूप से पुनरावर्ती काम करता है, एक की एक जोड़ी से मिलकर चाहिए एक साथ दो अलग (लेकिन बारीकी से संबंधित) कार्यों। मुझे संदेह है कि लेखक ने लिखा है कि वास्तव में हास्केल नहीं है, लेकिन एक हास्केल की तरह छद्म कोड है, इसलिए कोड को अनौपचारिक तरीके से एल्गोरिदम प्रस्तुत करने के लिए उपयोग किया गया था।

ध्यान दें कि पेपर का सुझाव है कि यह हास्केल के पूर्ववर्ती मिरांडा का सुझाव है, लेकिन मैं पुष्टि नहीं कर सकता कि यह कानूनी मिरांडा कोड है या नहीं।

Answer 2

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

foldforest की Rufflewind की परिभाषा की तुलना करें:

foldforest f g a (Cons subtree rest) = g (foldtree f g a subtree) (foldforest f g a rest) 
foldforest f g a Nil     = a 

...ह्यूजेस 'के साथ कागज से foldr की परिभाषा (हल्के से बदल):

foldr f a (Cons e rest)    = f e (foldr f a rest) 
foldr f a Nil      = a 

मत करो वे दोनों बहुत समान लग रहा है? वास्तव में केवल अंतर यह है कि foldforest में हम foldtree f g asubtree और (रिकर्सन के माध्यम से) g के साथ "विलय" करने से पहले उपट्री की सूची में अन्य सभी तत्वों को लागू करते हैं। क्या हम एक ऑपरेटर को परिभाषित कर सकते हैं जो ऐसा करता है और foldr पर पारित किया जा सकता है?

चलिए foldforest के मूल पर नज़र डालें जहां वास्तविक कार्य किया जाता है: g (foldtree f g a subtree)। समारोह संरचना ((f . g) h = f (g h) के रूप में ह्यूजेस 'समाचार पत्र में परिभाषित) का उपयोग करते हुए हम अलग ढंग से इस हिस्से को व्यक्त कर सकते हैं:

foldforest f g a (Cons subtree rest) = (g . foldtree f g a) subtree (foldforest f g a rest) 

अब की संक्षिप्तता के लिए h = (g . foldtree f g a) को परिभाषित करने और foldforest हमारे नए अंकन का उपयोग प्रत्यावर्तन खुलासा करने के लिए subtrees की एक ठोस सूची पारित:

foldforest f g a (Cons subtree1 (Cons subtree2 Nil)) 
            = h subtree1 (h subtree2 a) 

foldr पर इसी तरह के कॉल के रिकर्सन को प्रकट करने की तरह कैसा लगता है?

foldr f a (Cons subtree1 (Cons subtree2 Nil)) 
            = f subtree1 (f subtree2 a) 

अब यह स्पष्ट है कि हम foldforest से एक ऑपरेटर को निकालने के लिए जो हम एक शुरू करने राज्य a और Treeof रों की एक सूची के साथ foldr को पारित कर सकते हैं सक्षम थे है। foldtree की पूरी परिभाषा, प्रतिरूपकता और संक्षिप्तता को अधिकतम, की वजह से किया जाना चाहिए:

foldtree f g a (Node label subtrees) = f label (foldr (g . foldtree f g a) a subtrees)