読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

subs, interleave

Gauche

珠玉のリスト・プログラミング」で,3つの問題が出題されています。
Schemeを勉強中なので,挑戦してみようと思います。自己流で書いているので,書き方でまずいところがたくさんあると思います。lisperの方々のコメントがいただければ幸いです。

まず,1問目はこんな問題です。

  • 与えられたリストのすべての部分リストを生成する関数 subs

以下のように作ってみました。

subs.scm

(define subs
  (lambda (lst)
    (cond
     ((null? lst) '(()))
     (else
      (append (subs (cdr lst))
              (helper-subs (car lst) (subs (cdr lst))))))))

(define helper-subs
  (lambda (x lst)
    (cond
     ((null? (cdr lst))
      (cons (cons x (car lst)) '()))
     (else
      (cons (cons x (car lst))
            (helper-subs x (cdr lst)))))))

実行結果です。

gosh> (subs '(3))
(() (3))
gosh> (subs '(2 3))
(() (3) (2) (2 3))
gosh> (subs '(1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

なんとか動いているようです。

2問目は,こんな問題です。

  • 第一引数を第二引数のリストへ挿入したすべてのリストを生成する関数 interleave

以下のように作ってみました。

interleave.scm

(define interleave
  (lambda (x lst)
    (cond
     ((null? lst) (cons (cons x '()) '()))
     (else
      (cons
       (cons x lst)
       (helper-interleave (car lst) (interleave x (cdr lst))))))))

(define helper-interleave
  (lambda (x lst)
    (cond
     ((null? (cdr lst))
      (cons (cons x (car lst)) '()))
     (else
      (cons (cons x (car lst))
            (helper-interleave x (cdr lst)))))))

実行してみます。

gosh> (interleave '1 '())
((1))
gosh> (interleave '1 '(4))
((1 4) (4 1))
gosh> (interleave '1 '(3 4))
((1 3 . #0=(4)) (3 1 . #0#) (3 4 1))

できたと思いきや…,最後の実行例は間違っています。机上でトレースするとうまくいくような気がするのですが…。どうすればいいんだろう?
ちなみに,関数helper-interleaveは,以下のような動作をする関数です。

gosh> (helper-interleave '3 '((1 4) (4 1)))
((3 1 4) (3 4 1))

追記(2008/12/12)

上記の件で,shiroさんにコメントいただきました。ありがとうございます。自分で作ったinterleaveが間違っていないことが分かってうれしいです。益々,Schemeが好きになってきました(^^)。

gosh> (write (interleave '1 '(3 4)))
((1 3 4) (3 1 4) (3 4 1))#<undef>
gosh> (write (interleave '1 '(2 3 4)))
((1 2 3 4) (2 1 3 4) (2 3 1 4) (2 3 4 1))#<undef>

追記(2008/12/12)

  • 3つめの問題を解きました。ここです。