CODEWITHSUNDEEP
functional-programmingschemebinary-treeracket
abcd
abcd

Reputation: 33

Forming a tree with this format in DrRacket (or Scheme)

So I am using DrRacket and have a struct defined as: 

(define-struct thing (a b))

Then, I have an example tree of this format:

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

I need to build a function which takes in a non-positive number which is also a power of 2 (so like 1,2,4,8,16...) and either outputs the number 1 (if n=1) or makes a 'thing' in the format as above.

So far I have tried a lot of ways but I either end up getting something like: 

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

I cannot figure out how to increment the variables properly - I've been able to figure out how to apply the required number of make-things:

Here's the code I use right now:

(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))))))

Upvotes: 3

Views: 373

Answers (2)

dufresnb
dufresnb

Reputation: 135

#lang racket

(define-struct thing (a b) #:transparent)

I've defined thing as transparent, for ease of verification

(define (helper level max)
  (if (equal? (/ level 2) 1)
      (make-thing (- max 1) max)
      (make-thing (helper (/ level 2) (- max (/ level 2))) (helper (/ level 2) max))))

max is equal to the highest number in the current thing level is the highest number in the simplest (read lowest values) thing of the same shape (i.e. (thing (thing 5 6) (thing 7 8)) has a max of 8 and a level of 4)

(define (build-thing-or-number n)
  (cond
    ((= n 1) 1)
    (else (helper n n))))

as you can see, helper does all the work.

Upvotes: 2

Will Ness
Will Ness

Reputation: 71055

Allow me to call your build-thing-or-number just g, so I have less typing to do.

So you want

(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

We see that if we had more parameters it'd be much easier to do:

(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

And we use it simply as

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

And that's that!

Upvotes: 3

Related Questions