से अधिक एक विषम

Question

गुना, समय संकलन, सूची मैं विषम प्रकार की एक सूची है (या कम से कम है कि मैं क्या मन में है है):

data Nul 

data Bits b otherBits where 
    BitsLst :: b -> otherBits -> Bits b otherBits 
    NoMoreBits :: Bits b Nul 

अब, एक इनपुट प्रकार b को देखते हुए, मैं जाना चाहता हूँ प्रकार b साथ और उन्हें संक्षेप में प्रस्तुत, प्रकार b' /= b के साथ अन्य स्लैब अनदेखी Bits के सभी स्लैब के माध्यम से:

class Monoid r => EncodeBit b r | b -> r where 
    encodeBit :: b -> r 

class AbstractFoldable aMulti r where 
    manyFold :: r -> aMulti -> r 

instance (EncodeBit b r, AbstractFoldable otherBits r) => 
        AbstractFoldable (Bits b otherBits) r where 
    manyFold r0 (BitsLst bi other) = manyFold (r0 `mappend` (encodeBit bi)) other 
    manyFold b0 NoMoreBits = b0 

instance AbstractFoldable otherBits r => 
        AbstractFoldable (Bits nb otherBits) r where 
    manyFold r0 (BitsLst _ other) = manyFold r0 other 
    manyFold b0 NoMoreBits = b0 

लेकिन संकलक यह से कोई भी चाहता है। और अच्छे कारण से, चूंकि दोनों उदाहरण घोषणाओं का एक ही सिर है। प्रश्न: Bits पर मनमाने ढंग से टाइप करने का सही तरीका क्या है?

नोट: ऊपर के उदाहरण के साथ अपनी टिप्पणी

