;;;お題
;;;与えられた文字列中の文字F,GをそれぞれF-F-F-GG,GG
;;;に変換するとして
;;;初期文字列を"F"とする時,n回の置換で得られる
;:;文字列を求めよ
;;; 0回置換 ->"F"
;;; 1回置換 ->"F-F-F-GG"
;;; 2回置換 ->"F-F-F-GG-F-F-F-GG-F-F-F-GG-GGGG"


;;;解答例
(define foo
  (lambda (s n)
	(list->string (goo (string->list s) n))))

(define goo
  (lambda (l n)
	(if (zero? n) l
	  (goo (change-fg l (lambda (x) x)) (1- n)))))


;;;補助関数
;;;とても巨大な結果になるので末尾再帰でないと
;;;時間がかかって論外.ここではcollectorを用いて
;;;末尾再帰定義としている
(define change-fg
  (lambda (l col)
	(cond
	 ((null? l) (col '()))
	 ((eq? (car l) #\F)
	  (change-fg
	   (cdr l)
	   (lambda (x)
		 (col (append (string->list "F-F-F-GG") x)))))
	 ((eq? (car l) #\G)
	  (change-fg
	   (cdr l)
	   (lambda (x)
		 (col (append (string->list "GG") x)))))
	 (else
	  (change-fg
	   (cdr l)
	   (lambda (x)
		 (col (cons (car l) x))))))))

;;;適用例
(foo "F" 0)
"F"
(foo "F" 1)
"F-F-F-GG"
(foo "F" 2)
"F-F-F-GG-F-F-F-GG-F-F-F-GG-GGGG"

;;;(foo "F" 8)はとても長い文字列(29011文字)になる
;;;ので結果文字列の表示は省略

;;;参考:(foo "F" 8)の長さを求める
(length (string->list  (foo "F" 8)))
29011