लिस्प/स्कीम

Question

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

Answer 1

योजना में, आप इसे आसानी से कर सकते set!, set-car!, और set-cdr! (और कुछ और एक धमाके ('!') है, जो संशोधन को इंगित करता है में समाप्त होने वाले) के साथ:

(let ((x '(1 2 3))) 
    (set-car! x x) 
    ; x is now the list (x 2 3), with the first element referring to itself 
) 

Answer 2

कॉमन लिस्प डेटा संरचनाओं के संशोधन का समर्थन करता है setf के साथ।

आप tying the knot द्वारा हास्केल में एक परिपत्र डेटा संरचना बना सकते हैं।

Answer 3

कॉमन लिस्प में आप सूची सामग्री, सरणी सामग्री, CLOS उदाहरणों में से स्लॉट्स संशोधित कर सकते हैं, आदि

कॉमन लिस्प भी पढ़ सकते हैं और परिपत्र डेटा संरचनाओं लिखने के लिए अनुमति देता है। का प्रयोग करें

? (setf *print-circle* t) 
T 

; a list of two symbols: (foo bar) 

? (defvar *ex1* (list 'foo 'bar)) 
*EX1* 

; now let the first list element point to the list, 
; Common Lisp prints the circular list 

? (setf (first *ex1*) *ex1*) 
#1=(#1# BAR) 

; one can also read such a list 

? '#1=(#1# BAR) 
#1=(#1# BAR) 

; What is the first element? The list itself 

? (first '#1=(#1# BAR)) 
#1=(#1# BAR) 
? 

तथाकथित शुद्ध कार्यात्मक प्रोग्रामिंग भाषाओं दुष्प्रभाव अनुमति नहीं है। अधिकांश लिस्प बोलीभाषा शुद्ध नहीं हैं। वे दुष्प्रभावों की अनुमति देते हैं और वे डेटा संरचनाओं को संशोधित करने की अनुमति देते हैं।

उस पर अधिक के लिए लिस्प परिचय पुस्तकें देखें।

Answer 4

1. आत्म-संदर्भ डेटा संरचनाओं को बनाने के लिए आपको 'विनाशकारी संशोधन' की आवश्यकता नहीं है; उदाहरण के लिए, सामान्य लिस्प में, '#1=(#1#) एक विपक्षी सेल है जिसमें स्वयं शामिल है।

2. योजना और लिस्प विनाशकारी संशोधन करने में सक्षम हैं: यदि आप वैकल्पिक रूप से इस तरह इस परिपत्र विपक्ष का निर्माण कर सकते हैं: (let ((x (cons nil nil))) (rplaca x x) x)

आप हमें बताएं कि क्या सामग्री आप लिस्प सीखने जबकि ले रहे हैं कर सकते हैं/योजना? मैं अपने काले हेलीकॉप्टरों के लिए एक लक्षित सूची संकलित कर रहा हूं; लिस्प और योजना के बारे में गलत जानकारी के फैलाने को रोकना होगा।

Answer 5

CLOS उदाहरण:

 
(defclass node() 
    ((child :accessor node-child :initarg :child))) 

(defun make-node-cycle() 
    (let* ((node1 (make-instance 'node)) 
     (node2 (make-instance 'node :child node1))) 
    (setf (node-child node1) node2))) 

Answer 6

हाँ, और वे उपयोगी हो सकता है। मेरे कॉलेज के प्रोफेसरों में से एक ने स्कीम प्रकार बनाया जिसे उन्होंने मेडुसा नंबर कहा। वे मनमाने ढंग से परिशुद्धता फ्लोटिंग पॉइंट संख्याएं थीं जिनमें दोहराने वाले दशमलव शामिल हो सकते थे। उनके पास एक समारोह था:

(create-medusa numerator denominator) ; or some such 

जिसने तर्कसंगत प्रतिनिधित्व करने वाले मेडुसा संख्या का निर्माण किया। नतीजतन:

(define one-third (create-medusa 1 3)) 
one-third => ; scheme hangs - when you look at a medusa number you turn to stone 
(add-medusa one-third (add-medusa one-third one-third)) => 1 

के रूप में पहले कहा, इस सेट कार का विवेकपूर्ण आवेदन के साथ किया जाता है! और सेट-सीडीआर!

Answer 7

न केवल यह संभव है, यह सामान्य लिस्प ऑब्जेक्ट सिस्टम के लिए बहुत महत्वपूर्ण है: मानक-वर्ग स्वयं का एक उदाहरण है!

Answer 8

मैंने स्पष्ट योजना तकनीकों को उखाड़ फेंका; यह उत्तर केवल हास्केल को संबोधित करता है।

हास्केल में आप इसे let का उपयोग करके पूरी तरह कार्यात्मक रूप से कर सकते हैं, जिसे अच्छी शैली माना जाता है। एक अच्छा उदाहरण regexp-to-NFA रूपांतरण है। आप इसे IORef एस का उपयोग करके अनिवार्य रूप से भी कर सकते हैं, जिसे खराब शैली माना जाता है क्योंकि यह आपके सभी कोड को आईओ मोनैड में मजबूर करता है।

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

Answer 9

हम्म, लिस्प/स्कीम में स्वयं रेफरेंसियल डेटा स्ट्रक्चर, और एसआईसीपी धाराओं का उल्लेख नहीं किया गया है? खैर, संक्षेप में, स्ट्रीम == आलसी मूल्यांकन सूची। यह वास्तव में आपके द्वारा लक्षित आत्म संदर्भ का प्रकार हो सकता है, लेकिन यह एक प्रकार का आत्म संदर्भ है।

तो, एसआईसीपी में cons-stream एक वाक्यविन्यास है जो इसके तर्कों का मूल्यांकन करने में देरी करता है। (cons-stream a b) एक या बी के मूल्यांकन के बिना तुरंत वापस आ जाएगी, और केवल एक या ख जब आप आह्वान car-stream या cdr-stream

SICP से, http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html का मूल्यांकन करता है: >

(define fibs 
    (cons-stream 0 
       (cons-stream 1 
          (add-streams (stream-cdr fibs) 
             fibs)))) 

इस परिभाषा का कहना है कि fibs एक है धारा 0 और 1 से शुरू होती है, जैसे कि बाकी स्ट्रीम हो सकती है जो खुद को फाइबर जोड़कर उत्पन्न होती है एक स्थान से स्थानांतरित:

इस मामले में, 'fibs' एक वस्तु जिसका मूल्य 'fibs'

लगभग उल्लेख करने के लिए, आलसी धाराओं सामान्य रूप से उपलब्ध पुस्तकालयों में पर रहते हैं भूल गया SRFI-40 या SRFI के संदर्भ में परिभाषित किया गया है lazily असाइन किया गया है -41। इन दोनों में से एक सबसे लोकप्रिय योजनाओं में उपलब्ध होना चाहिए, मुझे लगता है कि

Answer 10

Tying the Knot (circular data structures in Haskell) StackOverflow

भी देखें हास्केल विकी पृष्ठ पर: Tying the Knot

Answer 11

मैं इस सवाल पर ठोकर खाई, जबकि के लिए खोज "परिपत्र LISTS लिस्प योजना "। STK सोचता है कि एक सूची दी गई है

सबसे पहले, इस बिंदु पर एक सूची

(define a '(1 2 3)) 

बनाने,:

यह कैसे मैं (STK योजना में) एक बना सकते हैं।

(list? a) 
> #t 

इसके बाद, पिछले तत्व (इस मामले में 3) के पास जाकर cdr जो वर्तमान में अपने आप को एक सूचक के साथ nil शामिल बदलें।

(set-cdr! (cdr (cdr a)) a) 

अब, एसटीके सोचता है कि कोई सूची नहीं है।

(list? a) 
> #f 

(कैसे यह इस बाहर काम करता है?)

अब अगर आप a प्रिंट आप (1 2 3 1 2 3 1 2 ... की एक असीम लंबी सूची मिल जाएगा और आप इस कार्यक्रम को मारने के लिए की आवश्यकता होगी। Stk में आप control-z या control-\ छोड़ने के लिए कर सकते हैं।

लेकिन परिपत्र-सूचियों के लिए क्या अच्छा है?

मैं ऐसे सप्ताह (M T W T F S S M T W ...), या 3 बिट्स (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..) द्वारा प्रतिनिधित्व पूर्णांकों का एक परिपत्र सूची के दिनों की एक परिपत्र सूची के रूप में सापेक्ष अंकगणित से कोई लेना देना अस्पष्ट उदाहरण के बारे में सोच सकते हैं।

क्या कोई असली दुनिया उदाहरण हैं?