インデックスでサブツリーを取得するにはどうすればよいですか？
次のツリーがあるとします。
私のプログラムでは、このツリーはリストを使用して表されます'(+ (* 5 6) (sqrt 3))。
インデックスでサブツリーを取得するにはどうすればよいですか？
インデックスは0から始まり、深さ優先である必要があります。上の図では、これを示すために、すべてのノードにインデックスを付けています。
例えば：
(define tree '(+ (* 5 6) (sqrt 3)))
(subtree tree 0) ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree tree 1) ; Returns: '(* 5 6)
(subtree tree 2) ; Returns: 5
(subtree tree 3) ; Returns: 6
(subtree tree 4) ; Returns: '(sqrt 3)
(subtree tree 5) ; Returns: 3
私はsubtreeこのように実装しようとしました：
(define (subtree tree index)
(cond [(= index 0) tree]
[else
(subtree (cdr tree)
(- index 1))]))
ただし、これはサブリストにトラバースしません。正しくありません。
編集：
subtree継続渡しスタイルを使用して実装しようとしました：
(define (subtree& exp index counter f)
(cond [(= counter index) exp]
[(null? exp) (f counter)]
[(list? exp)
(let ((children (cdr exp)))
(subtree& (car children)
index
(+ counter 1)
(lambda (counter2)
(if (null? (cdr children))
(f counter)
(subtree& (cadr children)
index
(+ counter2 1)
f)))))]
[else (f counter)]))
(define (subtree tree index)
(subtree& tree
index
0
(lambda (_)
(error "Index out of bounds" index))))
これは、次のようなツリーで正しく機能します。
'(+ 1 2)'(+ (* 5 6) (sqrt 3))
ただし、次のようなツリーでは失敗します。
'(+ 1 2 3)
私の実装の何が問題になっていますか？
回答
ヘアリーコントロールコンストラクトなしでこれを行う方法は、アジェンダを使用することです。
ただし、その前に、抽象化を定義してください。何かを歩いているコードを見るたびに、それは「ツリー」と呼ばれ、明示的なものcarでいっぱいです。cdr＆cより良いものが得られることを期待して、単に宇宙をコールドブートするのをやめなければなりません。あなたが教えている人があなたに言っていないのなら、これは彼らと強い言葉を持っています。
ツリー構造の抽象化を次に示します。ツリー構造が本当に不規則であるため、これらは特に重要です。どのノードでも「このノードの子をください」と言いたいです。葉は子のないノードであり、特別な種類のものではありません。
(define (make-node value . children)
;; make a tree node with value and children
(if (null? children)
value
(cons value children)))
(define (node-value node)
;; the value of a node
(if (cons? node)
(car node)
node))
(define (node-children node)
;; the children of a node as a list.
(if (cons? node)
(cdr node)
'()))
今、議題のためのいくつかの抽象化。アジェンダはリストとして表されますが、もちろんこれを知っている人は他にいません。より産業的な実装では、アジェンダをそのように表現したくない場合があります。
(define empty-agenda
;; an empty agenda
'())
(define agenda-empty?
;; is an agenda empty?
empty?)
(define (agenda-next agenda)
;; return the next element of an agenda if it is not empty
;; error if it is
(if (not (null? agenda))
(car agenda)
(error 'agenda-next "empty agenda")))
(define (agenda-rest agenda)
;; Return an agenda without the next element, or error if the
;; agenda is empty
(if (not (null? agenda))
(cdr agenda)
(error 'agenda-rest "empty agenda")))
(define (agenda-prepend agenda things)
;; Prepend things to agenda: the first element of things will be
;; the next element of the new agenda
(append things agenda))
(define (agenda-append agenda things)
;; append things to agenda: the elements of things will be after
;; all elements of agenda in the new agenda
(append agenda things))
これで、あらゆる種類の厄介な制御構造を使用せずに、関数の純粋な反復バージョンを簡単に作成できます（アジェンダはスタックを維持します）。
(define (node-indexed root index)
;; find the node with index index in root.
(let ni-loop ([idx 0]
[agenda (agenda-prepend empty-agenda (list root))])
(cond [(agenda-empty? agenda)
;; we're out of agenda: raise an exception
(error 'node-indexed "no node with index ~A" index)]
[(= idx index)
;; we've found it: it's whatever is next on the agenda
(agenda-next agenda)]
[else
;; carry on after adding all the children of this node
;; to the agenda
(ni-loop (+ idx 1)
(agenda-prepend (agenda-rest agenda)
(node-children
(agenda-next agenda))))])))
考える事：あなたは置き換えるとどうなるかagenda-prependによって、agenda-append上記の関数では？
実装を修正しました。これを改善する方法、またはsubtree継続渡しスタイル（CPS）を使用せずに実装する方法を知っている場合は、回答を投稿してください。私は特に非CPS（および非call / cc）の実装に興味があります。
継続渡しスタイルの使用：
(define (subtree& exp index counter f)
(cond [(= counter index) exp]
[(null? exp) (f counter)]
[(list? exp)
(define children (cdr exp))
(define (sibling-continuation siblings)
(lambda (counter2)
(if (null? siblings)
(f counter2)
(subtree& (car siblings)
index
(+ counter2 1)
(sibling-continuation (cdr siblings))))))
(subtree& (car children)
index
(+ counter 1)
(sibling-continuation (cdr children)))]
[else (f counter)]))
(define (subtree tree index)
(subtree& tree
index
0
(lambda (max-index)
(error "Index out of bounds" index))))
使用法：
(define t1 '(+ (* 5 6) (sqrt 3)))
(subtree t1 0) ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree t1 1) ; Returns: '(* 5 6)
(subtree t1 2) ; Returns: 5
(subtree t1 3) ; Returns: 6
(subtree t1 4) ; Returns: '(sqrt 3)
(subtree t1 5) ; Returns: 3
(define t2 '(+ 0 (* (/ 1 2) (- 3 4)) (sqrt 5) 6))
(subtree t2 0) ; Returns: '(+ 0 (* (/ 1 2) (- 3 4)) (sqrt 5) 6)
(subtree t2 1) ; Returns: 0
(subtree t2 2) ; Returns: '(* (/ 1 2) (- 3 4))
(subtree t2 3) ; Returns: '(/ 1 2)
(subtree t2 4) ; Returns: 1
(subtree t2 5) ; Returns: 2
(subtree t2 6) ; Returns: '(- 3 4)
(subtree t2 7) ; Returns: 3
(subtree t2 8) ; Returns: 4
(subtree t2 9) ; Returns: '(sqrt 5)
(subtree t2 10) ; Returns: 5
(subtree t2 11) ; Returns: 6
訪問したノードの現在の数を追跡するカウンターを使用して、ツリーを再帰的にウォークする1つのアプローチ。beforeloopがノードの子で呼び出されるたびに、カウンターがインクリメントされるためloop、サブツリーのウォークから戻ると、カウンターはこれまでにアクセスしたツリーノードの数を反映します（ロジックが失敗している場所です）。「exit」継続を使用して、目的のノードが見つかったときにコールスタックの巻き戻しを短絡し、再帰の奥深くから直接返します。
(require-extension (srfi 1))
(require-extension (chicken format))
(define (subtree tree idx)
(call/cc
(lambda (return-result)
(let loop ((node tree)
(n 0)) ; the counter
(cond
((= idx n) ; We're at the desired node
(return-result node))
((list? node) ; Node is itself a tree; recursively walk its children.
(fold (lambda (elem k) (loop elem (+ k 1))) n (cdr node)))
(else n))) ; Leaf node; return the count of nodes so far
;; return-result hasn't been called, so raise an error
(error "No such index"))))
(define (test tree depth)
(printf "(subtree tree ~A) -> ~A~%" depth (subtree tree depth)))
(define tree '(+ (* 5 6) (sqrt 3)))
(test tree 0)
(test tree 1)
(test tree 2)
(test tree 3)
(test tree 4)
(test tree 5)
チキンスキーム方言; ラケットをインストールしていません。必要な変換は、読者の練習問題として残されています。
（交換のようなルックスfoldではfoldl十分です）
OK、見てみましょう...このような深さ優先の列挙の一般的な構造は、明示的に維持されたスタック（または幅優先の順序の場合はキュー）を使用します。
(define (subtree t i)
(let loop ((t t) (k 0) (s (list))) ; s for stack
(cond
((= k i) t) ; or: (append s (cdr t)) for a kind of
((pair? t) (loop (car t) (+ k 1) (append (cdr t) s))) ; bfs ordering
((null? s) (list 'NOT-FOUND))
(else (loop (car s) (+ k 1) (cdr s))))))
これは似たようなことをしますが、あなたが望んでいたこととは異なります。
> (map (lambda (i) (list i ': (subtree tree i))) (range 10))
'((0 : (+ (* 5 6) (sqrt 3)))
(1 : +)
(2 : (* 5 6))
(3 : *)
(4 : 5)
(5 : 6)
(6 : (sqrt 3))
(7 : sqrt)
(8 : 3)
(9 : (NOT-FOUND)))
あなたの例のように、アプリケーションの最初の要素をスキップしたい：
(define (subtree-1 t i) ; skips the head elt
(let loop ((t t) (k 0) (s (list))) ; s for stack
(cond
((= k i) t)
((and (pair? t)
(pair? (cdr t)));____ ____ ; the
(loop (cadr t) (+ k 1) (append (cddr t) s))) ; changes
((null? s) (list 'NOT-FOUND))
(else (loop (car s) (+ k 1) (cdr s))))))
だから今、あなたが望むように、
> (map (lambda (i) (list i ': (subtree-1 tree i))) (range 7))
'((0 : (+ (* 5 6) (sqrt 3)))
(1 : (* 5 6))
(2 : 5)
(3 : 6)
(4 : (sqrt 3))
(5 : 3)
(6 : (NOT-FOUND)))