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

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です。
    • A Nodeサブの非空のリストであるTreeの。

機能far-left

  • 条件1 :「すべてのツリーで最も左のノードを見つける必要があるため、入力としてのLeafは無効です。
  • 条件2Node左端(またはfirst )要素としてLeafがある場合、そのNodeは左端のノードです。左端の要素が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