リスト修行

scheme

リストのナニが微妙なので練習問題が出ているサイトを探してきちんと取り組む事に。

そのイチ

まず最初は3. リストを作ろうより。
cons で以下の表示となるナニを作成せよ、との事。

  1.  ("hi" . "everybody")
  2. (0)
  3. (1 10 . 100)
  4. (1 10 100)
  5. (#\I "saw" 3 "girls")
  6. ("Sum of" (1 2 3 4) "is" 10)

では、まず机上にて。

gosh> (cons "hi" "everybody")
("hi" . "everybody")
gosh> (cons 0 '())
(0)
gosh> (cons 1 (cons 10 100))
(1 10 . 100)
gosh> (cons 1 (cons 10 (cons 100 '())))
(1 10 100)
gosh> (cons #\I (cons "saw" (cons 3 (cons "girls" '()))))
(#\I "saw" 3 "girls")
gosh> (cons "Sum of" (cons (cons 1 (cons 2 (cons 3 (cons 4 '()))))
(cons "is" (cons 10 '()))))
("Sum of" (1 2 3 4) "is" 10)
gosh>

あまりきちんと検証してません。これで駄目ならもっとちゃんとヤる。(違

gosh> (cons "hi" "everybody")
("hi" . "everybody")
gosh> (cons 0 '())
(0)
gosh> (cons 1 (cons 10 100))
(1 10 . 100)
gosh> (cons 1 (cons 10 (cons 100 '())))
(1 10 100)
gosh> (cons #\I (cons "saw" (cons 3 (cons "girls" '()))))
(#\I "saw" 3 "girls")
gosh> (cons "Sum of" (cons (cons 1 (cons 2 (cons 3 (cons 4 '()))))
(cons "is" (cons 10 '()))))
("Sum of" (1 2 3 4) "is" 10)
gosh>

ヨシ。(何

そのニ

次。値は何か、と。

  1. (car '(0))
  2. (cdr '(0))
  3. (car '((1 2 3) (4 5 6)))
  4. (cdr '(1 2 3 . 4))
  5. (cdr (cons 3 (cons 2 (cons 1 '()))))

机上検討なソレは以下。

gosh> (car '(0))
0
gosh> (cdr '(0))
()
gosh> (car '((1 2 3) (4 5 6)))
(1 2 3)
gosh> (cdr '(1 2 3 . 4))
(2 3 . 4)
gosh> (cdr (cons 3 (cons 2 (cons 1 '()))))
(2 1)
gosh>

これも直感的に書いてます。実際に評価させたらどうなるのか。

gosh> (car '(0))
0
gosh> (cdr '(0))
()
gosh> (car '((1 2 3) (4 5 6)))
(1 2 3)
gosh> (cdr '(1 2 3 . 4))
(2 3 . 4)
gosh> (cdr (cons 3 (cons 2 (cons 1 '()))))
(2 1)
gosh>

なんかどきどきするなぁ。前回のエントリでぼけ過ぎてて自分が信用できん。

そのサン

次はここ (第4回: 二をもって一となす)より。
まず_リストの長さを調べる手続きをつくってください(第4回:二をもって一となすより)_との事。

SICP にもあった気がするがカンニングはなしで。

(define (len l)
 (let f ((l l) (result 0))
   (if (null? l)
       result
       (f (cdr l) (+ 1 result)))))

動くかな。

gosh> (len '(1 2 3 4 5))
5
gosh> (len '())
0
gosh> (len '(1 2 3 (4 5) 6))
5
gosh>

とりあえず OK ってコトで。(を

次は_リストのn番目の要素をとりだす手続きをつくってください(第4回:二をもって一となすより)_、と。

こんな感じか。

gosh> (nth '(1 2 3 4 5) 3)
3
gosh>

以下に定義を。

(define (nth lst n)
 (define (checkng? n)
   (cond ((= n 0) #t)
         ((< (length lst) n) #t)
         (else #f)))
 (if (checkng? n)
     (error "out of range")
     (let f ((l lst) (n (- n 1)))
       (if (= n 0)
           (car l)
           (f (cdr l) (- n 1))))))

チェックしなくても良かったかなぁ。

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

(define (concat l1 l2)
 (append l1 l2))

これじゃアレだな。

(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 シバリって無理かな。
# ちなみに g には result 渡さんと駄目なのかな。駄目か。

ちょっと脱線

とは言え、cons と list と append について。
帰宅中のバス内にて、飛ばし気味に読んだ 2.2.1 のあたりを再読。リストに値を cons は可能、という事が分かる (今さら)。

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

あるいはリスト操作な手続きのヒナガタとして、リストの写像、な項にある scale-list な手続きは参考になる。

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
	    (scale-list (cdr items) factor))))

なんか、これに関する練習問題をやったのはつい最近だな。反復なソレに置き換えてみよう。

(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)))))))

むむ。append か。