読者です 読者をやめる 読者になる 読者になる

ToLookup<TKey,TElement> の基本と応用

.NET

ネタもと『どうでもいいコードの断片 - プログラマブルな趣味、もっぱらスクリプティング』.
ツボにはまればとっても便利な ToLookup.でもちょっと知名度低いかもしれない.
例えばこんなコード.

using System;
using System.Linq;
using System.IO;

static class Program
{
    static void Main(string[] args)
    {
        // ファイルリスト
        var fileNames = new[]
        {
            "200.xls",
            "100.doc",
            "300.ppt",
            "500.xls",
            "400.ppt",
            "600.ppt"
        };

        // 拡張子からファイルリストへのルックアップテーブルを作成
        var extToFiles = fileNames.ToLookup(f => Path.GetExtension(f));

        // 拡張子 ".xls" を持つファイル名を表示
        extToFiles[".xls"].ToList().ForEach(Console.WriteLine);

        // 拡張子 ".js" を持つファイル名を表示
        extToFiles[".js"].ToList().ForEach(Console.WriteLine);
    }
}

ILookup<TKey,TElement> って何?

ToList や ToArray,ToDictionary は今までも対応するコンテナがあったからまあ分かる.でも ToLookup が返す Lookup<TKey, TElement> ってコンテナは何? という人は IDictionary<TKey, IEnumerable<TElement>> の便利版と考えればとりあえず OK.

ILookup<string, int> lookup = ...

// インデクサにキーを与えると対応する IEnumerable<T> が返る
IEnumerable<int> q1 = lookup["Key1"];
IEnumerable<int> q2 = lookup["Key2"];

IDictionary<TKey, IEnumerable<TElement>> と比べてどこが便利かというと,存在しないキーについて空のシーケンスを返してくれるところ.

// 存在しないキーについては空シーケンスが返り,例外は起きない
IEnumerable<int> q2 = lookup["not existing key"];
Assert.AreEqual(0, q2.Count());

存在しないキーに空シーケンスを返すと何がうれしいの?

この挙動はパイプラインを連結していったときに真価を発揮する.

// 以下のようなコードで key の存在チェックが不要になる
List<string> list = ...

list.Select(key => lookup[key])
    .Select(q => q.Count());

list.SelectMany(key => lookup[key])
    .ForEach(Console.WriteLine);

どんなときに使うの?

データベースによる階層構造表現.ありがちな隣接リストモデルでたとえばこんなのを考えてみる.

Element Parent
"Object" null
"MarshalByRefObject" "Object"
"Stream" "MarshalByRefObject"
"BufferedStream" "Stream"
"FileStream" "Stream"
"IsolatedStorageFileStream" "FileStream"
"MemoryStream" "Stream"
"UnmanagedMemoryStream" "Stream"
"CryptoStream" "Stream"
"PipeStream" "Stream"
"AnonymousPipeServerStream" "PipeStream"
"AnonymousPipeClientStream" "PipeStream"
"NamedPipeServerStream" "PipeStream"
"NamedPipeClientStream" "PipeStream"

階層ツリーを親の方向にたどるのは簡単.要素名は Unique ということにして,ある要素の階層の親をたどるには再帰的に Parent 列の項目をたどっていけば OK.でも Root から子方向に全部たどるのはこのままだと分かりにくいね,と.
そこで Parent をキーにして "ToLookup" してみる.

  • Object
    • MarshalByRefObject
  • MarshalByRefObject
    • Stream
  • Stream
    • BufferedStream
    • FileStream
    • MemoryStream
    • UnmanagedMemoryStream
    • CryptoStream
    • PipeStream
  • FileStream
    • IsolatedStorageFileStream
  • PipeStream
    • AnonymousPipeServerStream
    • AnonymousPipeClientStream
    • NamedPipeServerStream
    • NamedPipeClientStream

これは親が同じ要素同士でテーブルを分割したのに相当する.最近の Explorer や Outlook の表示形態で「グループ化」ってのがあるけど,あれと同じ.
まず子要素を列挙して,列挙された子要素をキーとすれば今度は孫要素が列挙できる.こうして,ある要素にぶら下がった要素を全て列挙できる.

隣接リストモデルから ToLookup

まず C# 3.0 でテーブル定義.

var table = new []
{
    new {Element="Object", Parent=default(string)},
    new {Element="MarshalByRefObject", Parent="Object"},
    new {Element="Stream", Parent="MarshalByRefObject"},
    new {Element="BufferedStream", Parent="Stream"},
    new {Element="FileStream", Parent="Stream"},
    new {Element="IsolatedStorageFileStream", Parent="FileStream"},
    new {Element="MemoryStream", Parent="Stream"},
    new {Element="UnmanagedMemoryStream", Parent="Stream"},
    new {Element="CryptoStream", Parent="Stream"},
    new {Element="PipeStream", Parent="Stream"},
    new {Element="AnonymousPipeServerStream", Parent="PipeStream"},
    new {Element="AnonymousPipeClientStream", Parent="PipeStream"},
    new {Element="NamedPipeServerStream", Parent="PipeStream"},
    new {Element="NamedPipeClientStream", Parent="PipeStream"},
};

