Racket simple procedure for converting number from base 10 to base 4

Question

Im having some problems with racket. The assignment wants me to write a procedure that converts any number from base 10 to base 4, the solution should be written in a list. for example (convert-to-base-four 12) -> (list 3 0) Now i have written a procedure but it inserts each number in an individual list. heres my code.

(define (convert-to-base-four number)
  (cond
    [(<= number 3) (cons number empty)] 
    [(> number 3)  (reverse (list (remainder number 4)
                    (convert-to-base-four (floor (/ number 4)))))]))

Does anyone know what to do? Many thanks

You're using list when you should be using cons. Also the digits are going to be jumbled together in the wrong order because of the multiple reverse calls on different recursive steps. — Alex Knauth
the problem is that if I combined list and reverse it gets screwed up. Is this a paranthesis problem? — stuck_in_racket
No, it's not a paren problem. Your tree is fine. It's mostly a list vs. cons problem. Then once that's solved you have to figure out whether it should use reverse this way or not. — Alex Knauth
in other words when i use "list" I dont need the reverse but the numbers are put individually in lists for example (list (list 3) 0) — stuck_in_racket
ok I used append and it worked. Many thanks for your effort my friend. — stuck_in_racket

Mulan Mulan · Accepted Answer · 2017-11-23T18:10:04

AlexKnauth's comment is the one you need to be following – you must define and adhere to a strict domain (input) and codomain (output) for your function

;; from your code
(list Y
      (convert-to-base-four X))

It doesn't matter what Y and X are here: if convert-to-base-four returns a list of some value and a recursive call to convert-to-base-four – which returns a list – you're going to end up with a list of lists!

One solution, as another points out, is to use append – but beware, it's a trap

(define (base4 n)
  (if (< n 4)
      (list n)
      (append (base4 (floor (/ n 4)))
              (list (remainder n 4)))))

(displayln (base4 12))     ; (3 0)
(displayln (base4 13))     ; (3 1)
(displayln (base4 14))     ; (3 2)
(displayln (base4 15))     ; (3 3)
(displayln (base4 16))     ; (1 0 0)
(displayln (base4 123456)) ; (1 3 2 0 2 1 0 0 0)

A better solution would avoid the costly use of append – here we do that using a named let loop with two loop state variables m and acc

(define (base4 n)
  (let loop ((m n) (acc empty))
    (if (< m 4)
        (cons m acc)
        (loop (floor (/ m 4))
              (cons (remainder m 4) acc)))))

(displayln (base4 12))     ; (3 0)
(displayln (base4 13))     ; (3 1)
(displayln (base4 14))     ; (3 2)
(displayln (base4 15))     ; (3 3)
(displayln (base4 16))     ; (1 0 0)
(displayln (base4 123456)) ; (1 3 2 0 2 1 0 0 0)

Racket simple procedure for converting number from base 10 to base 4

2 Answers