Hatena::Grouphokudaisicp

raindrop84の日記

2009-01-04

2.43

00:52

2.42の場合
queen-colsの戻り値の要素数の回数だけenumerate-intervalを実行する
2.43の場合
enumerate-intervalの戻り値の要素数の回数だけqueen-colsを実行する

2.42

00:40


(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

;ボードの中の1マスの表現
(define (make-cell row col) (cons row col))
(define (get-row cell) (car cell))
(define (get-col cell) (cdr cell))
(define (same-cell? c1 c2)
  (and (= (get-row c1) (get-row c2))
       (= (get-col c1) (get-col c2))))

;ボード内のセルを操作する手続き
(define (add-cell board cell)
  (append board (list cell)))
(define (get-cell board col)
  (if (= (get-col (car board)) col)
      (car board)
      (get-cell (cdr board) col)))

;任意の集合に新しい場所の座標を連結する
(define (adjoin-position new-row k rest-of-queens)
  (add-cell rest-of-queens (make-cell new-row k)))

;空ボードの表現
(define empty-board '())

;k番目のクイーンが安全かどうか判断する
(define (safe? k positions)
  (define (safe-iter new-cell cells)
    (cond ((same-cell? (car cells) new-cell))
          ((= (get-row new-cell) (get-row (car cells))) #f)
          ((= (abs (- (get-row new-cell) (get-row (car cells))))
              (abs (- (get-col new-cell) (get-col (car cells))))) #f)
          (else (safe-iter new-cell (cdr cells)))))
  (safe-iter (get-cell positions k) positions))

;ボードを見やすい形式で出力する
(define (display-board board)
  (define (display-row cells row)
    (cond ((not (null? cells))
           (if (= (get-row (car cells)) row)
            (display "*")
            (display "."))
           (display-row (cdr cells) row))
          (else (newline))))
  (for-each (lambda (n) (display-row board n))
            (enumerate-interval 1 (length board))))

;ボードの集合を出力する
(define (display-board-all boards)
  (for-each (lambda (board) (display-board board) (newline)) boards))

2.40

00:33


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

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

2008-11-10

SICP1.1.7~1.2.2

16:42

1.1.7

平叙文

事実をありのままに述べる文

ここでは「それが何であるか」という記述方式

ET?

作用的順序において手続きが実行される際に,その引数は全て確定していなければならない

1.1.8

bound variable 束縛変数

bind 束縛する

scope 有効範囲

block structure ブロック構造 定義の入れ子

lexical scoping 静的有効範囲

1.2.1

recursive process 再帰プロセス

iterative process 反復的プロセス

recursive procedure 再帰的手続き 手続きが自分自身を呼ぶこと

tail recursive 末尾再帰再帰的手続きでも固定スペースで実行できる

2008-10-27

SICP1.1.1~1.1.6

00:15

1.1.1

(+ 111 222) combinations

+ operator

111,222 operands

combinationsを評価するとoperatorをoperandsに作用させた結果が得られる

1.1.3

define はSpecial forms(特殊形式)

1.1.4

手続き定義の一般形は(define (<name> <format parameters>) <body>)

1.1.5

作用的順序:引数を評価し,作用させる

正規順序:完全に展開し,簡約する

1.1.6

Special forms

cond

if

Ex.1.5

Gaucheは作用的順序で評価