अंतर सूची क्यों फोल्ड करने योग्य नहीं है?

Question

dlist package में DList डेटा प्रकार है, जिसमें बहुत से उदाहरण हैं, लेकिन Foldable या Traversable नहीं हैं। मेरे दिमाग में, ये सबसे अधिक "सूची-जैसी" प्रकार कक्षाएं हैं। क्या कोई प्रदर्शन कारण है कि DList इन कक्षाओं का उदाहरण नहीं है?

इसके अलावा, पैकेज foldr और unfoldr लागू करता है, लेकिन अन्य फ़ोल्डिंग फ़ंक्शंस में से कोई भी नहीं।

Answer 1

DList a एक newtype आवरण के आसपास [a] -> [a] है, जो एक contravariant स्थिति में एक a है, तो यह Foldable या Traversable, या यहाँ तक Functor सीधे लागू नहीं कर सकते। उन्हें लागू करने का एकमात्र तरीका नियमित सूचियों में और से परिवर्तित करना है (foldr कार्यान्वयन देखें), जो अंतर सूचियों के प्रदर्शन लाभ को हरा देता है।

Answer 2

चर्च-एन्कोडेड सूचियों का उपयोग करने के लिए आपको DList के बजाय एक विकल्प पर विचार करना चाहिए। विचार यह है कि आप एक सूची को एक अपारदर्शी मान के रूप में दर्शाते हैं जो जानता है कि सूची में foldr निष्पादित करने के तरीके को कैसे। यह RankNTypes एक्सटेंशन का उपयोग कर की आवश्यकता है:

{-# LANGUAGE RankNTypes #-} 

import Prelude 
import Control.Applicative 
import Data.Foldable (Foldable) 
import qualified Data.Foldable as F 
import Data.Traversable (Traversable) 
import qualified Data.Traversable as T 

-- | Laws: 
-- 
-- > runList xs cons nil == xs 
-- > runList (fromList xs) f z == foldr f z xs 
-- > foldr f z (toList xs) == runList xs f z 
newtype ChurchList a = 
    ChurchList { runList :: forall r. (a -> r -> r) -> r -> r } 

-- | Make a 'ChurchList' out of a regular list. 
fromList :: [a] -> ChurchList a 
fromList xs = ChurchList $ \k z -> foldr k z xs 

-- | Turn a 'ChurchList' into a regular list. 
toList :: ChurchList a -> [a] 
toList xs = runList xs (:) [] 

-- | We can construct an empty 'ChurchList' without using a @[]@. 
nil :: ChurchList a 
nil = ChurchList $ \_ z -> z 

-- | The 'ChurchList' counterpart to '(:)'. Unlike 'DList', whose 
-- implementation uses the regular list type, 'ChurchList' doesn't 
-- rely on it at all. 
cons :: a -> ChurchList a -> ChurchList a 
cons x xs = ChurchList $ \k z -> k x (runList xs k z) 

-- | Append two 'ChurchList's. This runs in O(1) time. Note that 
-- there is no need to materialize the lists as @[a]@. 
append :: ChurchList a -> ChurchList a -> ChurchList a 
append xs ys = ChurchList $ \k z -> runList xs k (runList ys k z) 

-- | Map over a 'ChurchList'. No need to materialize the list. 
instance Functor ChurchList where 
    fmap f xs = ChurchList $ \k z -> runList xs (\x xs' -> k (f x) xs') z 

-- | The 'Foldable' instance is trivial, given the 'ChurchList' law. 
instance Foldable ChurchList where 
    foldr f z xs = runList xs f z 

instance Traversable ChurchList where 
    traverse f xs = runList xs step (pure nil) 
     where step x rest = cons <$> f x <*> rest 

इस के लिए नकारात्मक पक्ष यह एक ChurchList -folding एक ChurchList सस्ती है के लिए कोई कुशल tail आपरेशन वहाँ है, लेकिन बार-बार पूंछ लेने महंगा है कि है ...

इसके अलावा