चर्च एन्कोडेड सूची की अधिक कुशल पूंछ

Question

यह एक साक्षर हैकेल पोस्ट है। इसे चलाने के लिए बस इसे "ChurchList.lhs" के रूप में सहेजें।

> {-# LANGUAGE Rank2Types #-} 

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

> newtype ChurchList a = CList {runCList :: forall r. (a -> r -> r) -> r -> r} 

उदाहरण के लिए के रूप में यह कैसे एक सूची से मेल खाती है करने के लिए, यहाँ एक हे (एन) समाकृतिकता

> fromList :: [a] -> ChurchList a 
> fromList xs = CList $ \cons empty -> foldr cons empty xs 

> toList :: ChurchList a -> [a] 
> toList cl = runCList cl (:) [] 

> instance Show a => Show (ChurchList a) where 
> show cl = "fromList " ++ show (toList cl) 

ये बातें अच्छे प्रदर्शन charecteristics है।

> singleton :: a -> ChurchList a -- O(1) 
> singleton a = CList $ \cons empty -> a `cons` empty 
> append :: ChurchList a -> ChurchList a -> ChurchList a -- O(1)!!! This also means cons and snoc are O(1) 
> append cl1 cl2 = CList $ \cons empty -> runCList cl1 cons (runCList cl2 cons empty) 
> concatCl :: ChurchList (ChurchList a) -> ChurchList a -- O(n) 
> concatCl clcl = CList $ \cons empty -> runCList clcl (\cl r -> runCList cl cons r) empty 
> headCl :: ChurchList a -> Maybe a -- O(1) 
> headCl cl = runCList cl (\a _ -> Just a) Nothing 

अब समस्या tail के साथ आता है।

> tailClbad :: ChurchList a -> Maybe (ChurchList a) --O(n)?!! 
> tailClbad cl = (fmap snd) $ runCList cl 
> 
> (\a r -> Just (a, case r of 
> Nothing -> CList $ \cons empty -> empty 
> Just (s,t) -> append (singleton s) t)) --Cons 
> 
> Nothing --Empty 

अनिवार्य रूप से मेरा कार्यान्वयन क्या करता है सूची को सिर और पूंछ में विभाजित करता है। विपक्ष सिर की जगह लेता है, और पुराने सिर को पूंछ में जोड़ता है। यह बल्कि अक्षम है। ऐसा लगता है कि चर्च सूची सामान्य रूप से विभाजित होने में अक्षम हैं।

मुझे उम्मीद है कि मैं गलत हूं। क्या tailCl का कार्यान्वयन है जो ओ (एन) से बेहतर है (अधिमानतः ओ (1))।

Answer 1

हाँ, यह ओ (एन) है। एक चर्च एन्कोडेड सूची को उसके फ़ोल्डर फ़ंक्शन के साथ पहचाना जाता है, जो हर जगह एक ही चीज़ करना चाहिए। चूंकि पूंछ को पहले आइटम के लिए कुछ करने की आवश्यकता होती है, वही कुछ शेष वस्तुओं के लिए कुछ भी किया जाना चाहिए।

{-# LANGUAGE RankNTypes #-} 

newtype ChurchList a = CList { getFoldr :: forall r. (a -> r -> r) -> r -> r } 

fromList :: [a] -> ChurchList a 
fromList xs = CList $ \f z -> foldr f z xs 

toList :: ChurchList a -> [a] 
toList cl = getFoldr cl ((:)) [] 

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

safeTail :: [a] -> Maybe [a] 
safeTail []  = Nothing 
safeTail (_:xs) = Just xs 

tailCtrivial :: ChurchList a -> Maybe (ChurchList a) 
tailCtrivial = fmap fromList . safeTail . toList 

Answer 2

कागज Church Encoding of Data Types Considered Harmful for Implementations Koopman, Plasmeijer और जेंसन द्वारा विस्तार से मुद्दे से निपटने के लिए लगता है। विशेष रूप से, (मेरे जोर) सार उद्धृत:

[...]

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

हालांकि, Scott encoding प्रदर्शन लाभ प्रदान करता है, जबकि, यह problematic होने की पुनरावर्ती प्रकार जोड़ने के बिना प्रणाली एफ में परिभाषित प्रतीत होता है।

Answer 3

नहीं, जरूरी हे (एन):

प्रस्तावना> ले 5। एसएनडी foldr (\ एक R-> (क: FST आर, FST र)) ([], अपरिभाषित) $ [1 ..]
[2,3,4,5,6]

यह वास्तव में प्रत्येक तत्व अंततः उत्पादित के लिए ओ (1) ओवरहेड जोड़ता है।

safetail के लिए कोशिश कर रहा है काम नहीं किया:

प्रस्तावना> FMAP (ले 5)। एसएनडी फ़ोल्डर (\ a r-> (fmap (a :) $ fst r, fst r)) (बस [], कुछ भी नहीं)
$ [1 ..]
बाधित।

तो,

tailCL cl = CList $ \k z-> snd $ runCList cl (\a r-> (a`k`fst r,fst r)) (z, undefined) 

प्रस्तावना> 5 ले। सूची बनाने के लिए । tailCL fromList $ [1 ..]
[2,3,4,5,6]

---

संपादित करें:@user3237465 द्वारा टिप्पणी followng, यह पता चला है कि safetail सब के बाद संभव है :

प्रस्तावना> fmap (5 ले ​​लो)। एसएनडी फ़ोल्डर (\ a ~ (आर, _) -> (बस (ए: से जस्ट आर), आर)) (बस [] , कुछ नहीं) $ [1 ..]
बस [2,3,4,5, 6]

कारण यह पहले काम नहीं किया है कि Maybe के fmap बलों इसकी दूसरा तर्क पता लगाने के लिए जो मामले में यह है, लेकिन यहाँ हम है कि यह एक Just मूल्य है, निर्माण से पता है। मैं इसे आपके प्रकार की परिभाषा के रूप में नहीं रख सकता था, हालांकि मैंने जो भी कोशिश की वह टाइप चेकर पास नहीं कर सका।