2006/12/31

整数からなるリストを、指定した自然数の正値をスタートタグ、負値をクローズタグとみなしてグループにくくりたい。ただし、そのようなグループはリストは入れ子になっているかもしれない。

ようするに、こんなふうな結果を得たい。
gosh> test-list
(2 5 3 0 9 1 9 4 -1 9 4 2 1 0 1 9 -2 -1 5 1 -1 4 -1)
gosh> (group-between test-list 1)
(2 5 3 0 9 (1 9 4 -1) 9 4 2 (1 0 (1 9 -2 -1) 5 (1 -1) 4 -1))


condでグループにくくりながら再帰が基本的な戦略だけど、入れ子になっているかもしれないので工夫が必要になる。これには、一番内側にあるグループをくくり出すという操作を、指定した数がリストの表面に見えなくなるまで再帰すればよさそう。そこで、指定した数の正値が連続したら、いったんグループわけを始めたところに戻ってやり直すようにする。そこで call/cc ですよ。←関係ない(2007/5/18追記)
(define (group-between ls n)
(define (group-most-inner ls)
(cond ((null? ls)
'())
((eq? (car ls) n)
(call/cc
(lambda (k)
(let R ((first (list (car ls)))
(rest (cdr ls)))
(cond ((null? rest)
(error "pair unmatched" n))
((eq? (car rest) (- 0 n))
(k (cons (append first (list (car rest)))
(group-most-inner (cdr rest)))))
((eq? (car rest) n)
(k (cons (car ls)
(group-most-inner (cdr ls)))))
(else
(R (append first (list (car rest)))
(cdr rest))))))))
(else
(cons (car ls)
(group-most-inner (cdr ls))))))
(cond ((not (member n ls))
ls)
(else
(group-between (group-most-inner ls) n))))
これを応用して、XMLやHTMLの文書から要素を取り出してくるのに使えそう。構造だけ欲しければsxmlにしてしまえばいいけど、元の文書の「見た目」を変えずに特定の要素だけいじるときには役立つかも。

No comments :