在 SICP 中推广素数对
Generalizing prime pairs in SICP
我花了一些时间从 SICP 第 2.2.3 节 - 作为常规接口的序列 中生成“素数对”，例如：
(1 3) 否，因为总和 = 4(1 4) 是的，因为总和 = 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) 或 (5 1 1) ?
您的 2D 案例相当于两个嵌套循环：
for i in 1 to n
for j in 1 to (i-1)
yield (i,j)
flatmap 只是实现机制。是的，这就是"monads"的本质：第二个循环的"shape"（范围）取决于 value (i) 由第一个产生；此外，无论循环的深度如何（这里是 2），最内层循环产生的所有值都以一个序列出现。
这也是回溯的本质，因为当我们完成给定i的所有j时，控制就来了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 在性能方面很糟糕（除非它可以作为低级原语使用），所有这些 append 的常量结构复制和重新分配。
当然只有在可变挑战的语言中才需要它。另一方面，Scheme 拥有所有原语中最大的原语：set-cdr!。它 具有 以自上而下的方式一次性构建列表的能力，无需复制，无需重新分配（这也是假设的内置 flatmap 的运作方式).突变没有任何问题，否则无法观察到！
通过在进入递归的过程中构建元组，传递一个回调从最深层次调用，我们让it 做我们需要的事情：只打印每个元组的构造，append! 它到增长列表的右端（为了效率保持它的引用作为隐藏状态，所以它可以在 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[=75= 的方式上构建它]，和之前的版本一样。
我花了一些时间从 SICP 第 2.2.3 节 - 作为常规接口的序列 中生成“素数对”，例如：
(1 3)否，因为总和 = 4(1 4)是的，因为总和 = 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) 或 (5 1 1) ?
您的 2D 案例相当于两个嵌套循环：
for i in 1 to n
for j in 1 to (i-1)
yield (i,j)
flatmap 只是实现机制。是的，这就是"monads"的本质：第二个循环的"shape"（范围）取决于 value (i) 由第一个产生；此外，无论循环的深度如何（这里是 2），最内层循环产生的所有值都以一个序列出现。
这也是回溯的本质，因为当我们完成给定i的所有j时，控制就来了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 在性能方面很糟糕（除非它可以作为低级原语使用），所有这些 append 的常量结构复制和重新分配。
当然只有在可变挑战的语言中才需要它。另一方面，Scheme 拥有所有原语中最大的原语：set-cdr!。它 具有 以自上而下的方式一次性构建列表的能力，无需复制，无需重新分配（这也是假设的内置 flatmap 的运作方式).突变没有任何问题，否则无法观察到！
通过在进入递归的过程中构建元组，传递一个回调从最深层次调用，我们让it 做我们需要的事情：只打印每个元组的构造，append! 它到增长列表的右端（为了效率保持它的引用作为隐藏状态，所以它可以在 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[=75= 的方式上构建它]，和之前的版本一样。