Generalizing prime pairs in SICP

Question

I've taken some time to work through the generation of "prime pairs" from SICP Section 2.2.3 - Sequences as Conventional Interfaces, for example:

• (1 3) No, since sum = 4
• (1 4) Yes, since sum = 5 (prime)

Here is what I have from scratch, which works:

#lang sicp

; RANGE helper function
(define (range a b) ; a to b
 (if (> a b) nil
     (cons a (range (+ 1 a) b))
 ))

; FILTER helper function
(define (filter func sequence)
  (cond ((null? sequence) nil)
        ((func (car sequence)) (cons (car sequence) (filter func (cdr sequence))))
        (else (filter func (cdr sequence)))))

; PRIME helper function
(define (prime? n)
 (cond ((or (= n 1) (= n 2)) #t)
       ((=(modulo n 2) 0) #f)
        (else ; see if no modulos=0 under length of sqrt(N)
         (= 0 
            (length (filter (lambda (i) (eq? i #t))
               (map (lambda (d) (= (modulo n d) 0)) (range 3 (sqrt n)))))))))

; MAP helper
(define (flatmap func seq)
  (if (null? seq) nil (append (func (car seq)) (flatmap func (cdr seq)))))

And the actual function:

; generate pair of two numbers with  1 <=  i < j <= N
(define (get-pairs n)
  (flatmap (lambda (i)
         (map (lambda (j)
                (list i j))
              (range 1 (- i 1))))
       (range 1 n)))

(define (get-prime-pairs n)
  (filter (lambda (p) (prime? (apply + p)))
          (get-pairs n)))

(get-prime-pairs 4)
; ((2 1) (3 2) (4 1) (4 3))

Pretty neat. Now I'm trying to write the same function that instead of just doing pairs, will do a tuple of size. Here is what I have so far for this:

(define (get-n-tuples size n)
  (define (get-n-tuples-internal i args)
    (cond ((= i size) (map (lambda (i) (cons i args)) (range 1 n)))
          (else
           (flatmap (lambda (k)
                      (get-n-tuples-internal (+ i 1) (cons k args)))
                    (range 1 n)))))
  (get-n-tuples-internal 1 '()))

(define (get-prime-seqs size num)
  (filter (lambda (p) (prime? (apply + p)))
          (get-n-tuples size num)))

(get-prime-seqs 4 4)
; ...
; (3 2 4 4)
; (2 3 4 4)
; (1 4 4 4))

One thing which I've found difficult though is to remove duplicate within the function itself by doing something like (range i (- (min args) 1)). So instead I've just used the same (range 1 n) for all of the loops.

How would I properly convert this so that it emulates the initial function, so that each successive number in the list must be smaller, i.e., if there are three numbers in the sequence then 1 <= num1 < num2 < num3 <= N, and a valid pair would be (4 2 1) but not (1 2 4) or (5 1 1) ?

Answer 1

Your 2D case is tantamount to two nested loops:

    for i in 1 to n
      for j in 1 to (i-1)
        yield (i,j)

flatmap is just implementational mechanism, for that. Yes, this is the essence of "monads": the "shape" (range) of the second loop depends on the value (i) produced by the first; furthermore all the values produced from the innermost loop come out in one sequence, no matter the depth of the loops (here it is 2).

It is also the essence of backtracking, since when we're done with all the js for a given i, the control comes back into the outer loop, and the next i is tried in its turn.

Back to our business. Naturally, the 3D case involves three nested loops:

    for i in 1 to n
      for j in 1 to (i-1)
        for k in 1 to (j-1)
          yield (i,j,k)

And in general you want it generalized to m nested loops, m = 2,3,4,... .

The standard way to build m nested loops is with recursion. If we're to use flatmap then we just need to realize that all the structure inside the outer loop represents the m-1 nested loops computation:

(define (tuplesND_ ND max_idx)
  (define (loopvals m imax)
    (if (= m 0)      ; at the deepest level
      (list '())     ; no more indices to collect
      (flatmap                 ; splice in, 
           (lambda (i)         ;   for each i...
             (map (lambda (tup)             ;   (back from
                       (cons i tup))        ;    recursion)
                  (loopvals (- m 1)     ; all the results from
                            (- i 1))))  ;   the m-1 inner loops
         (range 1 imax))))     ;   ...in the proper range
  (loopvals ND max_idx))

Seems to be working:

> (display (tuplesND_ 2 3))
((2 1) (3 1) (3 2))
> (display (tuplesND_ 2 4))
((2 1) (3 1) (3 2) (4 1) (4 2) (4 3))
> (display (tuplesND_ 3 3))
((3 2 1))
> (display (tuplesND_ 3 4))
((3 2 1) (4 2 1) (4 3 1) (4 3 2))
> (display (tuplesND_ 4 5))
((4 3 2 1) (5 3 2 1) (5 4 2 1) (5 4 3 1) (5 4 3 2))

Of course that flatmap is terrible performance-wise (unless it is available as a low-level primitive), with all its constant structure copying and reallocation with all those appends.

It is of course only needed in mutabilitationally-challenged languages. Scheme, on the other hand, has the greatest primitive of them all: set-cdr!. It has the ability to build lists in top-down manner, in one go, no copying, no reallocation (and that's how the hypothetical built-in flatmap would operate, too). And there is nothing wrong with mutation which is otherwise unobservable!

By building the tuple on our way into the recursion, passing a callback to be called from the deepest level, we let it do what we need: just print each tuple as it is constructed, append! it to the growing list's right end (maintaining its reference as a hidden state for efficiency, so it can be accessed in O(1) time), or whatever else we choose.

So, without further adieu,

(define ((tuplesND yield) ND max_idx)
  (define (loops m imax tup)
    (if (= m 0)                  ; at the deepest level,
        (yield (reverse tup))    ; give callback the value
        (for-each                ; otherwise, looping
           (lambda (i)                ; for each i...       
              (loops (- m 1) (- i 1)      ; going into
                     (cons i tup)))       ;   the recursion
           (range 1 imax)))           ; ...in the proper range
    "")       ; (some unimportant value that displays as nothing)  
  (loops ND max_idx '())         ; no indices collected at first
  "")       ; (some unimportant value that displays as nothing)

This builds the tuple on the way in, going into the deepest level of recursion, as opposed to building it on the way out, as in the previous version.