ToLookup を使ってルックアップテーブルに変換.

var lookup = table.Where(item => item.Parent != null)
                  .ToLookup(item => item.Parent, item => item.Element);

Parent が null のものを抜いておくのがこつ.ToLookup のオーバーロードもいくつかある
いったんルックアップテーブルができればあとは簡単.

// "Object" の子要素を列挙
lookup["Object"].ForEach(s => Console.WriteLine(s));

// "Object" の孫要素を列挙
lookup["Object"].SelectMany(item => lookup[item])
                .ForEach(s => Console.WriteLine(s));

// "Object" のひ孫素を列挙
lookup["Object"].SelectMany(item => lookup[item])
                .SelectMany(item => lookup[item])
                .ForEach(s => Console.WriteLine(s));

Lookup を利用した再帰を一発で書く

先日公開した Achiral では CascadeDepthFirst / CascadeBreadthFirst という Extension Method が用意してあって,先ほどの SelectMany の繰り返しを再帰的に行ってくれる.色々な型を "Extension" しているので,書き方も色々.

// Func<T, IEnumerable<T>>.CascadeDepthFirst(T initial)
var q1 = Make.Func((string item) => lookup[item])
             .CascadeDepthFirst("Object");

// ILookup<T, T>.CascadeDepthFirst(T initial)
var q2 = lookup.CascadeDepthFirst("Object");

// IEnumerable<T>.CascadeDepthFirst(ILookup<T, T> lookup)
var q3 = Make.Sequence("Object")
             .CascadeDepthFirst(lookup);

// IEnumerable<T>.CascadeDepthFirst(Func<T, IEnumerable<T>> func)
var q4 = Make.Sequence("Object")
             .CascadeDepthFirst(item => lookup[item]);

// IEnumerable<T>.CascadeDepthFirst(Func<T, IEnumerable<T>> func,
//                                  Func<T, int, TResult> selector)
var q5 = Make.Sequence("Object")
             .CascadeDepthFirst(item => lookup[item],
                                (item, nestLevel) => item);

実際に Reflection で mscorlib.dll と System.Core.dll に含まれる type-tree を書いてみる.ルートを System.IO.Stream として,それ以下のものを列挙.

using System;
using System.Linq;
using System.IO;

using Achiral;
using Achiral.Extension;

static class Program
{
    static void Main(string[] args)
    {
        // mscorlib.dll と System.Core.dll に含まれる全ての型
        var types = Enumerable.Concat(
                        typeof(int).Assembly.GetTypes(),
                        typeof(Enumerable).Assembly.GetTypes());

        var childrenLookup = types.Where(type => type.BaseType != null)
                                  .ToLookup(type => type.BaseType, type => type);

        childrenLookup.CascadeDepthFirst(typeof(Stream), (Type, NestLevel) => new { Type, NestLevel } )
                      .ConsoleWriteLine(item => new string(' ', 3 * item.NestLevel) + item.Type.FullName);
    }
}

実装についてはソースコードをどうぞ.

便利な ToLookup を追加する

Achiral では他にも ILookup を作るための拡張メソッドをサポートしている.
一番使い勝手が良いのが,IDictionary<TKey, IEnumerable<TResult>> から ILookup<TKey, TResult> を作る拡張メソッド.

using Achiral;
using Achiral.Extension;

var lookup = new Dictionary<string, IEnumerable<string>>
             {
                 { "Object", new []{"MarshalByRefObject"} },
                 { "MarshalByRefObject", new []{"Stream"} },
                 { "Stream", new []{"BufferedStream", "FileStream"} },
                 { "FileStream", new []{"IsolatedStorageFileStream"} },
             }.ToLookup();

このほか,IDictionary<TKey, Func<IEnumerable<TResult>>> から ILookup<TKey, TResult> への ToLookup も追加してある.

using Achiral;
using Achiral.Extension;

var lookup = new Dictionary<string, Func<IEnumerable<object>>>
             {
                 { "Once", () => Enumerable.Repeat(new object(), 1) },
                 { "Twice", () => Enumerable.Repeat(new object(), 2) },
                 { "Infinite", () => Make.Repeat(new object()) },
             }.ToLookup();

これで階層的な構造のデータソースも比較的楽に取り扱えるようになる,かもしれない.