(2/3) へ

C# で解く「なぜ関数プログラミングは重要か」(1/3)

2015-01-16 (鈴)

1. はじめに

約 30 年前に初稿が書かれた J. Hughes (和訳: 山下): 「なぜ関数プログラミングは重要か」[sampou.org] は,当時の Miranda [miranda.org.uk],現在の Haskell [haskell.org] がもつ関数型言語の特徴である高階関数と遅延評価の重要性をプログラム例を通して説明している。 ここでは,そこで主張された関数型言語の利点を現在の C# と LINQ が同じようにもつことをプログラム例の C# による解により実証する。

「なぜ関数プログラミングは重要か」は,当時の先進的な手続き型言語 (Modula-2, Ada) および遅延評価をしない関数型言語 (Standard ML) に対して「複雑なスコープ規則や分割コンパイルの規約は事務的な詳細でしかなく、問題を分解する新しい概念的道具をあたえるものではない」 と批判し,高階関数と組み合わせた遅延評価の利点を強調した。 これに対し LINQ は決して Miranda のような遅延評価を実現していないが,それでもそれと組み合わせた C# が Miranda などと同様に「新しい概念的道具」を与えていることを,ここで示そうと思う。

非関数型言語が遅延ストリームをライブラリとして実装しても関数プログラミングの強力さは得られない, という趣旨のことが「なぜ関数プログラミングは重要か」で主張されていると論ずる向きが最近一部で見られます。 明らかに誤読ですが,本稿によってその誤りが是正されることも期待します。

「なぜ関数プログラミングは重要か」が書かれた当時,LINQ のような遅延ストリームの実装は,確認できるかぎり,まだこの世にありませんでした。 したがって技術史的には,そもそもそうした主張がそこでなされている道理がありません。 一方,それはそれとして LINQ のメカニズムが Miranda にあるような遅延評価に匹敵するかどうかは必ずしも明らかではありません。 関数プログラミングの強力さが遅延ストリームで得られるかどうかは当時考えることができなかった新たな問題です。

LINQ が遅延評価と同等でないと示すことは簡単です。 「フィボナッチ数の計算 2: Don't say "They are lazy"」 のようにそのまま愚直に LINQ に書き写しただけでは破綻する例を与えることができます。 ここで示そうとしていることは,そういった難点を常識的な工夫で解決できるということです。

2. 「3. 関数の貼り合せ」について

「なぜ関数プログラミングは重要か」§3「関数の貼り合せ」の sum, product, anytrue, alltrue は LINQ の Aggregate メソッドで次のように書ける。 原版の reduce と同じく Aggregate は再利用できる高階関数として役立つ。

    static int sum(IEnumerable<int> seq) {
        return seq.Aggregate(0, (x, y)=> x + y);
    }

    static int product(IEnumerable<int> seq) {
        return seq.Aggregate(1, (x, y)=> x * y);
    }

    static bool anytrue(IEnumerable<bool> seq) {
        return seq.Aggregate(false, (x, y)=> x || y);
    }

    static bool alltrue(IEnumerable<bool> seq) {
        return seq.Aggregate(true, (x, y)=> x && y);
    }

doubleall と summatrix は LINQ の Select メソッドで次のように書ける。

    static IEnumerable<int> doubleall(IEnumerable<int> seq) {
        return seq.Select(n => 2 * n);
    }

    static int summatrix(IEnumerable<IEnumerable<int>> mat) {
        return sum(mat.Select(sum));
    }

IEnumerable が表現する列は,Lisp でいう car と cdr に容易に分割できるわけではありませんから,原版が reduce から map を構成したように Aggregate から Select を構成することは適切ではありません。

2.1 ラベル付き順序ツリー Tree<T>

ラベル付き順序ツリーを次のようなクラスとして表現する。 ツリーに対する簡約メソッド Reduce も与える。

    // ラベル付き順序ツリー
    class Tree<T> {
        public readonly T Label;
        public readonly IEnumerable<Tree<T>> Subtrees;

        public Tree(T x, IEnumerable<Tree<T>> y) {
            Label = x;
            Subtrees = y;
            // Console.WriteLine(" -- Tree({0}, {1})", x,
            //                   (y == null) ? 0 : y.GetHashCode()); 
        }

        public R Reduce<U, R>
            (Func<T, U, R> f, Func<IEnumerable<R>, U> g, U a) {
            if (Subtrees == null) {
                return f(Label, a);
            } else {
                IEnumerable<R> yy = Subtrees.Select(t => t.Reduce(f, g, a));
                U b = g(yy);
                return f(Label, b);
            }
        }
    }

サブツリーが空であることを表現するために Subtreesnull にすることと,Subtrees を空の IEnumerable オブジェクトにすることの二つの方法があります。

Miranda や Haskell ではいわゆる cons セルを使いますから null (nil) による表現の一択ですが,C# では IEnumerable オブジェクトを構築した結果がたまたま空の列になる場合がありますから,前者,null による方法だけに限ることは非現実的です。 一方,null を禁止して後者の表現方法だけに限ることは容易です。 実際,そうすると null に対する場合分けが不要になり,いくつかの関数定義が簡単になります。 しかし,空の列に対する処理につねに余分なコストがかかるようになります。 とりわけ LINQ の Max メソッドと Min メソッドは空の IEnumerable オブジェクトに対していちいち例外を発生させます。 ここでは効率のため,両方の表現方法を採ることにします。

