前後の値も利用したシーケンス処理 - NyaRuRuが地球にいたころ

// 連続して同じ値が来る箇所だけを省いて取得する
// この場合だと1,2,4,3,4,0が取れることを目指す
int[] array = { 1, 2, 4, 4, 3, 3, 4, 0, 0 };

シーケンス中で連続して同じ値が入っている各箇所について，2 個目以降は削除したシーケンスが欲しい，という問題．
割とこういう単純な問題でも，入社試験とかで「んじゃホワイトボードに書いてみて」なると案外焦ってミスったりするんですよね．って面接でプログラムを書いたことが数回しかない自分のような人間が適当に言ってるだけですが．
まあそれはさておき，現実のプログラミングで見かける以下のような問題，「シーケンス処理で前後の値も使ってほげふが」という点では同系統と見なすことができるんじゃないかと思います．

MIDI 規格のランニングステータスで省略されているステータスバイトを復元する
毎月の売り上げデータから，先月比で売り上げが下がっている月を探す
2 行続いた空行がデータの終わりを表すので，その 2 行の手前までを変数に格納する

この手の問題を解くのに for / while ループは見飽きてるでしょうから，別の方法を 2 つほど．

リスト処理関数を使う

LINQ でさまざまなリスト処理関数*1が追加されましたが，汎用的なリスト処理関数の組み合わせで「前後の値も利用したシーケンス処理」を行うことが出来ます．例えば TakeWhile や SkipWhile などは何かと便利ですね．
この他に前後の値を利用するのに便利な関数としては，F# で言うところの Seq.pairwise があります．このリスト処理関数は，N 個のシーケンスを，隣接するデータのペアのシーケンス tuple × (N - 1) 個に変換してくれます．C# で書くとこんな感じ．

public static IEnumerable<Tuple<T,T>> Pairwise<T>(this IEnumerable<T> source)
{
    //AssertNonNullArgument(source, "source");

    using (var enumerator = source.GetEnumerator())
    {
        if (!enumerator.MoveNext())
        {
            yield break;
        }
        var prev = enumerator.Current;
        while (enumerator.MoveNext())
        {
            yield return new Tuple<T,T>(prev, enumerator.Current);
            prev = enumerator.Current;
        }
    }
}

より汎用的な関数として，Scan (F# で言うところの Seq.scan) を事前に定義しておけば，Scan を使って Pairwise 相当のものを書くこともできます．
source を 2 回列挙する副作用がない，あるいはそれが無視できる場合には，source.Skip(1) と source を ZipWith で結合しても Pairwise の代わりになるでしょう．そういえば .NET Framework 4.0 では，Zip と Tuple が入るそうですね．
んで話を戻して，Pairwise を使うと「毎月の売り上げデータから，先月比で売り上げが下がっている月を探す」とか「連続で空行が来たら停止」みたいなのは割と簡単に書けることがあります．でも，データ数が 1 のときの扱いでやっぱり注意が必要だったり，最初の問題のように不確定な個数のデータが連続してやってくる場合には使えないこともあったり．そこまで万能でもない子かもしれません．端っこの情報が必要なときは，Scan のようなもう少し汎用的な関数に戻る必要がありそうです．

パターン言語 + 置換

最初の問題を文字列に置き換えてみましょう．つまり，文字列 "12433400" 中の連続する文字をひとつにまとめ，結果として文字列 "124340" を得る，とします．これは以下のように書けます．

var result = Regex.Replace(@"12433400", @"(.)\1+", @"$1");
// 結果: "124340"

この方法は一旦文字列化を行うため，例えば負数や 10 以上の数字に対してはそのままでは使えません．前方参照とか先読みとか戻り読みとか，折角強力なパターン記述能力を持ちながら，文字列にしか使えない世の多くの正規表現ライブラリはやっぱり勿体ないんじゃないかと思います．
C++ なら，『boost xpressive で数列に対する文法を作る - NyaRuRuの日記』のように，boost xpressive を使うことで，任意の int 型のシーケンスに対して同じような置換動作を定義できそうです．さらに文字の切り替わりをトークンの区切りとみたてることで，Lazy に列挙することもできそうな感じですね (regex_token_iterator)．
ついでにここ数ヶ月の心の友，Mathematica でも解いてみます．ここでは ReplaceRepeated を使ってみました．

{1, 2, 4, 4, 3, 3, 4, 0, 0} //. {a___, x_, x_, b___} -> {a, x, b}
(* 結果: {1, 2, 4, 3, 4, 0} *)

{1, 1, 1, 1, 1} //. {a___, x_, x_, b___} -> {a, x, b}
(* 結果: {1} *)

2 個連続した数値を 1 個にまとめるという処理を，結果が変わらなくなるまで何度も適用しています．N 個 (N > 1) の連続した数値を一気にキャプチャしたければ，以下の方法でも OK です (結果は同じ)．

{1, 2, 4, 4, 3, 3, 4, 0, 0} //. {a___, Longest[Repeated[x_, {2, Infinity}]], b___} -> {a, x, b}
(* 結果: {1, 2, 4, 3, 4, 0} *)

{1, 1, 1, 1, 1} //. {a___, Longest[Repeated[x_, {2, Infinity}]], b___} -> {a, x, b}
(* 結果: {1} *)

とまあこんな感じで，「次のデータをチラ見して」/「さっきのデータを憶えておいて」という頻出問題も，見方を変えればリスト処理関数として汎用化したり，かなりコンパクトなパターン言語に落とし込めたりするケースもありやなしやというお話でした．
もっとも，言語指定がありがちなお仕事プログラミングや入社試験でこんな手が使えるかどうかは微妙です．Loop が平常心と共にあらんことを．

おまけ: Mathematica のサイトライセンス

大学生/大学院生で Mathematica に興味があるけど持ってないという人は，いちど大学の IP アドレスから以下のページを見てみると良いかも．

http://www.wolfram.com/siteinfo/

更新履歴

2009年3月12日
- サブセクションを「Pairwise を使う」から「リスト処理関数を使う」に変更
  - これに伴い本文修正

*1:ここではシーケンスの意味でリストと呼んでいます