인덱스로 하위 트리를 얻으려면 어떻게합니까?
다음 트리가 있다고 가정합니다.
내 프로그램에서이 트리는 목록을 사용하여 표시 '(+ (* 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& I는 단순히 희망으로 우주를 콜드 부팅에서 자신을 중지해야 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위의 함수에서?
내 구현을 수정했습니다. 이를 개선하는 방법을 알고 있거나 subtreeCPS (Continuation-Passing Style)를 사용하지 않고 구현하는 방법을 알고 있는 경우 답변을 게시하십시오. 특히 비 CPS (및 비 호출 / 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
한 가지 접근 방식은 현재 방문한 노드 수를 추적하는 카운터를 사용하여 트리를 재귀 적으로 걷는 것입니다. loop노드의 자식 으로 before 가 호출 될 때마다 카운터가 증가하므로 loop하위 트리를 걸어 돌아올 때 카운터는 지금까지 방문한 트리 노드의 수를 반영합니다 (로직이 실패한 곳). 원하는 노드가 발견되면 호출 스택을 해제하고 재귀 내부 깊은 곳에서 직접 반환하기 위해 "종료"연속을 사용합니다.
(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충분하다)
좋아, 보자 ... 이러한 깊이 우선 열거의 일반적인 구조는 명시 적으로 유지되는 스택 (또는 너비 우선 순서의 경우 대기열)입니다.
(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)))