SICP 読み (26)

scheme SICP

段々とハードルが高くなってきている。「写像の入れ子 (Nested Mappings)」あたりを読んでいますが、定義が前提な手続きの理解が微妙で理解に若干時間がかかる。置き換えて、なソレも時間がかかるな。
以下、微妙なメモを。
prime-some-pairs については問題があるので詳細は別途。permutations 手続きについて追い掛けてみる。

いちいち置き換えしてると微妙な世界になってきたので、なんとかして省力化なソレを模索してみる。間違えてなければ良いのですが。例としては、

(permutations '(1 2 3))

を例に考えてみる。まず手続き内にて適用されると思われるのは以下。

(flatmap (lambda (x)
	   (map (lambda (p) (cons x p))
		(permutations (remove x '(1 2 3)))))
	 '(1 2 3))

flatmap 手続きは 以下のように置き換えられる。

(accumulate append '()
	    (map (lambda (x)
		   (map (lambda (p) (cons x p))
			(permutations (remove x '(1 2 3)))))
		 '(1 2 3)))

上記の map に適用される以下の手続きは 1、2、3、'() の順に引数が渡される。

(lambda (x) (map (lambda (p) (cons x p))
		 (permutations (remove x '(1 2 3)))))

引数が 1 の場合、こうなる (2、3 の場合は略)。

(map (lambda (p) (cons 1 p))
     (permutations '(2 3)))

上記 map の引数である (permutations '(2 3)) は上記と同様、以下の形になる。

(accumulate append '()
	    (map (lambda (x)
		   (map (lambda (p) (cons x p))
			(permutations (remove x '(2 3)))))
		 '(2 3)))

上の例と同様に上記の map に適用される以下の手続きは 2、3、'() の順に (以下略

(lambda (x) (map (lambda (p) (cons x p))
		 (permutations (remove x '(2 3)))))

引数が 2 の場合、以下。

(map (lambda (p) (cons 2 p))
     (permutations '(3)))

3 の場合は以下。

(map (lambda (p) (cons 3 p))
     (permutations '(2)))

では要素が 1 しかないリストを渡された場合、permutations はどういった挙動となるか、が分かれば (permutations '(2 3)) の挙動が分かるな。

例えば (permutations '(3)) の場合は

(accumulate append '()
	    (map (lambda (x)
		   (map (lambda (p) (cons x p))
			(permutations (remove x '(3)))))
		 '(3)))

と置き換えられ、

  • x が 3 の場合
    • permutations には '() が渡されるので '() が返却
    • (cons 3 '()) が返却
  • x が '() の場合
    • 内側の map で '() が返る

で、外側の cons に上記の返却値が適用されて

(cons (cons 3 '()) '())

となるのが (permutations '(3)) の結果。

これを踏まえると以下の式は

(map (lambda (p) (cons 2 p))
     (permutations '(3)))

(permutations '(3)) が '((3)) とすると

(map (lambda (p) (cons 2 p))
     '((3)))

となって

(cons (cons 2 '(3)) '())

となる、と。同様に以下のケースは

(map (lambda (p) (cons 3 p))
     (permutations '(2)))

こうなる。

(cons (cons 3 '(2)) '())

で、上記 2、3 および '() が渡された map が返すのは以下の形になるはず。map なソレを勘案してネストを工夫してます。

(cons                         ;; map
 (cons (cons 2 '(3)) '())     ;; 引数 x が 2 の場合の戻り
 (cons 
  (cons (cons 3 '(2)) '())    ;; 引数 x が 3 の場合の戻り
  '()))                       ;; 引数 x が '() の場合の戻り

で、最終的に引数が 1 の場合の以下の処理は

(map (lambda (p) (cons 1 p))
     (permutations '(2 3)))  ;; ((2 3) (3 2))

上に倣って map なナニを勘案するとこうなるのか

(cons
 (cons 1 '(2 3))
 (cons
  (cons 1 '(3 2))
  '()))

どうもまだ map が返すナニがきちんとイメージできてない。ただ、上記の微妙な置き換えはハズしてはいないはず。

(permutations '(1 2 3)) が返すソレは以下か。(微妙

(cons
 (cons
  (cons 1 '(2 3))
  (cons
   (cons 1 '(3 2))
   '()))
 (cons
  (cons
   (cons 2 '(1 3))
   (cons
    (cons 2 '(3 1))
    '()))
  (cons
   (cons
    (cons 3 '(1 2))
    (cons
     (cons 3 '(2 1))
     '()))
   '())))

まだ cons の理解が微妙な気がする (とは言えイマサラ修行は微妙
当分ウェイトトレイニング的な置き換えによる検証が時間はかかるけど必要、という事か。いかんなぁ、頭悪い。