functional-programming - 在 DrRacket(或 Scheme)中以这种格式形成一棵树

Question

所以我正在使用 DrRacket 并将结构定义为:

(define-struct thing (a b))

然后，我有一个这种格式的示例树:

(define v (make-thing 
              (make-thing (make-thing 1 2) 
                          (make-thing 3 4))  
              (make-thing (make-thing 5 6) 
                          (make-thing 7 8))))

我需要构建一个函数，该函数接受一个非正数，该数也是 2 的幂(例如 1,2,4,8,16...)并输出数字 1(如果 n= 1) 或按上述格式制作“东西”。

到目前为止，我已经尝试了很多方法，但我最终得到的结果是:

(make-thing (make-thing (make-thing 1 1) 
                        (make-thing 1 1)) 
            (make-thing (make-thing 1 1) 
                        (make-thing 1 1))))

我无法弄清楚如何正确地增加变量 - 我已经能够弄清楚如何应用所需数量的 make-thing:

这是我现在使用的代码:

(define (helper pow current)
  (cond
    ((= pow 0) 1)
    (else (make-thing 
             (helper (- pow 1) current) 
             (helper (- pow 1) (- current 1))))))

(define current 1)

(define (build-thing-or-number n)
  (cond
    ((= n 1) 1)
    (else (make-thing 
             (helper (- (log n 2) 1) current) 
             (helper (- (log n 2) 1) (add1 current))))))

Answer 1

请允许我将您的 build-thing-or-number 称为 g，这样我就可以少打字了。

所以你想要

(g 1)   =   1                  ; you've got this covered already
(g 2)   =   (thing 1 2)
(g 4)   =   (thing (thing 1 2) (thing 3 4))
(g 8)   =   (thing (thing (thing 1 2) (thing 3 4))       ; 1..4
                   (thing (thing 5 6) (thing 7 8)))      ; 5..8

我们看到，如果我们有更多的参数，它会更容易做到:

(define (h a b)                        ; from ... to
  (cond 
     ((= (+ a 1) b)                    ; like (h 1 2):
        (make-thing a b))              ;    just make the thing
     (else                             ; e.g. (h 1 4)   (h 5 8)
        (let ([c (/ (+ a b -1) 2)])    ;       c = 2     c = 6 
          (make-thing                  ; c is the middle
                 (h a c)               ; make the first half   1..2   1..4
                 (h ..... ))))))       ; and the second        3..4   5..8

我们简单地使用它

(define (g b)
  (cond ((= b 1) 1)
        (else (h ..... ))))

就是这样!