練習問題 (4)
相当グダグダ迷走しております。ちょっと微妙。
練習問題 2.9.6 (行儀の良いリストなら #t そうでなければ #f を返却する list? の定義)
実行例が出ている
guile> (list? '()) #t guile> (list? '(1 2 3)) #t guile> (list? '(a . b)) #f guile> (list? (let ((ls (cons 'a '()))) (set-cdr! ls ls) ls)) #f guile>
まず、circular なソレは除外で実装を検討。
リストについて自分の中で整理できていないので検討が相当迷走している。眠いのも手伝ってグダグダな下書きがコンピュータ上に残置されていて、朝イチ見たときゃヘコんだ。詳細については略しますが、現時点も含めてリソース消費しスギ。
リストの整理もしたいんですが、ツリーのマンガをどう書くか、とゆーのも微妙。とりあえず、迷走しまくった挙句に出した結論として「全ての部分リストの cdr 端が部分リストか空リスト」なのが行儀の良いリストとしとく。
ので、とりあえずリストの末端をなぞるコードから考えた方が良いかんじ。
(define (p x)
(display x)
(newline))
(define (traverse l)
(if (not (pair? l))
(p l)
(begin
(traverse (car l))
(traverse (cdr l)))))一応なぞれてはいますが、使いモノにはならんな。これって末尾再帰なナニにはできんの??
(define (traverse l)
(let f ((l l))
(if (not (pair? l))
(p l)
(begin
(f (car l))
(f (cdr l))))))む。動いとるな。begin ってなんか微妙。なんとかならんか。
(define (traverse l)
(let f ((l l))
(if (not (pair? l))
(p l)
(let ((l (car l)) (r (cdr l)))
(f l)
(f r)))))うーん。出力がネストしてくれたらシアワセだなぁ。リスト整理用のナニに使えそ。
(define (disp x lv)
(let f ((x x) (lv lv))
(if (zero? lv)
((lambda ()
(display x)
(newline)))
(let ((lv lv))
(display "|")
(f x (- lv 1))))))
(define (traverse l)
(let f ((l l) (lv 0))
(if (not (pair? l))
(disp l lv)
(let ((l (car l)) (r (cdr l)))
(f l (+ lv 1))
(f r (+ lv 1))))))まずい。課題を離れて現実トウヒしてんぞ。(駄目
紆余曲折の後に
げ。難しく考えスギだった。_「全ての部分リストの cdr 端が部分リストか空リスト」なのが行儀の良いリストとしとく_ってダウトじゃないか。(とほほほ
末端ペアの cdr が空リストだったらセーフなのかよ。てことは
guile> (list? '((a . b) c)) #t guile>
ああそうですか。丸一日頭を痛めたのが全部ムダでーす。使った時間は 1 日近い。
# と書いた時点でメモ (グダグダな下書き) を全部消去。(鬱
えーと末端の部分リストの cdr が空リストだったら #t 返しゃいいの??なんかだんだんハラ立ってきたし。それ以前に渡された引数が空リストだったら #t な。
(define (my-list? l)
(if (null? l)
#t
#f ;; 今から書く
))あとは cdr し続けて pair じゃなくなって空リストじゃなかったら #f か。
(define (my-list? l)
(if (null? l)
#t
(let f ((l l))
(if (pair? l)
(f (cdr l))
(null? l)))))とほほほ。試験。
guile> (my-list? '()) #t guile> (my-list? '(a b c)) #t guile> (my-list? '(a . b)) #f guile>
ちゃんと仕様は確認しようね、な見本デース。
circular なチェックはスルーします。進捗悪いし。(自己嫌悪
