C# Linqでクイックソート

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y <- xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]

これはHaskellのコードで、良く見かける定番のQuickSort。うん、短い。というわけでLinqでそれをやる。というネタは既出のン番煎じなのですが、気にせずやる。

// LinqでHaskell風のクイックソート
public static IEnumerable<T> QuickSort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    if (!source.Any()) return source;
    var pivot = source.First();
    return source
        .GroupBy(x => x.CompareTo(pivot))
        .OrderBy(g => g.Key) // OrderBy使うのはどうかなー、というところはある
        .SelectMany(g => (g.Key == 0) ? g : QuickSort(g));
}

GroupBy->SelectManyと流れるように書けて美しいー。これならHaskellにも引けを取らないですね!但し問題なのは、OrderByを使用しているところ。CompareToの結果である-1, 0, 1を並べ替えるために使っているのだけど、OrderByの中身はシュワルツ変換の挟まったクイックソートそのものなので邪道な感は否めない。OrderBy使うなら、そもそもsource.OrderBy(x => x)でもいいぢゃん、って話になってしまう。

// 非GroupBy版。LookupはGroupByの即時評価版と考えていい。
public static IEnumerable<T> QuickSort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    if (!source.Any()) return source;
    var pivot = source.First();
    var lookup = source.ToLookup(x => x.CompareTo(pivot));
    return QuickSort(lookup[-1]).Concat(lookup[0]).Concat(QuickSort(lookup[1]));
}

GroupByをToLookupに書き変えました。ToLookupはGroupByの即時評価版といった感じで、インデクサによるアクセスが可能。インデクサ使わないでそのままforeachで列挙する、なんて時はGroupByを使った方が良いです。今回はインデクサで順番を明示的に指定するため、ToLookupでパーティション切って、Concatで繋いでやれば出来あがり。やってることが非常に分かりやすくて良い。ソースの見た目も中々綺麗じゃないでしょうか。Haskellのものとも非常に近いです(ようするに++がConcatなので) ToLookupではなくWhereを使えば、見た目は更にHaskellに近づきますが、列挙が二回になるので、ここはToLookupで。

// 普通に?書いた場合。
public static void QuickSort<T>(IList<T> source, int lowerBound, int upperBound)
    where T : IComparable<T>
{
    var pivot = source[lowerBound + ((upperBound - lowerBound) >> 1)];
    var left = lowerBound - 1;
    var right = upperBound + 1;
    while (true)
    {
        while (source[++left].CompareTo(pivot) < 0) ;
        while (source[--right].CompareTo(pivot) > 0) ;
        if (left >= right) break;
        var temp = source[left];
        source[left] = source[right];
        source[right] = temp;
    }
    if (lowerBound < left - 1) QuickSort(source, lowerBound, left - 1);
    if (right + 1 < upperBound) QuickSort(source, right + 1, upperBound);
}

今度は非Linqに一般的?な書き方で。あまりヘタな書き方するとアレだなあ、と思ったので404 Blog Not Found:javascript - Array#sortはオレquicksortより遅い by ChromeのコードをC#に移植しました。あたしこの書き方嫌いなのよね、という感じにゴチャゴチャした印象は否めないというか、まあ、嫌いなのよね。一本の配列で頑張るところが、ゆとりな私としてはしんどい。ビットシフトも嫌よね。

public static IEnumerable<T> QuickSort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    var enumerator = source.GetEnumerator();
    if (!enumerator.MoveNext()) yield break;

    var pivot = enumerator.Current;
    var less = new List<T>();
    var equal = new List<T>();
    var greater = new List<T>();
    do
    {
        switch (enumerator.Current.CompareTo(pivot))
        {
            case -1: less.Add(enumerator.Current); break;
            case 0: equal.Add(enumerator.Current); break;
            case 1: greater.Add(enumerator.Current); break;
        }
    } while (enumerator.MoveNext());

    foreach (var item in QuickSort(less)) yield return item;
    foreach (var item in equal) yield return item;
    foreach (var item in QuickSort(greater)) yield return item;
}

最後に、非Linqで、ToLookup版を再現してみたものを。do-whileがToLookupでforeachの連発がConcat。ようするに富豪的にListを作りまくるってわけなんですね!書きやすいし分かりやすいので、一本配列版よりも遥かに好き度高い。現代人はListを贅沢に大量に好きなだけ使うのです。まあ、Linq版がない状態でこの書き方が浮かぶ or 実行に移せるかどうかといったら、かなり無理ですけど。

.NET Reactive Framework メソッド探訪第五回:Scan

Microsoft Silverlight を入手

var random = new Random();
Func<byte> nextByte = () => (byte)random.Next(0, byte.MaxValue + 1);

// CenterEllipseは真ん中の円のこと。
// 1000秒以内に3回クリックするとランダムで色が変わる
// GetMultiClickScan関数が今回の主題で、解説は後で。
CenterEllipse.GetMultiClickScan(3, 1000).Subscribe(() =>
    CenterEllipse.Fill = new SolidColorBrush(Color.FromArgb(255, nextByte(), nextByte(), nextByte())));

円を1秒以内にトリプルクリックすると色が変わります。右側のログ表示はミリセカンド単位でトリプルクリック時の経過時間を表しています。つまり、これが1000以内ならば色が変わり、1000より上ならば色は変わりません。このサンプルのテーマは、トリプルクリックの検出です。トリプルだけではなく、クアドラプルでもクインタプルでも、1秒以内じゃなくて5秒でも10秒でも応用できる形で書くとしたら、どう書く? グローバル変数に、クリックイベントを格納する配列でも置くかしらん。それがきっと簡単で分かりやすくて、でも……。

今回はRx Frameworkの関数から、Scanを取り上げます。この例題は私が考えたわけではなく、Ramblings of a Lazy Coder : My solutions to the Reactive Framework Tripple-click puzzleという問題からです。URLリンク先は解答編、というわけで、この解答を解説します。

