किसी प्रकार को कैसे लिखना है जो बिना किसी सूचियों के पेड़ के आइसोमोर्फिक है?

Question

हास्केल में, ऐसा कहा जाता है कि किसी भी एडीटी को उत्पादों के योग के रूप में व्यक्त किया जा सकता है। मैं एक फ्लैट प्रकार खोजने की कोशिश कर रहा हूं जो Tree पर Data.Tree पर isomorphic है।

Tree a = Node a [Tree a] -- has a nested type (List!) 

मैं नेस्ट प्रकार के बिना पेड़ के लिए एक कार्यात्मक रूप से समान परिभाषा लिखना चाहते हैं:

Tree = ??? -- no nested types allowed 

कि के लिए, मैं प्रकार अल्जेब्रास के लिए पुनरावर्ती संबंध में लिख करने की कोशिश की:

L a = 1 + a * L a 
T a = a * L (T a) 

इनलाइनिंग एल, मेरे पास था:

T a = a * (1 + T a * L (T a)) 
T a = a * (1 * T a * (1 + T a * L (T a))) 
T a = a * (1 + T a * (1 + T a * (1 + T a * L (T a)))) 

,210

कहीं नहीं जा रहा था कि, तो मैं बंद कर दिया और किया गुणा, मेरे साथ छोड़ रहा है:

T a = a + a * T a + a * T a * T a ... 

कौन सा ही है के रूप में:

T a = a * (T a)^0 + a * (T a)^1 + a * (T a)^2 ... 

उत्पादों की राशि है, लेकिन यह अनंत है मैं इसे हास्केल में नहीं लिख सकता। बीजगणित कोस द्वारा:

(T a) - (T a)^2 = a * T a 
- (T a)^2 - a * T a + (T a) = 0 

T a के लिए हल करने पर मैंने पाया कि:

T a = 1 - a 

कौन सा स्पष्ट रूप से कोई मतलब नहीं है। तो, मूल प्रश्न पर वापस जाएं: Data.Tree से Tree को कैसे फ़्लैट कर सकता हूं ताकि मैं एक प्रकार लिख सकूं जो बिना घोंसले वाले आइसोमोर्फिक है?

यह प्रश्न my previous question का डुप्लिकेट नहीं है। आखिरी वाला स्कॉट एन्कोडिंग के साथ नेस्टेड प्रकारों का प्रतिनिधित्व करने के बारे में है, जिसके लिए सही जवाब "घोंसले को अनदेखा" है। यह पूछने के लिए आगे बढ़ता है कि किसी नेस्टेड प्रकार को कैसे फ़्लैट करना है (क्योंकि स्कॉट एन्कोडिंग के किसी विशेष उपयोग के लिए इसकी आवश्यकता है, लेकिन सामान्य रूप से अनिवार्य नहीं है)।

Answer 1

एक बार जब आप

T a = a * (1 + T a * L (T a)) 

को मिला आप जारी रख सकता

= a + a * T a * L (T a) -- distribute 
    = a + T a * (a * L (T a)) -- commute and reassociate 
    = a + T a * T a   -- using your original definition of T backwards 

ताकि आप

data Tree a = Leaf a | InsertLeftmostSubtree (Tree a) (Tree a) 

पर पहुंचने मुझे यकीन है कि किस हद तक इस एक का एक उदाहरण है नहीं कर रहा हूँ हालांकि, सामान्य प्रक्रिया।

Answer 2

जवाब में से किसी को पढ़ने से पहले, मैंने सोचा कि यह एक मजेदार पहेली था और स्वीकार किए जाते हैं जवाब देने के लिए कुछ बराबर बाहर काम किया:

data Tree' a = Node a [Tree' a] deriving (Show, Eq, Ord) 
data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show, Eq, Ord) 

इसके अलावा, मैं रूपांतरण कार्यों लिखा था, क्या केवल की तरह लगता है में संभव तरीके:

convert :: Tree' a -> Tree a 
convert (Node x [])  = (Leaf x) 
convert (Node x (t:ts)) = Branch (convert t) $ convert (Node x ts) 

convert' :: Tree a -> Tree' a 
convert' (Leaf x)  = Node x [] 
convert' (Branch t ts) = Node x $ convert' t : subtrees 
    where (Node x subtrees) = convert' ts 

इन कार्यों के कार्यान्वयन शुद्धता का प्रमाण नहीं हैं, लेकिन तथ्य यह है कि वे typecheck, कोई गैर संपूर्ण पैटर्न से मेल खाता है, और सरल आदानों के लिए काम करने लगते हैं (यानी convert . convert' == id), मदद करता है कि डेटा टी ypes एक दूसरे के लिए isomorphic हैं, जो प्रोत्साहित कर रहा है।

ऐसी चीज बनाने के तरीके की सामान्य संरचना के लिए, मैं स्वीकार्य उत्तर में टाइप बीजगणित के मुकाबले अलग-अलग आया, इसलिए शायद मेरी विचार प्रक्रिया सामान्य विधि प्राप्त करने में सहायक होगी। मुख्य बात यह थी कि [x] को सामान्य रूप से में परिवर्तित किया जा सकता है। इसलिए, हमें [Tree' a] फ़ील्ड में उस परिवर्तन को लागू करने की आवश्यकता है, जबकि अतिरिक्त a "ऊपर" [Tree' a] को भी संरक्षित करना है। तो, मेरा Leaf a स्वाभाविक रूप से Nil के बराबर है लेकिन अतिरिक्त a के साथ; तो Branch कन्स्ट्रक्टर Cons b (List b) के समान है।

मुझे लगता है कि आप किसी भी डेटा निर्माता के लिए कुछ इसी तरह होता है, जो एक सूची कर सकते हैं: Constructor a b [c] दिया, तो आप इस दो कंस्ट्रक्टर्स के लिए नए प्रकार में परिवर्तित:

data Converted a b c = Nil a b | Cons c (Converted a b c) 

और दो वर्ष में सूचियों देखते हैं अगर

data Old a b c = Old a [b] [c] 

data New a b c = Done a 
       | AddB b (New a b c) 
       | AddC c (New a b c)