このとき sumtree は次のように書ける。

    static int sumtree(Tree<int> tree) {
        return tree.Reduce((x, y)=> x + y, 
                           yy => yy.Aggregate(0, (x, y)=> x + y),
                           0);
    }

原版の redtree 関数を下記のように直訳することもできます。

    static R redtree<T, U, R>(Func<T, U, R> f, Func<U, R, U> g, U a,
                           Tree<T> tree) {
        if (tree.Subtrees == null) {
            return f(tree.Label, a);
        } else {
            U b = tree.Subtrees.Aggregate
                (a, (U x, Tree<T> t)=> g(x, redtree(f, g, a, t)));
            return f(tree.Label, b);
        }
    }

このとき sumtree は下記のように書けます。

    static int sumtree(Tree<int> tree) {
        return redtree((x, y)=> x + y, (x, y)=> x + y, 0, tree);
    }

しかし IEnumerable による列はいわゆる car と cdr の cons セルから構成されているわけではありませんから,この redtree は sumtree のような例を除き LINQ ではあまり有用ではありません。 かわりに,サブツリーを Select メソッドで処理するように工夫した Reduce メソッドを使うことにします。

redtree も Reduce も引数の型が相当に込み入っています。 「なぜ関数プログラミングは重要か」には redtree 関数の型の記述はなく C# でコンパイルが通るようにするまで多少骨が折れました。 それまで,意味がわからない!! もう少し論理的に書きなさい!! と C# コンパイラから何度も文句を言われたような気がしたものです。 一方,明示的な型の記述は,プログラムを読む人にとってその関数が何者であるかを説明する強力なコメントになりますから, この難儀は開発環境による型推論の強化と推論結果の自動展開で解決すべき問題です。

labels は補助関数 cons<T> とともに次のように書ける。 cons<T> は第1引数を yield した後,第2引数の各要素をそれぞれ yield することで,いわゆるリストの cons 関数を実現する。

    static IEnumerable<T> cons<T>(T a, IEnumerable<T> x) {
        yield return a;
        if (x != null)
            foreach (T e in x)
                yield return e;
    }

    static IEnumerable<T> labels<T>(Tree<T> tree) {
        return tree.Reduce(cons,
                           yy => yy.SelectMany(y => y),
                           (IEnumerable<T>) null);
    }

maptree は次のように書ける。

    static Tree<R> maptree<T, R>(Func<T, R> f, Tree<T> tree) {
        return tree.Reduce((x, yy) => new Tree<R>(f(x), yy),
                           yy => yy,
                           (IEnumerable<Tree<R>>) null);
    }

2.2 実行例

下記のようなテスト用の主手続きを与える。

    static void Main() {
        Console.WriteLine(sum(new int[]{1, 2, 3, 4})); // => 10
        Console.WriteLine(product(new int[]{1, 2, 3, 4})); // => 24
        Console.WriteLine(anytrue(new bool[]{false, true, false})); // => True
        Console.WriteLine(alltrue(new bool[]{false, true, false})); // => False

        Console.WriteLine(string.Join(", ",
                                      doubleall(new int[]{1, 2, 3, 4})));
        // => 2, 4, 6, 8

        Console.WriteLine(summatrix (new int[][]{
                    new int[]{1, 2, 3},
                    new int[]{4, 5, 6}})); // => 21

        var theTree = new Tree<int>(1, new Tree<int>[] {
                new Tree<int>(2, null),
                new Tree<int>(3, new Tree<int>[]{
                        new Tree<int>(4, null)
                    })
            });
        Console.WriteLine(sumtree(theTree)); // => 10
        Console.WriteLine(string.Join(", ", labels(theTree)));
        // => 1, 2, 3, 4
        Console.WriteLine(string.Join(", ", labels(maptree(x => x + 100,
                                                           theTree))));
        // => 101, 102, 103, 104
    }

Windows 7 の Cygwin 上でコンパイルして実行した例を示す。

01:~/tmp$ csc whyfp3.cs
Microsoft (R) Visual C# Compiler version 12.0.21005.1
for C# 5
Copyright (C) Microsoft Corporation. All rights reserved.

01:~/tmp$ ./whyfp3
10
24
True
False
2, 4, 6, 8
21
10
1, 2, 3, 4
101, 102, 103, 104
01:~/tmp$  

Tree<T> クラスのコメントアウトされた画面出力を生かすと,次のようにインスタンス生成を追跡できる。

01:~/tmp$ csc whyfp3.cs
Microsoft (R) Visual C# Compiler version 12.0.21005.1
for C# 5
Copyright (C) Microsoft Corporation. All rights reserved.

01:~/tmp$ ./whyfp3
10
24
True
False
2, 4, 6, 8
21
 -- Tree(2, 0)
 -- Tree(4, 0)
 -- Tree(3, 46104728)
 -- Tree(1, 12289376)
10
1, 2, 3, 4
 -- Tree(101, 43495525)
 -- Tree(102, 0)
 -- Tree(103, 55915408)
 -- Tree(104, 0)
101, 102, 103, 104
01:~/tmp$  
(2/3) へ

Copyright (c) 2015 OKI Software Co., Ltd.