リスト修行 (2)

微妙。再帰から繰返しに書き換えるナニが微妙。

再度、そのサン

append シバリにチャレンジ。ってか、append の実装が先かな。

まず、引数は二つのリストで。しかも再帰。ポイントは (cons 値 リスト) なソレ。

(define (append l1 l2)
 (if (null? l1)
     l2
     (cons (car l1) (append (cdr l1) l2))))

繰り返しなナニはできるのか。

(define (append l1 l2)
 (let f ((l1 l1) (l2 l2))
   (if (null? l1)
       l2
       (cons (car l1) (append (cdr l1) l2)))))

これでは再帰。l1 を reverse して l2 に cons する位しか思い浮かばぬ。で、カンニングを。(こら

(define (append . l)
 (let f ((ls '()) (l l))
   (if (null? l)
       ls
       (let g ((ls ls))
         (if (null? ls)
             (f (car l) (cdr l))
             (cons (car ls) (g (cdr ls))))))))

このパターンって見たことあるなあ。てか、パターン的にしかプログラムが見れないわしのスキルは駄目な部類に入るな。しかも可変な引数に対応してます。
しかしこれが何故に再帰ではないのか、がナニ。ってもしかして繰返しが二重になってたら (あるいは外への脱出口があれば)、繰返しと認識されるんだろうか。

復帰

再度、_ふたつのリストを連結したリストをつくる手続きをつくってください(第4回:二をもって一となすより)_、を。

以下の解

(define (concat . l)
 (let f ((l l) (result '()))
   (if (null? l)
       result
       (let g ((ll (car l)) (result result))
         (if (null? ll)
             (f (cdr l) result)
             (g (cdr ll) (append result (list (car ll)))))))))

を、上記の append なパターンで書いてみるとこうなる。

(define (concat . l)
  (let f ((l l) (result '()))
    (if (null? l)
	result
	(let g ((result result))
	  (if (null? result)
	      (f (cdr l) (car l))
	      (cons (car result) (g (cdr result))))))))

一応、guile で確認した所では再帰ではない模様。むむむ。ってか、コードをニラんでいる内にワケワカになってきたし。

置き換えてみれば良いのかな??

(concat '(1 2) '(3 4))
 (f ((1 2) (3 4)) '()) ;; l は ((1 2) (3 4)) で retult は '()
  (g '()) ;; l は可視
   (f (3 4) (1 2))       ;; l が (3 4) result が (1 2)
    (g (1 2))
     (cons 1 (g (2)))
     (cons 1 (cons 2 (g '())))
     (cons 1 (cons 2 (f '() (3 4))))
     (cons 1 (cons 2 (3 4)))

ははー。勘違いしてた。上記 concat は内部手続き f の (null? f) が真の場合の result に最終的なリストが格納されてる、と思っていたのですがそうではないんだ。ってか、上記のナニでは無理矢理 cons の引数置き換えてるんだけど大丈夫なのかなぁ。

再度脱線

scale-list も微妙なループが可能か。以下を修正してみる。

(define (scale-list items factor)
  (let f ((l items) (n factor) (ret '()))
    (if (null? l)
	ret
	(f (cdr l) n (append ret (list (* (car l) n)))))))

最初にパターンに適当にノセてみた。以下。

(define (scale-list items factor)
  (let f ((l items) (n factor) (ret '()))
    (if (null? l)
	ret
	(let g ((ret ret))
	  (if (null? ret)
	      (f (cdr l) n (list (car l)))
	      (cons (* n (car ret)) (g (cdr ret))))))))

これを実行してみると以下のようになった。

gosh> (scale-list '(1 2 3) 3)
(3 6 3)
gosh> (scale-list '(1 2 3 4 5) 5)
(5 10 15 20 5)
gosh> 

むむ。上記の置き換えによれば ret 返却がマズい気がしますが置き換えて確認を。

(scale-list '(1 2 3) 3)
 (f '(1 2 3) 3 '())
  (g '())
   (f '(2 3) 3 '(1))
    (g '(1))
     (cons 3 (g '()))
     (cons 3 (f '(3) 3 '(2)))
     (cons 3 (g '(2)))
     (cons 3 (cons 6 (g '())))
     (cons 3 (cons 6 (f '() 3 '(3))))
     (cons 3 (cons 6 '(3)))

この手続きで作成される cons リストの末端は f な手続きが最後に返す ret になってて、最後は引数で渡されたリスト (上記の場合は '(1 2 3)) の末端要素をそのまんまナニしているから、なこその挙動と言えるな。
ってコトは f な手続きが返す ret を操作すれば良いの??

(define (scale-list items factor)
  (let f ((l items) (n factor) (ret '()))
    (if (null? l)
	(list (* (car ret) n))
	(let g ((ret ret))
	  (if (null? ret)
	      (f (cdr l) n (list (car l)))
	      (cons (* n (car ret)) (g (cdr ret))))))))

戻ってくるのはリストなんで car した値を計算しといて再度リストに戻してから返却って面倒だなぁ。とりあえず動作を確認。

gosh> (scale-list '(1 2 3) 3)
(3 6 9)
gosh> (scale-list '(1 2 3 4 5) 5)
(5 10 15 20 25)
gosh> 

動いて当然と言えば当然か。

そのヨン (再度復帰)

次。_ややこしい作りかたをされたものを、リストに直す手続きを書いてください(第4回:二をもって一となすより)_を。

例えば

gosh> (cons 1 (cons 3 5))
(1 3 . 5)
gosh> (cons (cons 3 5) 1)
((3 . 5) . 1)
gosh>

みたいなのをリストにすれば良いのか。

gosh> (tolist (cons 1 (cons 3 5)))
(1 3 5)
gosh> (tolist (cons (cons 3 5) 1))
(1 3 5)
gosh>

みたいな感じとみて、実装を検討。

まず、葉を数えあげてみる。SICP な例題を思いだしつつ、以下。

(define (leaf-count l)
  (cond ((null? l) 0)
	((not (pair? l)) 1)
	(else
	 (+ (leaf-count (car l))
	    (leaf-count (cdr l))))))

確かこんな感じだったはず。

gosh> (leaf-count (cons 1 (cons 3 5)))
3
gosh> (leaf-count (cons (cons 3 5) 1))
3
gosh> (leaf-count (list 1 2 3 4 5))
5
gosh>

多分大丈夫。(を
置き換えなナニを見てみる。

(leaf-count (list 1 2 3 4 5))
 (+ (leaf-count 1) (leaf-count '(2 3 4 5)))
 (+ 1 (leaf-count '(2 3 4 5)))
 (+ 1 (+ (leaf-count 2) (leaf-count '(3 4 5))))
 (+ 1 (+ 1 (leaf-count '(3 4 5))))
 (+ 1 (+ 1 (+ (leaf-count 3) (leaf-count '(4 5)))))
 (+ 1 (+ 1 (+ 1 (leaf-count '(4 5)))))
 (+ 1 (+ 1 (+ 1 (+ (leaf-count 4) (leaf-count '(5))))))
 (+ 1 (+ 1 (+ 1 (+ 1 (leaf-count '(5))))))
 (+ 1 (+ 1 (+ 1 (+ 1 (+ (leaf-count 5) (leaf-count '()))))))
 (+ 1 (+ 1 (+ 1 (+ 1 (+ 1 0)))))

簡単なリストを例にしてみたけど、(not (pair? l)) ん時に l を返却して、else なソレで cons すればリストになりそう。ん、null? な時は '() 返した方が良いのかな??

(define (tolist l)
  (cond ((null? l) '())
	((not (pair? l)) l)
	(else
	 (cons (tolist (car l))
	       (tolist (cdr l))))))

って駄目ぢゃん。大体がリストを元に検討してるからこんなになる訳で (以下略

gosh> (tolist (cons 1 (cons 3 5)))
(1 3 . 5)
gosh> (tolist (list 1 2 3 4 5))
(1 2 3 4 5)
gosh> (tolist (cons (cons 3 5) 1)) 
((3 . 5) . 1)
gosh> 

(cons 1 (cons 3 5)) なソレの置き換えを見た方が良さげ。

(leaf-count (cons (cons 3 5) 1))
 (+ (leaf-count '(3 . 5)) (leaf-count 1))
 (+ (leaf-count '(3 . 5)) 1)
 (+ (+ (leaf-count 3) (leaf-count 5)) 1)
 (+ (+ 1 1) 1)

むむ。append に走りそうなナニがあるんですが。

(define (tolist l)
  (cond ((null? l) '())
	((not (pair? l)) (list l))
	(else
	 (append (tolist (car l))
		 (tolist (cdr l))))))

動作を確認。

gosh> (tolist (cons 1 (cons 3 5)))
(1 3 5)
gosh> (tolist (cons (cons 3 5) 1))
(3 5 1)
gosh> (tolist '(1 2 (3 4) 5 6))
(1 2 3 4 5 6)
gosh> 

手続きの名前が微妙だけど動いてはいる。append シバリは別途で。