题目要求我们完成三个任务:
sum
,检查三元组的三个元之和是否等于 sum
,如果是的话返回真,否则返回假在 练习 2.40 ,我们写出了 unique-pairs
函数,它可以生成由相异整数组成的二元组:
1 ]=> (load "40-unique-pairs.scm")
;Loading "40-unique-pairs.scm"...
; Loading "p78-enumerate-interval.scm"... done
; Loading "p83-flatmap.scm"...
; Loading "p78-accumulate.scm"... done
; ... done
;... done
;Value: unique-pairs
1 ]=> (unique-pairs 5)
;Value 24: ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3) (5 1) (5 2) (5 3) (5 4))
我们可以推广这个方法,把它用于生成由相异整数组成的三元组,方法如下:
;;; 41-unique-triples.scm
(load "p78-enumerate-interval.scm")
(load "p83-flatmap.scm")
(load "40-unique-pairs.scm")
(define (unique-triples n)
(flatmap (lambda (i)
(map (lambda (j) ; cons 起 i 元素和二元组 j ,组成三元组
(cons i j))
(unique-pairs (- i 1)))) ; 生成不大于 i 的所有相异整数二元组
(enumerate-interval 1 n))) ; 生成 1 至 n 的所有整数,作为 i
这个函数通过 (enumerate-interval 1 n)
生成 1
到 n
作为变量 i
,再对每个 i
生成相异的二元组 (unique-pairs (- i 1))
,最后用 cons
组合起 i
和 (unique-pairs (- i 1))
,得出的结果就是相异的三元组。
测试:
1 ]=> (load "41-unique-triples.scm")
;Loading "41-unique-triples.scm"...
; Loading "p78-enumerate-interval.scm"... done
; Loading "p83-flatmap.scm"...
; Loading "p78-accumulate.scm"... done
; ... done
; Loading "40-unique-pairs.scm"...
; Loading "p78-enumerate-interval.scm"... done
; Loading "p83-flatmap.scm"...
; Loading "p78-accumulate.scm"... done
; ... done
; ... done
;... done
;Value: unique-triples
1 ]=> (unique-triples 5)
;Value 11: ((3 2 1) (4 2 1) (4 3 1) (4 3 2) (5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3))
谓词函数的定义如下:
;;; 41-triple-sum-equal-to.scm
(define (triple-sum-equal-to? sum triple)
(= sum
(+ (car triple)
(cadr triple)
(caddr triple))))
测试:
1 ]=> (load "41-triple-sum-equal-to.scm")
;Loading "41-triple-sum-equal-to.scm"... done
;Value: triple-sum-equal-to?
1 ]=> (triple-sum-equal-to? 6 (list 1 2 3))
;Value: #t
1 ]=> (triple-sum-equal-to? 0 (list 1 2 3))
;Value: #f
谓词函数的另一种更方便的定义方式是:
;;; 41-triple-sum-equal-to-using-fold.scm
(define (triple-sum-equal-to? sum triple)
(= sum
(fold-right + 0 triple)))
测试:
1 ]=> (load "41-triple-sum-equal-to-using-fold.scm")
;Loading "41-triple-sum-equal-to-using-fold.scm"... done
;Value: triple-sum-equal-to?
1 ]=> (triple-sum-equal-to? 3 (list 1 1 1))
;Value: #t
1 ]=> (triple-sum-equal-to? 0 (list 1 2 3))
;Value: #f
过滤的实质性工作可以使用 filter
函数来完成,我们只要写一个包装函数组合起谓词函数和 filter
就可以了:
;;; 41-remove-triples-not-equal-to.scm
(load "41-triple-sum-equal-to.scm")
(define (remove-triples-not-equal-to sum triple)
(filter (lambda (current-triple)
(triple-sum-equal-to? sum current-triple))
triple))
remove-triples-not-equal-to
接受 sum
和 triple
两个参数,删除 triple
中所有三元组之和不等于 sum
的三元组:
1 ]=> (load "41-unique-triples.scm")
;Loading "41-unique-triples.scm"...
; Loading "p78-enumerate-interval.scm"... done
; Loading "p83-flatmap.scm"...
; Loading "p78-accumulate.scm"... done
; ... done
; Loading "40-unique-pairs.scm"...
; Loading "p78-enumerate-interval.scm"... done
; Loading "p83-flatmap.scm"...
; Loading "p78-accumulate.scm"... done
; ... done
; ... done
;... done
;Value: unique-triples
1 ]=> (load "41-remove-triples-not-equal-to.scm")
;Loading "41-remove-triples-not-equal-to.scm"...
; Loading "41-triple-sum-equal-to.scm"... done
;... done
;Value: remove-triples-not-equal-to
1 ]=> (remove-triples-not-equal-to 5 (unique-triples 6))
;Value: ()
1 ]=> (remove-triples-not-equal-to 6 (unique-triples 6))
;Value 11: ((3 2 1))
1 ]=> (unique-triples 13)
;Value 14: ((3 2 1) (4 2 1) (4 3 1) (4 3 2) (5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3) (6 2 1) (6 3 1) (6 3 2) (6 4 1) (6 4 2) (6 4 3) (6 5 1) (6 5 2) (6 5 3) (6 5 4) (7 2 1) (7 3 1) (7 3 2) (7 4 1) (7 4 2) (7 4 3) (7 5 1) (7 5 2) (7 5 3) (7 5 4) (7 6 1) (7 6 2) (7 6 3) (7 6 4) (7 6 5) (8 2 1) (8 3 1) (8 3 2) (8 4 1) (8 4 2) (8 4 3) (8 5 1) (8 5 2) (8 5 3) (8 5 4) (8 6 1) (8 6 2) (8 6 3) (8 6 4) (8 6 5) (8 7 1) (8 7 2) (8 7 3) (8 7 4) (8 7 5) (8 7 6) (9 2 1) (9 3 1) (9 3 2) (9 4 1) (9 4 2) (9 4 3) (9 5 1) (9 5 2) (9 5 3) (9 5 4) (9 6 1) (9 6 2) (9 6 3) (9 6 4) (9 6 5) (9 7 1) (9 7 2) (9 7 3) (9 7 4) (9 7 5) (9 7 6) (9 8 1) (9 8 2) (9 8 3) (9 8 4) (9 8 5) (9 8 6) (9 8 7) (10 2 1) (10 3 1) (10 3 2) (10 4 1) (10 4 2) (10 4 3) (10 5 1) (10 5 2) (10 5 3) (10 5 4) (10 6 1) (10 6 2) (10 6 3) (10 6 4) (10 6 5) (10 7 1) (10 7 2) (10 7 3) (10 7 4) (10 7 5) (10 7 6) (10 8 1) (10 8 2) (10 8 3) (10 8 4) (10 8 5) (10 8 6) (10 8 7) (10 9 1) (10 9 2) (10 9 3) (10 9 4) (10 9 5) (10 9 6) (10 9 7) (10 9 8) (11 2 1) (11 3 1) (11 3 2) (11 4 1) (11 4 2) (11 4 3) (11 5 1) (11 5 2) (11 5 3) (11 5 4) (11 6 1) (11 6 2) (11 6 3) (11 6 4) (11 6 5) (11 7 1) (11 7 2) (11 7 3) (11 7 4) (11 7 5) (11 7 6) (11 8 1) (11 8 2) (11 8 3) (11 8 4) (11 8 5) (11 8 6) (11 8 7) (11 9 1) (11 9 2) (11 9 3) (11 9 4) (11 9 5) (11 9 6) (11 9 7) (11 9 8) (11 10 1) (11 10 2) (11 10 3) (11 10 4) (11 10 5) (11 10 6) (11 10 7) (11 10 8) (11 10 9) (12 2 1) (12 3 1) (12 3 2) (12 4 1) (12 4 2) (12 4 3) (12 5 1) (12 5 2) (12 5 3) (12 5 4) (12 6 1) (12 6 2) (12 6 3) (12 6 4) (12 6 5) (12 7 1) (12 7 2) (12 7 3) (12 7 4) (12 7 5) (12 7 6) (12 8 1) (12 8 2) (12 8 3) (12 8 4) (12 8 5) (12 8 6) (12 8 7) (12 9 1) (12 9 2) (12 9 3) (12 9 4) (12 9 5) (12 9 6) (12 9 7) (12 9 8) (12 10 1) (12 10 2) (12 10 3) (12 10 4) (12 10 5) (12 10 6) (12 10 7) (12 10 8) (12 10 9) (12 11 1) (12 11 2) (12 11 3) (12 11 4) (12 11 5) (12 11 6) (12 11 7) (12 11 8) (12 11 9) (12 11 10) (13 2 1) (13 3 1) (13 3 2) (13 4 1) (13 4 2) (13 4 3) (13 5 1) (13 5 2) (13 5 3) (13 5 4) (13 6 1) (13 6 2) (13 6 3) (13 6 4) (13 6 5) (13 7 1) (13 7 2) (13 7 3) (13 7 4) (13 7 5) (13 7 6) (13 8 1) (13 8 2) (13 8 3) (13 8 4) (13 8 5) (13 8 6) (13 8 7) (13 9 1) (13 9 2) (13 9 3) (13 9 4) (13 9 5) (13 9 6) (13 9 7) (13 9 8) (13 10 1) (13 10 2) (13 10 3) (13 10 4) (13 10 5) (13 10 6) (13 10 7) (13 10 8) (13 10 9) (13 11 1) (13 11 2) (13 11 3) (13 11 4) (13 11 5) (13 11 6) (13 11 7) (13 11 8) (13 11 9) (13 11 10) (13 12 1) (13 12 2) (13 12 3) (13 12 4) (13 12 5) (13 12 6) (13 12 7) (13 12 8) (13 12 9) (13 12 10) (13 12 11))
1 ]=> (remove-triples-not-equal-to 10 (unique-triples 13))
;Value 15: ((5 3 2) (5 4 1) (6 3 1) (7 2 1))