क्या इन नि: शुल्क निर्माणों का सामान्यीकरण है?

मैं के साथ मुक्त की तरह विचारों के आसपास खेल रहा था, और पाया इस:क्या इन नि: शुल्क निर्माणों का सामान्यीकरण है?

{-# LANGUAGE RankNTypes #-} 

data Monoid m = Monoid { mempty :: m, mappend :: m -> m -> m } 
data Generator a m = Generator { monoid :: Monoid m, singleton :: a -> m } 

newtype Free f = Free { getFree :: forall s. f s -> s } 

mkMonoid :: (forall s. f s -> Monoid s) -> Monoid (Free f) 
mkMonoid f = Monoid { 
    mempty = Free (mempty . f), 
    mappend = \a b -> Free $ \s -> mappend (f s) (getFree a s) (getFree b s) 
} 

freeMonoid :: Monoid (Free Monoid) 
freeMonoid = mkMonoid id 

mkGenerator :: (forall s. f s -> Generator a s) -> Generator a (Free f) 
mkGenerator f = Generator { 
    monoid = mkMonoid (monoid . f), 
    singleton = \x -> Free $ \s -> singleton (f s) x 
} 

freeGenerator :: Generator a (Free (Generator a)) 
freeGenerator = mkGenerator id

मैं जिसके तहत मैं एक funcion लिख सकता है खोजने के लिए करना चाहते हैं:

mkFree :: (??? f) => f (Free f)

लेकिन मैं असमर्थ रहे हैं f के लिए एक सार्थक संरचना खोजने के लिए (छोटे से एक जिसमें mkFree??? का एक तरीका है) जो इस फ़ंक्शन को लिखे जाने की अनुमति देगा। विशेष रूप से, मेरी सौंदर्य भावना पसंद करेगी यदि इस संरचना में Free प्रकार का उल्लेख नहीं किया गया है।

क्या किसी ने इससे पहले ऐसा कुछ देखा है? क्या यह सामान्यीकरण संभव है? क्या एक दिशा में एक ज्ञात सामान्यीकरण है जिसे मैंने अभी तक नहीं सोचा है?

स्रोत

2013-02-13 luqui

मैं Hackage पर इस राशि (church encoded version सटीक होना करने के लिए।): Http://hackage.haskell.org/ पैकेज/मुक्त functors-0.1।1, लेकिन मुझे नहीं लगता कि आप यही चाहते हैं? –

ठीक है, मेरे पैकेज में आपके पास जो मेल खाता है, मुझे लगता है कि मैं समझता हूं कि आप क्या चाहते हैं। अनुवादित यह होगा कि 'मॉनीओड (फ्री मोनॉयड ए)', या आम तौर पर एक उदाहरण 'सी (फ्री सी ए)' उदाहरण कैसे उत्पन्न किया जाए। उदा 'न्यू' उदाहरण यहां: https://github.com/sjoerdvisscher/free-functors/blob/master/examples/FreeNum.hs। यह मूल रूप से 'लिफ्टएएन' और साधारण मामलों के लिए कुछ शोर है, जो कुछ टेम्पलेट हैकेल के साथ हल करने योग्य होना चाहिए। लेकिन मुझे लगता है कि पूरी तरह से सामान्य मामला काफी जटिल है। –

@SjoerdVisscher, यह वह शोर है जिसमें मुझे रूचि है (यही कारण है कि मैं डेटा प्रकारों का उपयोग कर रहा हूं, यहां कक्षाएं नहीं)। यह 'ट्रैवर्सबल' जैसा लगता है, लेकिन यह पैरामीटर की नकारात्मक घटनाओं पर भी काम करता है। मैं सोच रहा था कि संरचनात्मक (आत्मनिरीक्षण प्रकार हस्ताक्षर) की बजाय बीजगणितीय संपत्ति (जैसे 'ट्रैवर्सबल') है, जिससे यह उदाहरण उत्पन्न किया जा सकता है। – luqui

सार्वभौमिक बीजगणित का लिंक एक अच्छा प्रारंभिक बिंदु था, और उस पर पढ़ने के बाद थोड़ा सा सब कुछ गिर गया।

type Alg f x = f x -> x

किसी भी (एंडो) functor f के लिए

: क्या हम के लिए देख रहे एक एफ बीजगणित है। उदाहरण के लिए, एक monoid बीजगणित के लिए functor है:

data MonoidF m = MEmpty | MAppend m m deriving Functor

किसी भी Monoid उदाहरण के लिए वहाँ स्पष्ट monoid बीजगणित है:

monoidAlg :: Monoid m => Alg MonoidF m 
monoidAlg MEmpty = mempty 
monoidAlg (MAppend a b) = mappend a b

अब हम मुक्त functors पैकेज से मुक्त functor परिभाषा ले जा सकते हैं,

newtype Free f a = Free { runFree :: forall b. Alg f b -> (a -> b) -> b }

मुक्त functor कुछ अर्थों में सबसे अच्छा तरीका है किसी भी एक अल में सेट a चालू करने के लिए है: और च-बीजगणित के साथ वर्ग बाधा की जगह gebra।

unit :: a -> Free f a 
unit a = Free $ \_ k -> k a

यह सबसे अच्छा तरीका है, क्योंकि किसी अन्य तरीके से एक बीजगणित b में a बारी करने के लिए, हम b करने के लिए स्वतंत्र बीजगणित से एक समारोह दे सकते हैं:

rightAdjunct :: Functor f => Alg f b -> (a -> b) -> Free f a -> b 
rightAdjunct alg k (Free f) = f alg k

क्या है यह कैसे है बाईं वास्तव में पता चलता है कि मुक्त functor एक एफ बीजगणित बनाता है (और यह आपके लिए क्या पूछा है):

freeAlg :: Functor f => Alg f (Free f a) 
freeAlg ff = Free $ \alg k -> alg (fmap (rightAdjunct alg k) ff)

थोड़ा व्याख्या करने के लिए: fff (Free f a) प्रकार है और हमें Free f a बनाने की आवश्यकता है। हम ऐसा कर सकते हैं यदि हम बना सकते हैं, alg :: f b -> b और k :: a -> b दिए गए हैं। इसलिए हम alg से ff पर लागू कर सकते हैं यदि हम प्रत्येक Free f a को b पर मैप कर सकते हैं, लेकिन यह rightAdjunctalg और k के साथ है।

आप समझ गए होंगे, यह Free f functor f पर मुक्त इकाई है

instance Functor f => Monad (Free f) where 
    return = unit 
    m >>= f = rightAdjunct freeAlg f m

स्रोत

2013-02-26 10:22:28

धन्यवाद! मैं कल भी इस अहसास में आया था। इसे लिखने के लिए समय लेने के लिए धन्यवाद! – luqui

एनपी, इस सामान को सीखने की खुशी मेरी सारी थी! क्या आपको कुछ चाहिए? –

क्या इन नि: शुल्क निर्माणों का सामान्यीकरण है?

उत्तर

संबंधित मुद्दे