考え方としては、クリックイベントに「クリックされた時間」という情報を付加。更に、クリック回数分の「前のデータ」を参照して指定時間内で連続クリックかどうかを確認する。時間情報の付加は匿名型を作るだけなので簡単ですが、「前のデータ」を参照するのが厄介。Linqは前にしか進まないし、送られてくるデータは過去のものなど知らない。このことはReactive Frameworkだけの話ではなく、以前にもLINQで左外部自己結合Scan?という記事で書きましたが、そこで出てくる解決策がScan。そうそう、ScanはAchiralにあるので(ということでlinq.jsにもあります)、動作は分かってます。ようするにAggregateの計算過程吐きだし版です。とりあえずlinq.js ReferenceでE.Range(1,10).Scan("x,y=>x+y")と打ってみてください(宣伝宣伝)

Scanならば「一個前」の情報が手に入る。しかし「複数個前」の情報はどうすれば? 答えは配列使えばいいぢゃない。だそうです。過程のデータをとりあえず配列に入れて、次に送り出してやれば、そりゃ簡単に取り出せますね。何だか邪道な気がしますが、気にしない気にしない。URL先の解答例では生の配列を使って、インデックスをゴニャゴニャとしていて非常に正しいとは思いますが、あまり生の配列のインデックスは扱いたくないので、Queueを使ってみました。別にQueueのClear()のコストなんてたかが知れてるっしょ(中ではArray.Clearを呼んでいて、Array.Clearは……以下略)という割り切りで。

public static IObservable<MouseButtonEventArgs> GetMultiClickScan
    (this UIElement element, int count, int multiClickSpeedInMilliSeconds)
{
    return Observable.FromEvent<MouseButtonEventArgs>(element, "MouseLeftButtonDown")
        .Select(e => e.EventArgs)
        .Scan(new
        {
            Times = new Queue<DateTime>(count),
            Hit = false,
            Event = (MouseButtonEventArgs)null // ダミーなのでnullをキャストするのが楽
        }, (a, e) =>
        {
            var isHit = false;
            var now = DateTime.Now;
            a.Times.Enqueue(now);
            if (a.Times.Count == count)
            {
                var first = a.Times.Dequeue();
                Debug.WriteLine((now - first).TotalMilliseconds); // Debug
                if ((now - first).TotalMilliseconds <= multiClickSpeedInMilliSeconds)
                {
                    isHit = true;
                    a.Times.Clear();
                }
            }

            return new
            {
                Times = a.Times,
                Hit = isHit,
                Event = e
            };
        })
        .Where(a => a.Hit)
        .Select(a => a.Event);
}

ScanはAggregateと全く同じで、accumlatorのみの実行の他に、第一引数でseedを渡すこともできます。Scanのseedで、変数と判定を行うためのフラグを保持するクラスを作り、accumlatorで判定と変数の持ち越しを行い、Whereで判定をフィルタリング。このコンボは非常に強力で、幾らでも応用が効きそう。LinqでのAggregateはほとんど使われませんが、RxにおけるScanはよく見かけることになるのではないかと思います。

で、理屈は分かったけれど、何だかゴチャゴチャとしてない? という感想は否めない。ただ、グローバル領域に変数を置く必要なくフラグを閉じ込められていること、そして、応用の効きそうな柔らかさが見えたり見えなかったりしませんか? 応用的なものも、追々考えていきたいです。

次元の狭間へ

Scanが出たので、Aggregateもついでにおさらい。これはLinq to ObjectsのAggregateと変わりません。ちなみにRx Frameworkでの内部実装はScan().Last()だったりするので、Scanとほんとーに丸っきり変わりません。じゃあ、無限リピートのFromEventにたいしてAggregateって、実行するとどうなるの?というのは気になるところですが、答えは次元の狭間に入ってしまって、その行からコードが一切進まなくなります。AggregateだけじゃなくCountやLast、ToEnumerableなど全てを列挙してから答えを返す系のメソッドは全て同じ結果になります。コンソールアプリの簡単なコードで試してみると、こうなる。

class MyClass
{
    public event EventHandler<EventArgs> Ev;

    public void Fire()
    {
        Ev(this, new EventArgs());
    }
}

static void Main(string[] args)
{
    var mc = new MyClass();
    var count = Observable.FromEvent<EventArgs>(mc, "Ev")
        .Count(); // ここで次元の狭間にダイブする

    mc.Fire(); // ここに到達することは未来永劫無い
}

恐ろしや。ただ、前段階でTakeやTakeWhileを挟めば、無限リストは有限リストとなるので、面白い感じに制限が出来ます。この辺も応用例として、そのうち紹介していければと思います。

カウンター

もう一度Scanを見ます。トリプルクリックの例題は捻りすぎな感が否めないので、もっとストレートに、Scanの「前の値を保持し続けることが出来る」という点を見せる例題を一つ。クロージャの例なんかでも定番のカウンターで。

Microsoft Silverlight を入手

Observable.FromEvent<RoutedEventArgs>(CounterButton, "Click")
    .Scan(0, (x, y) => ++x)
    .Subscribe(i => CounterButton.Content = i + "Clicked");

とても簡潔で、変数が全て閉じ込められていて、綺麗……。

Linqは美人

public class Stamp
{
    public int Year { get; set; }
    public string Name { get; set; }
    public Stamp(int year, string name) { this.Year = year; this.Name = name; }
    public override string ToString() { return this.Year + ":" + this.Name; }
}

public class StampCollection : IEnumerable<Stamp>
{
    private Dictionary<string, Stamp> stamps = new Dictionary<string, Stamp>();

    public void Add(Stamp s) { stamps.Add(s.Name, s); }
    public void Add(int year, string name) { stamps.Add(name, new Stamp(year, name)); }

    // yield returnを通さなくてもそのままreturn可能
    public IEnumerator<Stamp> GetEnumerator()
    {
        return stamps.Values.OrderBy(s => s.Year).GetEnumerator();
    }

