开发者

Scheme: recursion and lists

开发者 https://www.devze.com 2023-01-06 23:29 出处:网络
I\'ve been trying to learn some programming on my own by working through the textbook How to Design Programs for Scheme. I\'ve gotten through everything until now. Here\'s the problem:

I've been trying to learn some programming on my own by working through the textbook How to Design Programs for Scheme. I've gotten through everything until now. Here's the problem:

9.5.5 Develop the function convert. It consumes a list of digits and produces the corresponding number. The first digit is the least significant, and so on.

Following the first few steps, from data analysis to template, I end up with this, the bare bones of a program:

;; A list-of-numbers is eithe开发者_运维知识库r 1. an empty list, empty, or 2. (cons n 
lon) where n is a number and lon is a list of numbers 
;; convert : lon -> number 
;; to consume a lon and produce the corresponding number. The least 
significant digit corresponds to the first number in the list, and so 
on. 
;; (= (convert (cons 1 (cons 9 (cons 10 (cons 99 empty))))) 991091) 
(define (convert lon) 
  (cond 
    [(empty? lon)...] 
    [(cons? lon)...(first lon)...(convert (rest lon))...])) 

How do I get past this stage to, as the book has it, "combining values"? The one way I think could work is if I multiplied the first value by 10 to the power of the value's significance in the total number, e.g.,

(cons 1 (cons 9 empty)) => 1 * 10^(SIGNIFICANCE), where LEAST SIGNIFICANCE would be 0. Using my limited understanding of programming, I figure that requires some counter, where n increases by one every time the function, in a manner of speaking, is called recursively. But that looks to me to be an attempt to run two recursions at the same time. Because expressions are evaluated sequentially (obviously), you can't call the counter function as you call the convert function.

So, can anyone help me solve this problem? I would prefer if you solved this using natural recursion and the CONStructor for lists and not lambda or other ideas the book hasn't addressed yet.

Thanks!


You don't need to do exponentiation - simple multiplication will do just fine.

(define (convert digits) 
  (cond
    ((empty? digits) 0)
    (else (+ (* 10 (convert (rest digits))) (first digits)))
  )
)

(convert '(1 2 3 4 5 6))

Or, another way of thinking about it:

(define (convert digits)
  (convert-helper digits 1 0)
)

(define (convert-helper digits multiplier sofar)
  (cond
    ((empty? digits) sofar)
    (else 
        (convert-helper 
            (rest digits) 
            (* 10 multiplier) 
            (+ (* multiplier (first digits)) sofar)
        )
    )
  )
)


(convert '(1 2 3 4 5 6))


Here's a tail recursive version:

(define (convert lon)
  (let rec ((i 0)
            (n 0)
            (lon lon))
    (cond ((empty? lon) n)
          (else (rec (+ i 1)
                     (+ n (* (first lon) (expt 10 i)))
                     (rest lon))))))
0

精彩评论

暂无评论...
验证码 换一张
取 消