SICP読書録 #28 2.2.3(続き)マップのネスト - 練習問題2.41

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

マップのネスト

整数$n$が与えられたとき、$1 \leq j \le i \leq n$で、かつ$i+j$が素数となるような、$i, j$のペアを見つける、という問題を考える。

$i, j$を含む2次元ベクトルをどうにか生成する、というのがこの問題の要点となる。まずは完全なコードを示そう。

_.scm

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum-pairs n)
  (map make-pair-sum
      (filter prime-sum? (flatmap
        (lambda (i)
          (map (lambda (j) (list i j))
               (enumerate-interval 1 (- i 1))))
        (enumerate-interval 1 n)))))

prime-sum-pairs手続きにおいて、mapの中でmapを呼んでいる。このネスト構造により、多次元のベクトルを生成している。

続いて、集合を与えるとそのすべての順列を生成する手続きを作ってみる。

_.scm

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
    sequence))

(define (permutations s)
  (if (null? s)
    (list nil)
    (flatmap (lambda (x)
      (map (lambda (p) (cons x p))
        (permutations (remove x s))))
    s)))

この場合、ベクトルの次元数は集合の大きさによって決まる。map内でpermutations手続きを再起的に呼ぶことでこれを実現しているのだ。

練習問題 2.40

$1 \leq j \le i \leq n$となる整数のペア$(i, j)$を生成する手続きを作成する。

_.scm

(define (unique-pairs n)
  (flatmap
    (lambda (i)
      (map (lambda (j) (list i j))
        (enumerate-interval 1 (- i 1))))
    (enumerate-interval 1 n)))

これさえあれば、prime-sum-pairs手続きは以下のように簡単になる。

_.scm

(define (prime-sum-pairs n)
  (map make-pair-sum
    (filter prime-sum? (unique-pairs n))))

練習問題 2.41

次元をひとつ上げて、$1 \leq j \le i \le k \leq n$となる整数のトリオ$(i, j, k)$を生成する手続きを作成する。

_.scm

(define (unique-trios n)
  (flatmap
    (lambda (i)
      (map (lambda (p) (cons i p))
        (unique-pairs (- i 1))))
    (enumerate-interval 1 n)))

トリオの合計値が指定された値となるものを見つける手続きを作ってみる。

_.scm

(define (sum-trio t)
  (+ (car t) (cadr t) (caddr t)))

(define (eq-sum-trios n s)
  (filter
    (lambda (t) (= (sum-trio t) s))
    (unique-trios n)))