    // GetEnumeratorと名乗りながらGetEnumeratorじゃないのが少しアレですね
    public IEnumerable<Stamp> GetEnumerator2()
    {
        return stamps.Values.OrderByDescending(s => s.Year);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

// 利用時例
static void Main(string[] args)
{
    // コレクション初期化子は、複数引数時は更に{}で囲む
    var stamps = new StampCollection()
    {
        {1998, "hoge1"},
        {1999, "hoge2"},
        {2000, "hoge3"}
    };
    
    // GenericsにしておくとCast<T>を使わずLinqでコンボ出来る
    stamps.GetEnumerator2().Select(s => s.Name).ToList().ForEach(Console.WriteLine);
}

memo:C#の反復と例外 - ニート=>(vb=>..なんて無かった)=>ネトゲ屋のものを少し書き換えました。コレクション初期化子と、yield returnせずにそのまま投げ返すように変えただけですが。Linqは美人。ですです。

JavaScriptでString.Format的な超簡易テンプレート置換

// String.Format的な超簡易テンプレート置換関数
var Format = function(template, replacement)
{
    if (typeof replacement != "object") // 可変長引数時はreplacementを詰め替え
    {
        replacement = Array.prototype.slice.call(arguments, 1);
    }
    return template.replace(/\{(.+?)\}/g, function(m, c)
    {
        return (replacement[c] != null) ? replacement[c] : m
    });
}

// 例。可変長引数渡しでも配列渡しでもオブジェクト渡しでも可。
var case1 = Format("<div id={0}>{1}</div>", "あいでぃ", "要素");
var case2 = Format("<div id={0}>{1}</div>", ["あいでぃ", "要素"]);
var case3 = Format("<div id={ID}>{ELEM}</div>", { ID: "あいでぃ", ELEM: "要素" })

.NET FrameworkのString.Formatは文字を連結するのに、非常にお手軽で良いです。というわけでJavaScriptでもそれをやる。ついでにテンプレート置換風にオブジェクト渡しにも対応させる。単純な置換時は数字で、長ったらしい置換時はオブジェクトで。両方に対応させなければ、詰め替えが必要ないので正規表現でカカッと一行なんですねえ。詰め替えも別にslice.callで一発だし。以前にlinq.jsを絡めてgdgdとやってたのですが、二度もね!、あんなにgdgdやらずとも、もんのすごーく単純明快に書ける。無理やり使おうとして、無駄に複雑になるのはイクない。

と、恥ずかしくなったので今回載せました。あと、JavaScriptは文字連結面倒くせー、って時にササッとコピペで取り出して使いたい時のために(笑) ちゃんとDateTime等も含めたフォーマット変換に対応させるとか、テンプレートだったらちゃんとテンプレートエンジンな感じでforやifも動くように、とかの話は知りません。

そういえば、置換部分の関数ですけど、最初は格好つけて「return replacement[c] || m」って書いたんですが、これだとマッチがハッシュ内に見つからなかった場合(undefinedになってる)だけでなく、 空文字列の場合もfalse扱いになってしまってダメなんですね。C#の??のように使いたいのですが、例えば数字だと「var i = 0 || 3」だったら3になるしで使いづらい。というわけで、結局==nullばかり使うことになる。===undefinedって書けって話でもありますが、まあ、==nullのほうが色々考えなくて済むから楽で。

ログ吐き骨組み

Microsoft Silverlight を入手

デモ大事。Subscribeの時にConsole.WriteLine並べて、実行結果想像つきますよね、というのがいまひとつすぎたので、出力が見える骨組みを作りました。今後のReactive Frameworkの紹介時にソースコード上のDebug.WriteLineは、こーいうことなんですねー、と思ってください。毎回これ乗っけてると長ったらしいので、暗黙の、ということで。

<UserControl x:Class="SilverlightApplication4.MainPage"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation" 
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    xmlns:d="http://schemas.microsoft.com/expression/blend/2008" xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
    mc:Ignorable="d" d:DesignWidth="640" d:DesignHeight="480">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition />
            <ColumnDefinition Width="200" />
        </Grid.ColumnDefinitions>

        <StackPanel Grid.Column="0">
            <Button Name="ExecuteButton" Content="Execute" />
            <Button Name="ErrorButton" Content="Error" />
            <Button Name="ObservableButton" Content="Observable" />
            <Button Name="EnumerableButton" Content="Enumerable" />
        </StackPanel>
        <ScrollViewer Grid.Column="1">
            <TextBlock Name="LogBrowseTextBlock"></TextBlock>
        </ScrollViewer>
    </Grid>
</UserControl>
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Threading;
using System.Windows.Controls.Primitives;
using System.Reflection;

namespace SilverlightApplication4
{
    public partial class MainPage : UserControl
    {
        public MainPage()
        {
            InitializeComponent();
            Debug.Set(LogBrowseTextBlock, Dispatcher);

            ExecuteButton.GetClick().Subscribe(() =>
                Observable.Range(1, 10).Subscribe(
                    i => Debug.WriteLine(i),
                    e => Debug.WriteLine(e),
                    () => Debug.WriteLine("completed")
                )
            );

            ErrorButton.GetClick().Subscribe(() =>
                Observable.Range(1, 10)
                    .Do(i => { if (i == 5) throw new Exception(); })
                    .Subscribe(
                        i => Debug.WriteLine(i),
                        e => Debug.WriteLine("onError"),
                        () => Debug.WriteLine("onCompleted")
                    )
            );

            ObservableButton.GetClick().Subscribe(() =>
                GetMethodNames(typeof(Observable)).ToList().ForEach(s => Debug.WriteLine(s))
            );

            EnumerableButton.GetClick().Subscribe(() =>
                  GetMethodNames(typeof(Enumerable)).ToList().ForEach(s => Debug.WriteLine(s))
            );
        }

        IEnumerable<string> GetMethodNames(Type type)
        {
            return type.GetMethods(BindingFlags.Static | BindingFlags.Public)
                .Select(mi => mi.Name)
                .OrderBy(s => s)
                .Distinct();
        }
    }

    public static class Debug
    {
        private static TextBlock textBlock;
        private static Dispatcher dispatcher;

        public static void Set(TextBlock textBlock, Dispatcher dispatcher)
        {
            Debug.textBlock = textBlock;
            Debug.dispatcher = dispatcher;
        }

        public static void WriteLine(object message)
        {
            if (textBlock != null)
            {
                dispatcher.BeginInvoke(() =>
                    textBlock.Text = message.ToString() + Environment.NewLine + textBlock.Text);
            }
        }
    }

    public static class ControlExtensions
    {
        public static IObservable<Event<RoutedEventArgs>> GetClick(this ButtonBase button)
        {
            return Observable.FromEvent<RoutedEventArgs>(button, "Click");
        }
    }
}

幾ら簡易的なものだから、という言い訳がましさを考えても、かなり微妙なコードな気がする。原型はWPFでTraceListenerにTextBlockに書きだすものを追加して、Trace.WriteLineで処理していたもの。SilverlightにはTraceがなかったので、そのまま静的クラス・メソッドに置き換えて、Silverlightにも本来あるDebugを塗り替えちゃうという……。ようするにそのままコピペしても動くよね!的な感じでやりたいな、というところなわけです。ダメ?

ついでにSubscribeの中でObservableって、汚い、ように見えるかも。でも実際これはなんてことなくて、ようはJavaScriptっぽいんですよね、ほんと。DOMContentLoadedにイベント登録のaddEventListener並べるのと一緒で。じゃあ実際こうしてグチャグチャ並べるかというとそうではないようで、実際は拡張メソッドへ記述する、という形で分散していくようですが、まだまだ分からず。Microsoft側の実例やドキュメントが整ってくれないと何とも言えない感じ。

作業環境

画像クリックで原寸サイズ。最近思うところあってVisual Studioの配置をごにょごにょと弄っています。今は、こんな感じに落ち着きました。左にエラー一覧・検索など。右にソリューションエクスプローラー・クラスビュー・スタートページなど。そして左右にそれぞれコードウィンドウを分割。原則的にメインウィンドウは左。コード定義ウィンドウを右ウィンドウに開いて常時表示。もしくはXAML編集と並列したり。といったところです。コード定義ウィンドウはデカい画面で常時表示で初めて効果を発揮しますね、素晴らしく便利。

30インチ 2560x1600の無駄遣いが火を吹く!というわけですが、やっぱ広いって便利、エディタウィンドウ2面同時表示って便利、です。30インチでなくても、横2560は19インチ1280x1024のデュアルで行けます。ただ、実際はこれに加えてデバッグ時のプログラム本体なりブラウザなりを置いておく場所が欲しいので、その場合はデュアルじゃ足りないですね……。グラフィックボードが一枚でトリプルをサポートしてくれれば、というか、するべき、ですよね。ATIのEyefinityにはとても期待してます。

.NET Reactive Framework メソッド探訪第四回:メソッド一覧

前回が少し、明らかに説明不足でした……。Subscribeが原則としてIObserverを受ける(直接ラムダ式でonNextを記述するのはただの省略記法)ということは、IObserverを別に作っておける。もっと進めると、Subscribeで実行されるコード本体は自由に入れ替え可能。ということになります。ここが、イベント直記入に対するReactive Frameworkの強みの一つ。それ○○パターンだって?そうですね?その○○パターンがデフォルトで何も考えず使えるのならば、素晴らしいと思います。

では、ここからようやくメソッド探訪。の前に、全メソッド一覧を見てみます。IObservable<T>拡張メソッド一覧。そう、最初感動したのは、ドット打ってIntelliSenseに並んだこのメソッド名を見て、なのよね。いかにも素晴らしいことが出来そうな予感だったという。

Aggregate
Amb
AsObservable
Catch
CombineLatest
Concat
Cons
Contains
Count
Create
Defer
Delay
Dispatch
Do
Empty
Finally
First
FirstOrDefault
Flatten
ForkJoin
FromEvent
Generate
GetEnumerator
HoldUntilChanged
Interval
Last
LastOrDefault
Latest
Let
LetRec
LongCount
Merge
MostRecent
Never
Next
Post
Range
Reify
Repeat
Retry
Return
Sample
Scan
Select
SelectMany
Send
Single
SingleOrDefault
Skip
SkipWhile
Spawn
Start
Subscribe
Synchronize
Take
TakeWhile
Throttle
Throw
Timeout
ToAsync
ToBehavior
ToEnumerable
ToObservable
ToSubject
Until
WaitUntil
Where
Zip

かなり多い。68個ある。名前から想像つくのもあれば全くつかないものも。順番はどうしようかな、LinqではGenerating, Projection and Filtering, Join, Set, Ordering, Grouping, Aggregate, Paging, Convertで分けられたので、何らかの指針でもって分けた方が良いのは間違いないのですが、実際に中を突っつかないと何が何なのか全く分からない。

Func<Type, IEnumerable<string>> GetMethodNames = 
    type => type
        .GetMethods(BindingFlags.Static|BindingFlags.Public)
        .Select(mi => mi.Name)
        .OrderBy(s => s)
        .Distinct();

var enumerable = GetMethodNames(typeof(Enumerable));
var observable = GetMethodNames(typeof(Observable));

observable.Except(enumerable).ToList().ForEach(Console.WriteLine);

メソッド名一覧はobservableのみを吐いたもので、上のコードはEnumerableとの差分も取ってみたものです。Enumerableと重複しないものは47個でした。そんなに被ってる、というわけではないですね……。ちなみに、Enumerableは50個。覚えきれているので、もっと少ないと思ってたんですが、意外と多かった。Linq to Objectsもきちんと理解して使えるようになるのに半年ぐらいかかってしまっているので、今回も長期戦かなー。ちんたらやってる間にドキュメントが出てくるのを期待したい。

.NET Reactive Framework メソッド探訪第三回:Subscribe

メソッド探訪とか言いながら、ちっとも探訪してません。今回までが基礎知識で、Linq to Objectsで言ったらイテレータがどうこう、という段階。次回以降はメソッドを見ていきたいと思います。では、最後の予習ということで、Subscribe。SubscribeはIObservable<T>連鎖の終点となるもので(但し、別にSubscribeだけが終点というわけではない、FirstとかCountとか、終点になるものは他にもあります)ForEachのようなもの。戻り値はIDisposableで、イベント発生の監視を止めたい時はDisposeを呼ぶ。と、第一回の時に書きましたので、今回は別の方向から見ていきます。

static void Main(string[] args)
{
    Observable.Range(1, 10).Subscribe(Observer.Create(
        (int i) => Console.WriteLine(i), // OnNext
        e => { throw e; }, // OnError
        () => Console.WriteLine("Completed") // OnCompleted
    ));

    Console.ReadLine();
}

今回はコンソールアプリで。結果は想像つくとおり、1から10、最後にCompletedを表示。Observable.RangeはEnumerable.Rangeと同じです。というか中身的にはEnumerable.Range.ToObservableで変換されているだけです。RepeatとEmptyも用意されているので、ちょっとしたメソッド確認用に便利に使えると思います。それにしてもコード、ゴチャゴチャしてますねえ、わけわかんない書き方してわざと難解にやってるんじゃないだろうかって感じですが、その通りです、ので、普通の書き方も下の方でちゃんと書きます。で、SubscribeはIObservable<T>のメソッドとして定義されています。IEnumerable<T>がGetEnumeratorを持つように、IObservableはSubscribeを持つ。そして、原則Subscribeの引数はIObserver<T>です。

public interface IObservable<T>
{
    IDisposable Subscribe(IObserver<T> observer);
}

public interface IObserver<T>
{
    void OnCompleted();
    void OnError(Exception exception);
    void OnNext(T value);
}

インターフェイスなので直接生成することは出来ない。よってファクトリメソッドObserver.Createを用いて生成します。生成されるのは前回見たAnonymousEnumeratorと同じくinternalのジェネリッククラス「AnonymousObserver<T>」で、インターフェイスの各メソッドにデリゲートを直接放り込むだけの単純明快なものです。勿論、IObservable<T>を継承して自前の専用のものを用意しても構いませんが、クロージャを活かせば、自前で定義する意味など少しもありません。コンパイラの自動生成クラス任せでOK。

これの動作はメソッド名通りで、OnNextは値が来るたびに実行されるメソッド。OnCompletedは全て完了した時(FromEvent経由のものなど、実質無限リピート状態の場合は、Disposeが呼ばれた時)に実行されるメソッド。OnErrorは例外が発生した時に実行されるメソッド。発生した例外は原則catchされるので、再スローしたい時は、そのまんまですがthrow eの明示が必要です。

……それにしても面倒くさい。Observer.Createは。onNextだけが書ければいいんだよ!ってシーンにわざわざ空の式を書けとでも?(ちなみに空は()=>{}です) 大体がして、推論出来ないから(int i)だとか、型を書かなければならないのもかったるい。というわけで、拡張メソッドが用意されています。

public static IDisposable Subscribe<TSource>(this IObservable<TSource> source);
public static IDisposable Subscribe<TSource>(this IObservable<TSource> source, Action onNext);
public static IDisposable Subscribe<TSource>(this IObservable<TSource> source, Action<TSource> onNext);
public static IDisposable Subscribe<TSource>(this IObservable<TSource> source, Action onNext, Action<Exception> onError);
public static IDisposable Subscribe<TSource>(this IObservable<TSource> source, Action<TSource> onNext, Action<Exception> onError);
public static IDisposable Subscribe<TSource>(this IObservable<TSource> source, Action onNext, Action<Exception> onError, Action onCompleted);
public static IDisposable Subscribe<TSource>(this IObservable<TSource> source, Action<TSource> onNext, Action<Exception> onError, Action onCompleted);

いっぱいありますけど、ようするに無視した部分は空のメソッドが代わりに埋められる、というだけの話。これを使えば、最初の例は、onNextだけにすると

Observable.Range(1, 10).Subscribe(i => Console.WriteLine(i));

と、簡潔明快に記述出来るわけです。メデタシメデタシ。

過去記事

.NET Reactive Framework メソッド探訪第一回:FromEvent
.NET Reactive Framework メソッド探訪第二回:AnonymousEnumerable

無限リピートの幸福

Reactive Frameworkが、結構に無限リピートな感じなので、関連してC# Linqでどう書くにあった13日金曜日問題を今更書いてみた。n番煎じ。

// 今日から2013年12月31日までの、13日の金曜日とその総数を表示してください。
// 「今日」を無限リピートという方針で書いてみたりして(総数は省略)
// 利点はTodayを変数として外側に定義する必要が無くLinq内に閉じ込められる
// Toを求めるのに足したり引いたりする必要がなく自然に書ける、の二つかしらん
// 「まで」という問いに対してTakeWhileで解答するのは自然で良いと思う

Enumerable.Repeat(DateTime.Now, int.MaxValue)
    .Select((d, i) => d.AddDays(i))
    .TakeWhile(d => d.Year < 2014)
    .Where(d => (d.DayOfWeek == DayOfWeek.Friday) && (d.Day == 13))
    .ToList()
    .ForEach(d => Console.WriteLine(d.ToShortDateString()));

TakeWhileが好きです。問題文に対して、自然に解答出来るような気がするので。「今日から(Repeat)」「2013年12月31日までの(TakeWhile)」「13日の金曜日(Where)」。実に自然に記述できる。いやまあ、Repeatが直感的かというと結構微妙なところではありますが。Rangeでfrom,toのほうが自然だろ常識的に考えて、というのも確かなんですけど、Rangeだとtoを作るのに計算式が必要ってのが、ちょっと違うかな、と。

Pizza (programming language)のexampleにもあるような、Streamを始めとして何かを無限リピートしてTakeWhileで終了条件を設定、というのはパターンとして結構幅広く使える、と思う。ある種のデザインパターン。イディオムイディオム。参考リンクはC# 3.0 と while(true) と Iterator - NyaRuRuの日記この辺り。

例えばVS2010から搭載されるEnumerable.Zipや、あとCycleを定義してみる。

// この二つを混ぜ合わす(VS2010で搭載されるZip関数)
var seq1 = Enumerable.Range(1, 10);
var seq2 = Enumerable.Range(10, 10);
Enumerable.Repeat(new { e1 = seq1.GetEnumerator(), e2 = seq2.GetEnumerator() }, int.MaxValue)
    .TakeWhile(t => t.e1.MoveNext() && t.e2.MoveNext())
    .Select(t => t.e1.Current + t.e2.Current); // ここがZipのSelectorの部分
// foo,bar,hoge,foo,bar,hogeを無限に繰り返す
var elements = new[] { "foo", "bar", "hoge" };
var cycle = Enumerable.Repeat(elements, int.MaxValue).SelectMany(ar => ar);

Linqのお陰でかつてない勢いでint.MaxValueを使っているこの頃。Repeatも万能ですねえ。いやまあ、もう素直にAchiral使えよって話なんですが、標準メソッドのみで粘るのも面白くて。そういえばでついでなのでlinq.jsでもやってみた。

// JavaScriptはAddDaysがないので副作用全開でTodayを
// setHours(24)で翌日にしてしまう、という方針でやってみた

E.Repeat(new Date())
 .Do("$.setHours(24)")
 .TakeWhile("$.getFullYear() < 2014")
 .Where("$.getDay() == 5 && $.getDate() == 13")
 .ForEach("alert($)");

DoはReactive Frameworkにもありました。副作用を加えた上で素通しするメソッド。副作用は嫌なものです。汚いです。何が嫌かというと、動作を考えるのに見る範囲を広げなきゃいかんところかなあ。そしてLinqの何がいいかというと、見る範囲が物凄く限定される(ラムダ式一文だけを見ればいい)と思っている。だからLinq内でクロージャ(というか外部の変数をキャプチャして使う)もあんま好ましくないし、C#クエリ構文のletも好きじゃない。なるべくなら使いたくない。長文耐性なのは分かるけれど、カッコやインデントがなくてスマートだけれど、その分だけスコープが不明瞭になるという側面が否めない。まあ、letが必要なシチュエーションをSelectManyでやると、大抵はもっと奇怪になるのですけど。

んでまあ、この場合だとAddDaysのかわりにnew Date(year,month,day)で新しいのを作れば副作用なくSelectが使えるわけですが、ありきたりで面白くないと思ったので別な方向に走ってみた。というか、無限リピートは、無限リピートする何かに対して副作用全開で操作を加え続ける、という形の方が面白いというか実用的というか普通だとは思う。冒頭の例みたいなやつだと、別にRangeでよくね?って感じですし。Haskellじゃないんだから、潔癖症にならずに、副作用といかに楽しくお付き合いするかが大事なのですかね。

あ、ちなみに$は引数が一つの場合の省略記法です。こういった機能はScalaにもある。引数が一つのみの場合が大半なので、記述がグッと縮まるし、何よりも引数名を付ける必要がないのが嬉しい。C#でも使えるようになると嬉しいなあ、とずっと思ってるんですが中々どうして無理なんですかねえ、残念。

.NET Reactive Framework メソッド探訪第二回:AnonymousEnumerable

予定は常に変更されるもの、というわけで、今回はAnonymousEnumerableとAnonymousEnumeratorを見たいと思います。表に出てこない、internalのクラスな上に、内部でも全然使われていないので、見る必要はあんまりない。のですが、これと対になるAnonymousObservableとAnonymousObserverを見るにあたって、先に慣れ親しんだIEnumerable/Enumeratorで考えたほうが分かりやすかったので、これを先に考えます。

class AnonymousEnumerable<T> : IEnumerable<T>
{
    private Func<IEnumerator<T>> getEnumerator;
    public AnonymousEnumerable(Func<IEnumerator<T>> getEnumerator)
    {
        // 以下略
}

class AnonymousEnumerator<T> : IEnumerator<T>
{
    private Func<T> current;
    private Action dispose;
    private Func<bool> moveNext;

    public AnonymousEnumerator(Func<bool> moveNext, Func<T> current, Action dispose)
    {
        this.moveNext = moveNext;
        this.current = current;
        this.dispose = dispose;
    }

    public T Current
    {
        get { return this.current(); }
    }

    public bool MoveNext()
    {
        return this.moveNext();
    }
    
    // 以下略
}

Reflectorで見ちゃってるので、一部だけ(ライセンス!)。ただ、どれも一行なので見るまでもなく何をやってるのか想像付くと思います。 お馴染みのインターフェイスを実装しているだけですが、その実装を全てコンストラクタで受ける関数に任せています。ようするにこれはどういうことなのかというと、実例としてEnumerable.RepeatとSelectをAnonymousEnumerableで実装してみるとこうなります。

public static class Enumerable
{
    public static IEnumerable<T> Repeat<T>(T element, int count)
    {
        return new AnonymousEnumerable<T>(() =>
        {
            var index = 0;
            var current = default(T);
            return new AnonymousEnumerator<T>(
                () => // MoveNext
                {
                    if (index == 0) current = element;
                    return (index++ < count);
                },
                () => current, // Current
                () => { } // Dispose
            );
        });
    }
    
    // 実際のSelectは<TSource,TResult>ですが、都合により略
    public static IEnumerable<T> Select<T>(this IEnumerable<T> source, Func<T, T> selector)
    {
        return new AnonymousEnumerable<T>(() =>
        {
            var enumerator = source.GetEnumerator();
            return new AnonymousEnumerator<T>(
                () => enumerator.MoveNext(),
                () => selector(enumerator.Current),
                () => enumerator.Dispose()
            );
        });
    }
}

勿論、普通はyieldを使えばいいわけですが、もしyieldがなければ、こういう形で実装するのが簡潔でベスト、に見える。クロージャでコンパイラにクラス生成を任せているわけですねー。外部イテレータですが、外部のクラスに分割せず中に書けるため、すっきり分かりやすい。この発想はあったけどC#でやるという発想はなかったわ、というわけで結構感動しました。

そうそう、この仕組みはlinq.jsと丸っきり同じなのです。感動ってのは、私の基本方針は間違ってなかったんだ!の裏付けでの喜びなので不純です。そのJavaScriptでの実装はこんな感じ。

Linq.Object = function(getEnumerator)
{
    this.GetEnumerator = getEnumerator;
}

Linq.Enumerator = function(moveNext)
{
    this.Current = null;
    this.MoveNext = moveNext;
}

Repeat: function(element, count)
{
    return new Linq.Object(function()
    {
        var index = 0;
        return new Linq.Enumerator(function()
        {
            if (this.Current == null) this.Current = element;
            return (index++ < count);
        });
    });
}

Select: function(selector)
{
    var source = this;
    selector = Linq.Utils.CreateFunctor(selector);

    return new Linq.Object(function()
    {
        var enumerator = source.GetEnumerator();
        var index = 0;

        return new Linq.Enumerator(function()
        {
            if (enumerator.MoveNext())
            {
                this.Current = selector(enumerator.Current, index++);
                return true;
            }
            else
            {
                return false;
            }
        });
    });
}

スコープが若干違うかなって感じですが、大体同じです。(Linq.ObjectはLinq.Enumerableに名前変えよう……)。JavaScriptだからこそ、yieldがなくてもスッキリ定義出来る!と思っていただけに、そっかあ、そういう手を使えば良かったのかと少しショックだったりして。ほんとC#は柔軟な言語で、むしろもうJavaScriptよりもLightWeightだよ!

さて、次回はAnonymousObservableとAnonymousObserverを見てみることにします。勿論、予定は未定です。ていうかSubscribeはどうした、というと、Subscribeの中身はAnonymousObserverなので全然横道にそれてません、大丈夫です、まだ一直線です。

.NET Reactive Framework メソッド探訪第一回:FromEvent

まず、リアクティブフレームワークとは何ぞや、ということなのですが今のところInfoQ: .NETリアクティブフレームワーク(Rx)がLINQ to Eventsを可能にするの記事ぐらいしか情報はありません。.NET 4.0に含まれる(かもしれない)ということ、現在のところSilverlight Toolkitの単体テストのところにこっそりと配置されていること。それだけです。紹介も、記事中にもリンクされていますがunfold: Introducing Rx (Linq to Events)の一連の記事ぐらいしかありません。これの前文が中々に素敵です。

Buried deep in the bin folder of the Silverlight Toolkit Unit Tests is a hidden gem: The Rx Framework (System.Reactive.dll). If you glanced quickly you’d miss it altogether but it’s one of the most exciting additions to the .NET framework since Linq.

今のところ微妙にパッとしない(Parallelは簡単に使えるがゆえにインパクトが足らない)4.0の隠し玉はコレですね、間違いない。軽く触ってみたのですが、中々に感動的。Linq to Objects好きならば間違いなく琴線に触れます。C#3.0がコレクションの操作をforeachからLinqに変えてしまったように、.NET4.0はイベントもLinqに変わる。まさにLinq to Everywhere! Functional Reactive Programming!

How to use

Silverlight ToolkitをダウンロードしてSource/Binaries/System.Reactive.dllを頂けば完了。ただし、これはそのままだとSilverlightのプロジェクトでしか動作しないので、その他ので利用したい場合はここの記事に示されているように、githubに公開されているコードを実行(Cecilのdllが必要、記事文中にリンクされています)して変換する必要があります。今回はとりあえず、Silverlightで試してみたいと思います。こちらはこちらで、Silverlight 3 Toolsのダウンロードが必要ですけれど。

実例

Microsoft Silverlight を入手

マウスの動きに円が追随する、という単純なものをSilverlightで作ってみました。移動は完全に追随するのではなく、座標が15で割り切れる位置の場合のみ移動としました。スナップすることをイメージしたつもりなのですが、動きがガクガクです。これは、マウス移動に完全に追随して全ての座標でイベントが発生するわけではない = 15で割り切れる座標を通過してもイベントが発生しない場合がある = 動きがガクガク。というわけで、スナップしたい場合はWhereで間引くのではなく、Selectで近傍座標に寄せるべきです、が、いやまあ、例なので……。

// XAMLではなく全部コード上に書いたのは両方を張るのが面倒だから……
// 内容はCanvasとEllipseを配置するというもので、本筋とは関係ありません
InitializeComponent();
var canvas = new Canvas { Background = new SolidColorBrush(new Color {A=255, R = 100, G = 100, B = 100 }) };
var ellipse = new Ellipse { Height = 30, Width = 30, Fill = new SolidColorBrush(Colors.Orange) };
canvas.Children.Add(ellipse);
this.Content = canvas;

// FromEventはイベント発火がトリガとなってLinq発動
// 後段に送られるのはEvent<T>というもので、
// SenderとEventArgsという読み取り専用プロパティを持つクラス
var canvasMove = Observable.FromEvent<MouseEventArgs>(canvas, "MouseMove")
    .Select(e => e.EventArgs.GetPosition(canvas))
    .Where(p => (p.X % 15 == 0) || (p.Y % 15 == 0))
    .Subscribe(p =>
    {
        ellipse.SetValue(Canvas.LeftProperty, p.X - ellipse.Width / 2);
        ellipse.SetValue(Canvas.TopProperty, p.Y - ellipse.Height / 2);
    });

// Subscribeの戻り値の型はIDisposable
// Disposeを呼ぶと登録したイベントをデタッチすることが出来る
// デタッチしないなら取得する必要は特にはない
// canvasMove.Dispose();

MouseMoveでイベントが発火する度にLinqを通る。なるほど、イベントがリストに、見える。イベントを無限リスト生成として捉えることで、イベントに対してLinq操作が可能になった。ObserverパターンとIteratorパターンは同じだったんだよ!なんだってー!みたいなノリがある。もう少し丁寧に見ると、Observable.FromEventでイベントをPush型の無限リストに変換。戻り値はIObservable<T>。イベント発火時に後段に流れてくるのはEvent<T>。これは通常のイベント登録時に使うsenderとeventArgsをラップしただけの単純なもの。あとはIObservableに用意されているメソッド(Select, Where, TakeWhileなどお馴染みのものから、Delay, WaitUntilなどイベント用の目新しいメソッドなど多数)を繋げて、最後にSubscribe。このSubscribeは、つまり通常のイベント登録時のメソッド本文の役割を果たす。Linqで言ったらForEachのようなもの。Subscribeのオーバーロードも幾つかあるのですが、それはまた後日。

// つまるところ、以下のコードと同じだったりはする
// ただ、IObservable<T>は通常のイベント登録では無理な複雑な操作が簡単、
// そして何よりも、このような単純なコードでもそんなに複雑になっていない!
canvas.MouseMove += (sender, e) =>
{
    var pos = e.GetPosition(canvas); // Select
    if (!(pos.X % 15 == 0 || pos.Y % 15 == 0)) return; // Where
    ellipse.SetValue(Canvas.LeftProperty, pos.X - ellipse.Width / 2);
    ellipse.SetValue(Canvas.TopProperty, pos.Y - ellipse.Height / 2);
};

通常のイベント登録と対比してみると分かりやすいかしらん。FromEventではMouseEventArgsという型を明示する必要があるのがカッタルイ。推論は偉大。が、しかし、IObservableが複雑な操作が可能なのに対し、イベントに追加では直球なものしか書けない。また、複雑な操作が可能なわりには、FromEventは驚くほどシンプルに書ける。シンプルな操作でも(記述するのに)重たくない、というのは特筆すべきことじゃあないでしょうか。

// stringを避けたこういう登録方法もあるけれど、面倒なうえに警告出る
Observable.FromEvent((EventHandler<MouseEventArgs> h) => new MouseEventHandler(h),
        h => canvas.MouseMove += h, // addHandler
        h => canvas.MouseMove -= h) // removeHandler
    .Subscribe(e => Debug.WriteLine(e.EventArgs.GetPosition(canvas)));

ところで、イベント名をstringで書くのはどうよ、ていうかJavaScriptのaddEventHandlerみたいで嫌だよね?ね?リファクタリング効かないわ、IntelliSenseも動かないわでロクなことがない。というわけで、FromEventのオーバーロードを見ると、ちゃんと普通に登録する方法も用意されてはいる。一応、用意、されては、いる。が、しかし、あんまりだー。あんまりすぎるー。流れてくるEventhandler<MouseEventArgs>をMouseMoveが受け取ってくれないので、第一引数でMouseEventHandlerに変換する(ところで警告が消せないのですが、警告無しで処理する方法ってあるのかしらん)。あとは、addとremoveの登録。長ったらすぎてこれはダメぽ。確かに、こんなんなら、stringでいいです……。

Microsoft Silverlight を入手

// 普段あまり書かないMouseEventArgsとかいう型定義は書きにくいし
// メソッド名もstringで書くのはミスが出がち、ということで
// 拡張メソッドでイベント取り出し用のメソッドを予め作っておくと良い
public static IObservable<Event<MouseEventArgs>> GetMouseMove(this UIElement elem)
{
    return Observable.FromEvent<MouseEventArgs>(elem, "MouseMove");
}

// マウスの軌跡を1秒後に描画します
canvas.GetMouseMove()
    .Select(e => e.EventArgs.GetPosition(canvas))
    .Delay(1000)
    .Subscribe(p =>Dispatcher.BeginInvoke(()=>
    {
        ellipse.SetValue(Canvas.LeftProperty, p.X - ellipse.Width / 2);
        ellipse.SetValue(Canvas.TopProperty, p.Y - ellipse.Height / 2);
    }));

汚い部分は隔離!ということで、拡張メソッドに退避してやると、美しく書ける。いやまあ、この辺は全部unfold: The Joy of Rx: Extension Eventsに書いてあることなのですけど。んで、デモ的にもう少し面白げがあったほうがいいかな、と思ったのでDelayを足してみました。1秒後にマウス移動の軌跡を描画します。グルグルーっとマウス動かして止めてみてください。スムーズ、とは言い難いですね、しょんぼり。記述も、Delayを足すだけ。と言いたかったんですがBeginInvokeかあ、これどーにかなる方法ないかなあ。

次回

全10回ぐらいで、全部のメソッドを紹介するつもりです。私が理解できればの話ですが。ちょこちょこと実例的なものも交えていきたいと思います。私が使いこなせればの話ですが。というわけで、次回はSubscribeのオーバーロードの紹介にしたいと思います。Reactive Frameworkならではの魅力、に関してはもう少し先になってしまいそう。少し飛ばして、非同期連結の話なんかを先に持ってきた方が良いかなあ。

Profile

Yoshifumi Kawai

Cysharp, Inc
CEO/CTO

Microsoft MVP for Developer Technologies(C#)
April 2011
|
July 2024

Twitter:@neuecc GitHub:neuecc

Archive