सूची को शायद हास्केल में परिभाषित किया गया है? क्यों नहीं?

Question

आप offen Maybe List उदाहरण के लिए त्रुटि हैंडलिंग के अलावा देख पा रहे हैं, क्योंकि सूचियों थोड़ा Maybe खुद को कर रहे हैं: [] और अपने स्वयं के "Just": (:) वे अपने स्वयं के "Nothing" है। मैंने मानक का उपयोग करके और "प्रयोगात्मक" सूचियों को बदलने के लिए शायद और सूची का उपयोग करके एक सूची प्रकार लिखा था। ।

data List a = List a (Maybe (List a)) 
    deriving (Eq, Show, Read) 

toExp [] = Nothing 
toExp (x:xs) = Just (List x (toExp xs)) 

toStd Nothing = [] 
toStd (Just (List x xs)) = x : (toStd xs) 

पुनरावृत्ति को कम करने के प्रयास के रूप में, आप इसे सामान्य करने के लिए क्या सोचते हैं?

पेड़ भी इन सूचियों का उपयोग में परिभाषित किया जा सकता है:

type Tree a = List (Tree a, Tree a) 

मैं, हालांकि कोड के इस अंतिम टुकड़ा परीक्षण नहीं किया।

Answer 1

सभी ADTS isomorphic (लगभग - अंत देखें) (,), Either, (), (->), Void और Mu के कुछ संयोजन के लिए जहां

data Void --using empty data decls or 
newtype Void = Void Void 

और Mu एक functor की fixpoint गणना करता

newtype Mu f = Mu (f (Mu f)) 

उदाहरण के लिए

data [a] = [] | (a:[a]) 

रूप

data [a] = Mu (ListF a) 
data ListF a f = End | Pair a f 

ही है जो अपने आप में

data Maybe a = Nothing | Just a 

के बाद से

newtype ListF a f = ListF (Either() (a,f)) 

isomorphic को है

newtype Maybe a = Maybe (Either() a) 

isomorphic को है

आप

newtype ListF a f = ListF (Maybe (a,f)) 

जो

data List a = List (Maybe (a,List a)) 

और अपनी परिभाषा के म्यू में inlined जा सकती है

data List a = List a (Maybe (List a)) 

सिर्फ म्यू का खुलासा और बाहरी के उन्मूलन है हो सकता है कि (गैर-खाली सूचियों के अनुरूप)

और आप कर रहे हैं ...

बातें

1. कस्टम ADTS का उपयोग की एक जोड़ी बढ़ जाती है स्पष्टता और प्रकार सुरक्षा

2. यह सार्वभौमिकता उपयोगी है: देखने GHC.Generic

---

ठीक है, मैं लगभग isomorphic कहा। यह बिल्कुल नहीं है, अर्थात्

hmm = List (Just undefined) 

सूचियों का [a] = [] | (a:[a]) परिभाषा कोई समकक्ष मूल्य है। ऐसा इसलिए है क्योंकि हास्केल डेटा प्रकार coinductive हैं, और a point of criticism of the lazy evaluation model रहा है। आप इन समस्याओं को चारों ओर केवल सख्त रकम और उत्पादों का उपयोग करके प्राप्त कर सकते हैं (और मूल्य कार्यों से कहते हैं), और एक विशेष "लेज़ी" डेटा निर्माता

data SPair a b = SPair !a !b 
data SEither a b = SLeft !a | SRight !b 
data Lazy a = Lazy a --Note, this has no obvious encoding in Pure CBV languages, 
--although Laza a = (() -> a) is semantically correct, 
--it is strictly less efficient than Haskell's CB-Need 

और फिर सभी Isomorphisms ईमानदारी से एन्कोड किया जा सकता जोड़ने।

Answer 2

आप Maybe के संदर्भ में सूचियों को परिभाषित कर सकते हैं, लेकिन ऐसा नहीं करते हैं। आपका List प्रकार खाली नहीं हो सकता है। या [a] के प्रतिस्थापन के लिए आप Maybe (List a) का इरादा रखते थे। यह बुरा लगता है क्योंकि यह सूची और शायद प्रकारों में अंतर नहीं करता है।

यह काम करेगा

newtype List a = List (Maybe (a, List a)) 

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

Answer 3

आप हास्केल में तरीकों के समूह में सूचियों को परिभाषित कर सकते हैं। उदाहरण के लिए, कार्य के रूप में:

