在 SICP 中推广素数对

我花了一些时间来研究“素数对”的生成SICP 第 2.2.3 节 - 作为常规接口的序列， 例如：

• (1 3)不，因为总和 = 4
• (1 4)是的，因为 sum = 5（素数）

这是我从头开始得到的，有效的：

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

以及实际的功能：

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

很简约。现在我正在尝试编写相同的函数，该函数不只是执行对，而是执行一个元组size。到目前为止，这是我所掌握的：

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

我发现困难的一件事是通过执行类似的操作来删除函数本身内的重复项(range i (- (min args) 1))。所以我只是用了同样的(range 1 n)对于所有循环。

我如何正确地转换它，以便它模拟初始函数，以便列表中的每个连续数字必须更小，即，如果序列中有三个数字，那么1 <= num1 < num2 < num3 <= N，有效的一对是(4 2 1)但不是(1 2 4) or (5 1 1) ?

您的 2D 情况相当于两个嵌套循环：

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

flatmap只是执行机制。是的，这就是本质"monads": the "shape"第二个循环的（范围）取决于value (i）由第一个产生；此外，无论循环的深度如何（此处为 2），最内层循环生成的所有值都会按一个顺序输出。

这也是其本质回溯，因为当我们完成所有的js 对于给定的i，控制来了back进入外循环，并且next i依次进行尝试。

回到我们的业务。当然，3D 情况涉及三个嵌套循环：

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

一般来说，你希望它概括为m嵌套循环，m = 2,3,4,... .

标准构建方式m嵌套循环是带有递归的。如果我们要使用flatmap那么我们只需要意识到外循环内的所有结构都代表m-1嵌套循环计算：

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

似乎正在工作：

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

当然那flatmap就性能而言是糟糕的（除非它可作为低级原语使用），其所有常量结构复制和重新分配与所有这些appends.

当然只有在可变地-有挑战性的语言。另一方面，Scheme 拥有其中最重要的原语：set-cdr!. It has能够以自上而下的方式一次性构建列表，无需复制，无需重新分配（这就是假设的内置列表的方式）flatmap也会运行）。突变并没有什么问题，否则是无法观察到的！

通过在我们的方式构建元组into递归，传递一个callback为了从最深层调用，我们让it做我们需要的事情：只需打印每个元组的构造，append! https://stackoverflow.com/a/13256555/849891它到增长列表的右端（为了提高效率，将其引用保持为隐藏状态，因此可以在O(1)时间），或我们选择的任何其他内容。

所以，无需进一步告别，

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

这会在途中构建元组in，进入最深层次的递归，而不是在途中构建它out，与之前的版本一样。