18

Lispまたはスキームで自己参照データ構造(たとえば、サイクルを含むグラフ)を構築する方法はありますか? これまで考えたことはありませんでしたが、破壊的な変更を行う方法がないため、いじってみると簡単な方法を見つけることができません。これは関数型言語の本質的な欠陥にすぎないのでしょうか? もしそうなら、haskell のような遅延関数型言語はどうでしょうか?

4

11 に答える 11

15

Common Lisp では、リストの内容、配列の内容、CLOS インスタンスのスロットなどを変更できます。

Common Lisp では循環データ構造の読み書きも可能です。使用する

? (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)
?

いわゆる純粋な関数型プログラミング言語は、副作用を許しません。ほとんどの Lisp 方言は純粋ではありません。それらは副作用を許し、データ構造を変更することを許します。

詳細については、Lisp 入門書を参照してください。

于 2009-03-03T09:33:35.703 に答える
9

スキームでは、、、、および（および変更を示すバング（）で終わるその他のもの）を使用して簡単に行うことができます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
  )
于 2009-03-03T03:35:51.723 に答える
9

Common Lisp は、 によるデータ構造の変更をサポートしていsetfます。

結び目を結ぶことで、Haskell で循環データ構造を構築できます。

于 2009-03-03T04:05:16.023 に答える
5

  1. 自己参照データ構造を構築するために「破壊的な変更」は必要ありません。たとえば、Common Lisp では、'#1=(#1#)それ自体を含むコンスセルです。

  2. Scheme と Lisp は破壊的な変更を行うことができます: 上記の循環コンスを次のように構築することもできます: (let ((x (cons nil nil))) (rplaca x x) x)

Lisp/Scheme の学習中に使用している教材を教えていただけますか? 黒いヘリコプターのターゲット リストを編集しています。Lisp と Scheme に関する誤った情報の拡散は止めなければなりません。

于 2009-03-03T14:49:58.687 に答える
3

それが可能であるだけでなく、Common Lisp Object System の中心でもあります: 標準クラスはそれ自体のインスタンスです!

于 2009-03-03T23:08:41.937 に答える
1

StackOverflowで Knot (Haskell の循環データ構造)を結ぶ

Haskell Wiki ページも参照してください: Tying the Knot

于 2009-08-06T13:32:07.047 に答える
1

CLOS の例:

(defclass ノード ()
  ((child :accessor node-child :initarg :child)))

(defun make-node-cycle ()
  (let* ((node1 (make-instance 'node))
         (node2 (make-instance 'ノード:子ノード1)))
     (setf (node-child node1) node2)))
于 2009-03-03T18:14:03.860 に答える
0

「CIRCULAR LISTS LISP SCHEME」を検索しているときに、この質問に出くわしました。

これは、（STkスキームで）作成する方法です：

まず、リストを作成します

(define a '(1 2 3))

この時点で、STk は a がリストであると考えます。

(list? a)
> #t

次に、最後の要素 (この場合は ) に移動し、現在含まれている をそれ自体へのポインターに3置き換えます。cdrnil

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

ここで、STk は 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 ..)。

実際の例はありますか？

于 2010-03-07T06:03:44.337 に答える
0

うーん、Lisp/Scheme の自己参照データ構造と SICP ストリームについて言及されていませんか? 要約すると、ストリーム == 遅延評価リスト。それはまさにあなたが意図した種類の自己参照かもしれませんが、一種の自己参照です。

したがって、cons-streamSICP には、引数の評価を遅らせる構文があります。 a または b を評価せずにすぐに戻り、または(cons-stream a b)を呼び出したときにのみ a または b を評価します。car-streamcdr-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 で始まるストリームであることを示しており、ストリームの残りの部分は、それ自体に 1 桁シフトされた fibs を追加することによって生成できます。

この場合、「fibs」には、値が「fibs」に関して遅延定義されたオブジェクトが割り当てられます。

言及するのをほとんど忘れていましたが、遅延ストリームは、一般的に利用可能なライブラリ SRFI-40 または SRFI-41 で生き続けています。これら 2 つのうちの 1 つが最も一般的なスキームで利用できるはずです。

于 2009-06-18T06:30:49.117 に答える