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 は、リストでなく整数が最後の引数になっているんだろう…？