スキームはツリーの左端のノードを再帰的に検索します

2020-02-14 recursion tree scheme racket

私は、任意のツリーで最も左のノードを見つける関数を書いています。この関数はツリーを走査したり、左端のノードを指定したりせず、最初のノードの左端の子を指定します。

(define (far-left tree)
  (cond (null? (cadr tree))
        (car tree)
        (far-left (cdr tree))))

サンプル入力。目的のノードではなく、多くのノードを提供します。

(display (far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))))

Answers

データ定義Tree

  • Treeは、 LeafまたはNodeいずれかです。
    • LeafNumberです。
    • Nodeは、サブTree空でないリストです。

機能far-left

  • 条件1 :入力としてのLeafは無効です。これは、「ツリーで最も左にあるノードを見つけることになっているためです。
  • 条件2Node左端(またはfirst )要素にLeafがある場合、それは左端のノードです。左端の要素がLeafではないTreeである場合、それに対して再帰します。
#lang typed/racket

(define-type Leaf Number)
(define-type Node (Pairof Tree (Listof Tree)))
(define-type Tree (U Leaf Node))

(: far-left (-> Tree Node))
(define (far-left tree)
  (cond [(number? tree) (error "Farthest left node of a leaf does not exist!")]
        [(cons? tree)   (if (number? (first tree)) tree (far-left (first tree)))]))

テスト

(far-left '(1 (3 4 (6 7 (12 13))) 8 9 (10 11)))
; =>  '(1 (3 4 (6 7 (12 13))) 8 9 (10 11))

(far-left '((3 4 (6 7 (12 13))) 1  8 9 (10 11)))
; => '(3 4 (6 7 (12 13)))

(far-left '(((6 7 (12 13)) 3 4) 1  8 9 (10 11)))
; => '(6 7 (12 13))

(far-left '((((12 13) 6 7) 3 4) 1  8 9 (10 11)))
; => '(12 13)

「最初のノードの左端の子」と呼ぶものは(cadr tree)です。
関数には1つ(cadr tree)があり、それは最初の条件が常に真であることを示唆しています。
そして、それが何が起こっているのかです。

condの形式は

(cond clause-1 clause-2 ...)

各句の形式は(condition value)です。

あれは、

(cond (condition-1 value-1)
      (condition-2 value-2)
      (condition-3 value-3)
      ...)

これをあなたの機能に合わせると、あなたはそれを見るでしょう

  • null? condition-1(cadr tree)value-1
  • carcondition-2treevalue-2
  • far-leftcondition-3(cdr tree)value-3です。

null?以来null?#fではなく、常に最初の句が選択されます。

正しい形式は

(define (far-left tree)
    (cond
        ((null? (cadr tree)) (car tree))
        (else (far-left (cdr tree)))

ただし、このコードはまだ機能しません。
演習として残されたバグの修正。

Related