2011/03/03

drop して take すればリストに窓が開く

激しく時代遅れな話題ですが……
[1,2,3,4,5] が与えられたとき [[1,2][2,3][3,4][4,5]] を返すような関数を定義せよ
http://valvallow.blogspot.com/2011/02/12345-12233445.html

これは、窓をガラガラっと動かしながらリストを覗く、という問題です。ようするに、こういう話(n = 3 の場合)。
            1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
リストに窓を作るには、drop して take するのが簡単です。窓をガラガラっと動かすほうは、この問題の場合にはリストを作ることになっているので、unfold 系の高階関数を使えばよいでしょう。Scheme よりすっきり書けるので Haskell で書きます。
import Data.List (unfoldr)

overlaps n ls = unfoldr (window n) ls

window :: Int -> [a] -> Maybe ([a], [a])
window 1 _ = Nothing
window _ [] = Nothing
window _ (x:[]) = Nothing
window n ls = Just (take n ls, drop (n-1) ls)
drop の引数が n-1 なのは、窓をガラガラっとする前と後で隙間が要素1つぶんだけ重なっているという問題だからです。

Scheme も SRFI-1 に unfold があるので、ほぼ同じように「窓をガラガラっ」(drop して take した window を unfold)という気分で書けます。Gaucheだと、リストの長さの制限がゆるいバージョンの take や drop が用意されているし(take*drop*。util.list を使う)、いつのころからか unfold も組み込まれているので(最近知ったunfold組み込みはうそでした。すみません)、なおよい。
(use util.list)
(define (overlaps ls n)
(unfold exhaust? (take$ n) (drop$ (sub n)) ls))

(define (sub n) (max 1 (- n 1))
(define (exhaust? ls) (or (null? ls) (null? (cdr ls))))
(define (take$ n) (cut take* <> n))
(define (drop$ n) (cut drop* <> n))
結果として、podhmoの日記 と同じ答になりました。

そういえば、どうして Scheme の take や drop は、リストでなく整数が最後の引数になっているんだろう…?

No comments :