फिक्स्ड पॉइंट संयोजक?

Question

पारस्परिक रूप से पुनरावर्ती कार्यों के tuples बनाने के लिए एक निश्चित बिंदु संयोजक है? अर्थात। मैं वाई-कॉम्बिनेटर की तरह कुछ ढूंढ रहा हूं लेकिन जो कई "रिकर्सिव" * फ़ंक्शन लेता है, और फ़ंक्शंस का एक टुपल लौटाएगा?

*: वास्तव में पाठ्यक्रम की पुनरावृत्ति नहीं है, क्योंकि वे सामान्य वाई-कॉम्बिनेटर तरीके से स्वयं (और भाई बहनों) को तर्क के रूप में लेने के लिए लिखे जाते हैं।

Answer 1

जो प्राणी आप खोज रहे हैं वह वाई * संयोजक है।

this page by oleg-at-okmij.org के आधार पर मैं Y * Clojure में पोर्ट:

(defn Y* [& fs] 
    (map (fn [f] (f)) 
    ((fn [x] (x x)) 
     (fn [p] 
     (map 
      (fn [f] 
      (fn [] 
       (apply f 
       (map 
        (fn [ff] 
        (fn [& y] (apply (ff) y))) 
        (p p))))) 
      fs))))) 

आपसी पुनरावर्ती क्रिया की क्लासिक उदाहरण इसलिए यहाँ भी/अजीब है उदाहरण है:

(let 
    [[even? odd?] 
    (Y* 
    (fn [e o] 
     (fn [n] 
     (or (= 0 n) (o (dec n))))) 
    (fn [e o] 
     (fn [n] 
     (and (not= 0 n) (e (dec n))))) 
    ) 
    ] 
    (do 
    (assert (even? 14)) 
    (assert (odd? 333)) 
    )) 

आप कर सकते हैं यदि आप बड़े पर्याप्त तर्कों का उपयोग करते हैं तो आसानी से इस फ़ंक्शन के साथ स्टैक को उड़ाएं, इसलिए यहां इसका ट्रैम्पोलिन्ड संस्करण है उदाहरण के लिए पूर्णता जो स्टैक का उपभोग नहीं करती है:

(let 
    [[even? odd?] 
    (Y* 
    (fn [e o] 
     (fn [n] 
     (or (= 0 n) #(o (dec n))))) 
    (fn [e o] 
     (fn [n] 
     (and (not= 0 n) #(e (dec n))))) 
    ) 
    ] 
    (do 
    (assert (trampoline even? 144444)) 
    (assert (trampoline odd? 333333)) 
    )) 

Y * Combinator monadic पारसर्स, जिनमें से मैं तैयार रहें lambder.com पर जल्द ही ब्लॉग होगा, के आपसी पुनरावर्ती परिभाषाओं को परिभाषित करने के लिए बहुत उपयोगी है;)

- Lambder

Answer 2

मुझे इस बारे में पूरी तरह से यकीन नहीं है। मैं अभी भी इसके औपचारिक प्रमाण को खोजने की कोशिश कर रहा हूं। लेकिन ऐसा लगता है कि आपको एक की जरूरत नहीं है। हास्केल में, आप की तरह कुछ पूछना चाहते हैं तो:

ठीक :: (एक -> एक) -> एक
ठीक च = जाने एक्स = एक्स में fx

मुख्य = जाने {x =। .. वाई ...; y = ... एक्स ...} x

में आप के लिए

मुख्य = मुख्य पुनर्लेखन कर सकते हैं FST $ $ \ (एक्स, वाई) को ठीक -> (... y .. ।, ... x ...)

लेकिन जैसा कि मैंने कहा, मैं इस बारे में 100% निश्चित नहीं हूं।

Answer 3

निम्नलिखित वेब पेज आपसी रिकर्सन (पॉलीवार्यैडिक फ़िक्सपॉइंट संयोजक) के लिए फिक्स-पॉइंट संयोजनकर्ताओं का विस्तार से वर्णन करता है। यह अब तक का सबसे आसान संयोजक प्राप्त करता है। http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic

संदर्भ में आसानी के लिए, यहाँ हास्केल (एक-लाइनर)

fix_poly:: [[a]->a] -> [a] 
fix_poly fl = fix (\self -> map ($ self) fl) 
    where fix f = f (fix f) 

और यहाँ में सबसे सरल polyvariadic Combinator है यह योजना, एक सख्त भाषा

(define (Y* . l) 
    ((lambda (u) (u u)) 
    (lambda (p) 
     (map (lambda (li) (lambda x (apply (apply li (p p)) x))) l)))) 

में है कृपया उदाहरणों और अधिक चर्चा के लिए वेब पेज देखें।