{-# LANGUAGE RankNTypes #-} 

newtype List a = List { runList :: forall b. (a -> b -> b) -> b -> b } 

nil :: List a 
nil = List (\_ z -> z) 

cons :: a -> List a -> List a 
cons x xs = List (\f z -> f x (runList xs f z)) 

isNil :: List a -> Bool 
isNil xs = runList xs (\x xs -> False) True 

head :: List a -> a 
head xs = runList xs (\x xs -> x) (error "empty list") 

tail :: List a -> List a 
tail xs | isNil xs = error "empty list" 
tail xs = fst (runList xs go (nil, nil)) 
    where go x (xs, xs') = (xs', cons x xs) 

foldr :: (a -> b -> b) -> b -> List a -> b 
foldr f z xs = runList xs f z 

इस कार्यान्वयन के लिए चाल है कि सूचियों कार्यों कि सूची के तत्वों पर एक गुना पर अमल के रूप में प्रतिनिधित्व किया जा रहा है:

fromNative :: [a] -> List a 
fromNative xs = List (\f z -> foldr f z xs) 

toNative :: List a -> [a] 
toNative xs = runList xs (:) [] 

किसी भी मामले में, क्या वास्तव में मामलों अनुबंध (या कानून) कि प्रकार और उसके संचालन का पालन करते हैं, और प्रदर्शन कार्यान्वयन के प्रदर्शन। असल में, अनुबंध को पूरा करने वाला कोई भी कार्यान्वयन आपको सही कार्यक्रम देगा, और तेजी से कार्यान्वयन आपको तेजी से कार्यक्रम देगा।

सूचियों का अनुबंध क्या है?ठीक है, मैं पूरी तरह से विस्तार से व्यक्त करने के लिए नहीं जा रहा हूँ, लेकिन सूचियों इस तरह के बयान का पालन:

1. head (x:xs) == x
2. tail (x:xs) == xs
3. [] == []
4. [] /= x:xs
5. तो xs == ys और x == y, तो x:xs == y:ys
6. foldr f z [] == z
7. foldr f z (x:xs) == f x (foldr f z xs)

संपादित करें: और यह टाई 'जवाब augustss रहे हैं:

newtype ExpList a = ExpList (Maybe (a, ExpList a)) 

toExpList :: List a -> ExpList a 
toExpList xs = runList xs (\x xs -> ExpList (Just (x, xs))) (ExpList Nothing) 

foldExpList f z (ExpList Nothing) = z 
foldExpList f z (ExpList (Just (head, taill))) = f head (foldExpList f z tail) 

fromExpList :: ExpList a -> List a 
fromExpList xs = List (\f z -> foldExpList f z xs) 

Answer 4

यदि यह एक सूची है, यह Functor का एक उदाहरण है, है ना होना चाहिए?

instance Functor List 
    where fmap f (List a as) = List (f a) (mapMaybeList f as) 

mapMaybeList :: (a -> b) -> Maybe (List a) -> Maybe (List b) 
mapMaybeList f as = fmap (fmap f) as 

यहाँ एक समस्या है: आप Functor की List एक उदाहरण बना सकते हैं, लेकिन अपने शायद सूची नहीं है, भले ही Maybe, आप सीधे एक निर्माण नहीं कर सकते हैं अपने आप में Functor का एक उदाहरण पहले से ही नहीं था किसी भी चीज के उदाहरण में Maybe . List की तरह (आपको एक रैपर प्रकार की आवश्यकता होगी)।

इसी तरह अन्य टाइपक्लास के लिए।

---

कहा करने के बाद कि, अपने निर्माण के साथ आप इस, जो आप मानक हास्केल के साथ ऐसा नहीं कर सकते को सूचीबद्ध कर सकते हैं:

instance Comonad List 
    where extract (List a _) = a 
     duplicate x @ (List _ y) = List x (duplicate y) 

एक हो सकता है कि सूची अभी भी नहीं comonadic हालांकि होगा।

Answer 5

जब मैं पहली बार हास्केल का उपयोग शुरू किया, मैं भी इस आधार पर कि यह अतिरेक से बचने के लिए अच्छा है पर के रूप में ज्यादा के रूप में मैं कर सकता मौजूदा प्रकार में चीजों का प्रतिनिधित्व करने की कोशिश की। मेरी वर्तमान समझ (चलती लक्ष्य!) व्यापार-बंद के बहुआयामी वेब के विचार को और अधिक शामिल करती है। मैं उदाहरणों को चिपकाने और पूछने के लिए यहां कोई भी "उत्तर" नहीं दे रहा हूं, "क्या आप देखते हैं कि मेरा क्या मतलब है?" मुझे उम्मीद है कि यह वैसे भी मदद करता है।

data UseCache = YesUseCache | NoUseCache 
    deriving (Eq) 

data DryRun = YesDryRun | NoDryRun 
    deriving (Eq) 

data Compression = NoCompression 
       | GzipCompression 
    deriving (Eq) 

आप नोटिस किया है कि इन तीन प्रकार सभी Bool की हो सकती थी:

के Darcs कोड का एक सा पर एक नजर है? आपको क्यों लगता है कि डार्क्स हैकर्स ने फैसला किया है कि उन्हें अपने कोड में इस प्रकार की अनावश्यकता पेश करनी चाहिए?

type Slot = Maybe Bool     -- OLD code 
data Slot = InFirst | InMiddle | InLast -- newer code 

तुम्हें क्या लगता है कि हम फैसला किया है कि दूसरा कोड पहले के ऊपर एक सुधार था: एक और उदाहरण के रूप में, यहाँ हम कुछ साल वापस बदल कोड का एक टुकड़ा है?

अंत में, यहाँ मेरा दिन काम सामान में से कुछ से कोड का एक सा है। यह newtype वाक्य रचना कि उल्लेख किया augustss,

newtype Role = Role { fromRole :: Text } 
    deriving (Eq, Ord) 

newtype KmClass = KmClass { fromKmClass :: Text } 
    deriving (Eq, Ord) 

newtype Lemma = Lemma { fromLemma :: Text } 
    deriving (Eq, Ord) 

यहाँ आप ध्यान देंगे कि मैं एक पूरी तरह से अच्छा Text प्रकार लेने और फिर इसे ऊपर लपेटकर तीन अलग अलग चीज़ों के रूप में की उत्सुक बात किया है उपयोग करता है। सादे पुराने Text की तुलना में तीन चीजों में कोई नई विशेषताएं नहीं हैं। वे सिर्फ अलग होने के लिए हैं। ईमानदार होने के लिए, मुझे पूरी तरह से यकीन नहीं है कि ऐसा करने के लिए मेरे लिए एक अच्छा विचार था। मैं अस्थायी रूप से सोचता हूं कि ऐसा इसलिए था क्योंकि मैं कई कारणों से कई अलग-अलग बिट्स और टेक्स्ट के टुकड़ों में हेरफेर करता हूं, लेकिन समय बताएगा।

तुम क्या मैं कम से प्राप्त करने के लिए कोशिश कर रहा हूँ देख सकते हैं?