{-# LANGUAGE MultiParamTypeClasses, 
      FunctionalDependencies, 
      GADTs, 
      DataKinds, 
      FlexibleInstances, 
      FlexibleContexts 
#-} 

Answer 1

उत्तर देना संकलित किया गया है:

वास्तव में, मैं मैं प्रकार से विषम सूची फ़िल्टर कर सकते, तो कर सकते हैं। क्या यह संभव है?

आप प्रकार से विषम सूची फ़िल्टर अगर आप b करने के लिए एक Typeable बाधा जोड़ सकते हैं।

मुख्य विचार यह है कि हम Data.Typeable के cast :: (Typeable a, Typeable b) => a -> Maybe b का उपयोग यह निर्धारित करने के लिए करेंगे कि सूची में प्रत्येक आइटम एक निश्चित प्रकार का है या नहीं। सूची में प्रत्येक आइटम के लिए Typeable बाधा की आवश्यकता होगी। इस बाधा के साथ एक नई सूची प्रकार बनाने के बजाय, हम जांच करने की क्षमता बनाएंगे कि सूची में All प्रकार कुछ बाधाओं को पूरा करते हैं या नहीं।

हमारा लक्ष्य निम्न प्रोग्राम आउटपुट [True,False] बनाना है, जो केवल Bool तत्वों के लिए एक विषम सूची को फ़िल्टर करना है। मैं पहली बार टुकड़ा वे के लिए

{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE TypeOperators #-} 

example :: HList (Bool ': String ': Bool ': String ': '[]) 
example = HCons True $ HCons "Jack" $ HCons False $ HCons "Jill" $ HNil 

main = do 
    print (ofType example :: [Bool]) 

HList यहाँ की जरूरत है के साथ भाषा एक्सटेंशन और आयात जगह के लिए endevour हास्केल में एक विषम सूची का एक काफी मानक परिभाषा का उपयोग कर रहा होगा DataKinds

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE KindSignatures #-} 

data HList (l :: [*]) where 
    HCons :: h -> HList t -> HList (h ': t) 
    HNil :: HList '[] 

हम करना चाहते हैं ofType जैसे हस्ताक्षर के साथ "अगर All एक विषम सूची में चीजें Typeable हैं, तो विशिष्ट Typeable प्रकार की उन चीज़ों की एक सूची प्राप्त करें।

import Data.Typeable 

ofType :: (All Typeable l, Typeable a) => HList l -> [a] 

ऐसा करने के लिए, हमें कुछ बाधाओं को संतुष्ट करने वाले प्रकारों की सूची में All चीजों की धारणा विकसित करने की आवश्यकता है। हम GADT में संतुष्ट बाधाओं के लिए शब्दकोशों को संग्रहीत करेंगे जो या तो पूंछ के All के लिए सिर बाधा शब्दकोष और बाधाओं को कैप्चर करता है या साबित करता है कि सूची खाली है। All के लिए एक प्रकार की सूची एक बाधा को संतुष्ट करती है यदि हम इसके लिए शब्दकोश कैप्चर कर सकते हैं।

{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE ConstraintKinds #-} 

-- requires the constraints† package. 
-- Constraint is actually in GHC.Prim 
-- it's just easier to get to this way 
import Data.Constraint (Constraint) 

class All (c :: * -> Constraint) (l :: [*]) where 
    allDict :: p1 c -> p2 l -> DList c l 

data DList (ctx :: * -> Constraint) (l :: [*]) where 
    DCons :: (ctx h, All ctx t) => DList ctx (h ': t) 
    DNil ::      DList ctx '[] 

DList वास्तव में शब्दकोशों की एक सूची है। DCons हेड आइटम (ctx h) पर लागू बाधा के लिए शब्दकोश को कैप्चर करता है और शेष सूची के लिए सभी शब्दकोश (All ctx t)।हम सीधे निर्माता से पूंछ के लिए शब्दकोश नहीं प्राप्त कर सकते हैं, लेकिन हम एक ऐसा फ़ंक्शन लिख सकते हैं जो उन्हें All ctx t के लिए शब्दकोश से निकालता है।

{-# LANGUAGE ScopedTypeVariables #-} 

import Data.Proxy 

dtail :: forall ctx h t. DList ctx (h ': t) -> DList ctx t 
dtail DCons = allDict (Proxy :: Proxy ctx) (Proxy :: Proxy t) 

प्रकार के एक खाली सूची तुच्छता से किसी भी बाधा अपने आइटम के सभी को संतुष्ट करने के लिए लागू

instance All c '[] where 
    allDict _ _ = DNil 

एक सूची के सिर की कोई समस्या संतुष्ट करता है और पूंछ के सभी में भी तो सब कुछ करता है, तो सूची बाधा को संतुष्ट करती है।

{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE UndecidableInstances #-} 

instance (c h, All c t) => All c (h ': t) where 
    allDict _ _ = DCons 

अब हम ofType, जो ScopedTypeVariables साथ प्रकार चर तय करने के लिए forall रों की आवश्यकता है लिख सकते हैं।

import Data.Maybe 

ofType :: forall a l. (All Typeable l, Typeable a) => HList l -> [a] 
ofType l = ofType' (allDict (Proxy :: Proxy Typeable) l) l 
    where 
    ofType' :: forall l. (All Typeable l) => DList Typeable l -> HList l -> [a] 
    ofType' d@DCons (HCons x t) = maybeToList (cast x) ++ ofType' (dtail d) t 
    ofType' DNil HNil  = [] 

हम maybeToList . cast के साथ अपने शब्दकोशों के साथ एक साथ HList ज़िप करने और परिणाम श्रृंखलाबद्ध कर रहे हैं। हम इसे RankNTypes के साथ स्पष्ट कर सकते हैं।

{-# LANGUAGE RankNTypes #-} 

import Data.Monoid (Monoid, (<>), mempty) 

zipDHWith :: forall c w l p. (All c l, Monoid w) => (forall a. (c a) => a -> w) -> p c -> HList l -> w 
zipDHWith f p l = zipDHWith' (allDict p l) l 
    where 
    zipDHWith' :: forall l. (All c l) => DList c l -> HList l -> w 
    zipDHWith' d@DCons (HCons x t) = f x <> zipDHWith' (dtail d) t 
    zipDHWith' DNil HNil  = mempty 

ofType :: (All Typeable l, Typeable a) => HList l -> [a] 
ofType = zipDHWith (maybeToList . cast) (Proxy :: Proxy Typeable) 

---

constraints †