How can write a program in scheme to find factors of a list of integer? how can extend it into arbitrarily large input?

Question

This is the code for single integer, how can it extend to arbitrarily large input by passing list as a parameter?

(define (factors n)
  (define (*factors d)
    (cond ((> d n) (list))
          ((= (modulo n d) 0) (cons d (*factors (+ d 1))))
          (else (*factors (+ d 1)))))
  (*factors 1))
            
(display (factors 1111111))
(newline)

Answer 1

"...how can it extend to arbitrarily large input by passing list as a parameter?"

The process described by the posted *factors procedure is not iterative, i.e., not tail-recursive, and it will grow stack space for large inputs. I take it that OP is interested in finding a tail-recursive version of this code to improve the space efficiency.

You can convert this to an iterative process by adding an accumulator to the helper procedure. This allows results to be stored in the accumulator and passed through recursive calls without the need for any further operations when those calls return, i.e., tail recursion.

(define (factors-iter n)
  (define (iter d result)
    (cond ((> d n) (reverse result))
          ((zero? (modulo n d))
           (iter (+ d 1) (cons d result)))
          (else
           (iter (+ d 1) result))))
  (iter 1 '()))

Here are the results of tracing the execution of these procedures:

> (factors-trace 8)
|(%factors 1 8)
| (%factors 2 8)
| |(%factors 3 8)
| |(%factors 4 8)
| | (%factors 5 8)
| | (%factors 6 8)
| | (%factors 7 8)
| | (%factors 8 8)
| | |(%factors 9 8)
| | |()
| | (8)
| |(4 8)
| (2 4 8)
|(1 2 4 8)
(1 2 4 8)

> (factors-iter-trace 8)
|(iter 1 8 ())
|(iter 2 8 (1))
|(iter 3 8 (2 1))
|(iter 4 8 (2 1))
|(iter 5 8 (4 2 1))
|(iter 6 8 (4 2 1))
|(iter 7 8 (4 2 1))
|(iter 8 8 (4 2 1))
|(iter 9 8 (8 4 2 1))
|(1 2 4 8)
(1 2 4 8)

Here factors-trace and factors-iter-trace are slightly modified versions of the factors and factors-iter definitions, allowing for a trace. You can see that the %factors process grows in stack size as the computation progresses, but iter maintains a constant stack size.

As others have already answered, the easiest way to use factors-iter with a list of inputs is to use map:

> (map factors-iter '(4 42 314 2998))
((1 2 4) (1 2 3 6 7 14 21 42) (1 2 157 314) (1 2 1499 2998))

Answer 2

If you have a procedure that does something for one value, you can use map to do it for all elements of a list.

(map factors '(50 256 1911))
; ==> ((1 2 5 10 25 50)
;      (1 2 4 8 16 32 64 128 256)
;      (1 3 7 13 21 39 49 91 147 273 637 1911))