在 SICP 中推广素数对 [英] Generalizing prime pairs in SICP
问题描述
我花了一些时间来研究质数对"的生成.来自 SICP 第 2.2.3 节 - 作为常规接口的序列，例如:
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)不，因为 sum = 4(1 4)是的，因为 sum = 5 (prime)
(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)))))
和实际功能:
; 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 的元组.到目前为止，这是我所拥有的:
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))
我发现困难的一件事是通过执行类似 (range i (- (min args) 1)) 之类的操作来删除函数本身中的重复项.因此，我只是对所有循环使用了相同的 (range 1 n).
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.
我将如何正确转换它以模拟初始函数，以便列表中的每个连续数字必须更小，即，如果序列中有三个数字，则 1 <= num1 <;数量 2 (4 2 1) 但不是 (1 2 4) 或 (5 1 1) ?
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) ?
推荐答案
您的 2D 案例相当于两个嵌套循环:
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 只是实现机制.是的，这就是monads"的本质:第二个循环的形状"(范围)取决于值(i) 产生的第一个；此外，从最里面的循环产生的所有值都以一个序列出现，无论循环的深度如何(这里是 2).
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).
这也是回溯的本质，因为当我们完成给定i的所有j之后，控制返回返回到外循环，next i 依次被尝试.
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.
回到我们的业务.自然，3D 案例涉及三个嵌套循环:
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)
一般来说，您希望将其推广到 m 个嵌套循环，m = 2,3,4,... .
And in general you want it generalized to m nested loops, m = 2,3,4,... .
构建 m 个嵌套循环的标准方法是使用递归.如果我们要使用flatmap，那么我们只需要意识到外循环内的所有结构都代表了m-1 嵌套循环计算:
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 (g m imax)
(if (= m 0)
(list '()) ; at the deepest level
(flatmap (lambda (i)
(map (lambda (tup) (cons i tup)) ; back from
(g (- m 1) (- i 1)))) ; recursion
(range 1 imax))))
(g 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.
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.
当然只有在可变性挑战的语言中才需要它.另一方面，Scheme 拥有其中最大的原语:set-cdr!.它能够以自上而下的方式一次性构建列表，无需复制，无需重新分配(这也是假设的内置 flatmap 的操作方式)).突变没有任何问题，否则无法观察到！
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!
通过构建元组进入递归，传递一个回调从最深层调用，我们让它做我们需要的是:只需在构造每个元组时打印它，append! 它到一个不断增长的列表的右端(将其保持为隐藏状态以提高效率，因此可以在 O(1) 时间内访问它)，或者我们选择的任何其他方式.
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 a growing list's right end (maintaining it as a hidden state for efficiency, so it can be accessed in O(1) time), or whatever else we choose.
所以，不用再说了，
(define ((tuplesND yield) ND max_idx)
(define (g m imax tup)
(if (= m 0)
(yield (reverse tup)) ; at the deepest level
(for-each ; (looping only)
(lambda (i)
(g (- m 1) (- i 1) ; going into
(cons i tup))) ; the recursion
(range 1 imax)))
"") ; (some unimportant value that displays as nothing)
(g ND max_idx '())
"") ; (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.
这篇关于在 SICP 中推广素数对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
