SICP 読み (27)

scheme SICP

このあたりはスデに未知の領域です。なんと言えば良いのかは分かりませんが、表現力が凄いな、と。

問題 2.40

一式を以下に。

(define (filter predicate sequence)
  (cond ((null? sequence) '())
	((predicate (car sequence))
	 (cons (car sequence)
	       (filter predicate (cdr sequence))))
	(else
	 (filter predicate (cdr sequence)))))

(define (accumulate op init seq)
  (if (null? seq)
      init
      (op (car seq)
	  (accumulate op init (cdr seq)))))

(define (enumulate-interval low high)
  (if (> low high)
      '()
      (cons low (enumulate-interval (+ low 1) high))))

(define (unique-pair n)
  (accumulate append '()
	      (map (lambda (i)
		     (map (lambda (j) (list i j))
			  (enumulate-interval 1 (- i 1))))
		   (enumulate-interval 1 n))))

(define (square n)
  (* n n))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
	((divides? test-divisor n) test-divisor)
	(else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

(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? (unique-pair n))))

問題 2.41

これも解のみ。解は若干微妙な感じ。もっと良い方法がありそげ、と言いますか。

(define (filter predicate sequence)
  (cond ((null? sequence) '())
	((predicate (car sequence))
	 (cons (car sequence)
	       (filter predicate (cdr sequence))))
	(else
	 (filter predicate (cdr sequence)))))

(define (accumulate op init seq)
  (if (null? seq)
      init
      (op (car seq)
	  (accumulate op init (cdr seq)))))

(define (enumulate-interval low high)
  (if (> low high)
      '()
      (cons low (enumulate-interval (+ low 1) high))))

(define (unique-trio n)
  (accumulate append '()
	      (map (lambda (i)
		     (map (lambda (j)
			    (map (lambda (k) (list i j k))
				 (enumulate-interval 1 (- j 1))))
			  (enumulate-interval 1 (- i 1))))
		   (enumulate-interval 1 n))))

(define (ans n s)
  (filter (lambda (x) (= s (+ (car x) (cadr x) (caddr x))))
	  (accumulate append '() (unique-trio n))))

問題 2.42

safe? の良さげな実装を思いつかない。試験ドリブンで書いた方が良さげな感じもする。

追記

と言いつつ動きはした。
何点かポイントを以下に。

  • empty-board は通常のパターンであれば '() なんですが、何故にマスクされているのか、と思っていたら (queen-cols 0) が '() を返してしまうと flatmap な map が動かなくっていきなり終わるからなんですね (机上では気がつかなかった)。adjoin-position では末端に append すんだろな、という適当な読みを根拠に '(()) を (queen-cols 0) が返却する事にする。
  • で、adjoin-position で '(()) に append するのはダウトだから k を渡さねぇといけないんだな、と思いつつスルーしていた。
  • safe? はもっとスマートな実装が可能なはず。

で、最終的に手入力な試験では safe? も動いているのに () から 1 は引けんぞ、みたいなメセジを残してオチてまして、相当悩んだ挙句に guile で trace かけたら原因が判明。

adjoin-position にて '(()) に append してたんで

(() 1 1)

みたいなリストになっていて、が原因だった。

メモのコメントには (append '(()) 1) とか無問題、とか書いていて、かなりナサケ無い気持ちになってしまいました。(とほほほ

2.43 もコードをぱっと見て、どうなる、という事が類推できれば良いのでしょうが、リストやら再帰やらにまだ慣れていないのか、すぐにイメージできん。疲労困憊のせいだけではない事は確かではないか、と。