C# 関数型プログラミングの深層 (8) 高階関数、カリー化、ファーストクラス関数

[C# シリーズ経由の LINQ]

[C# 関数型プログラミングの詳細シリーズ]

最新バージョン:https://weblogs.asp.net/dixin/functional-csharp-higher-order-function-currying-and-first-class-function

一次関数と高次関数

高階関数は、入力として 1 つ以上の関数パラメーターを受け入れる関数、または出力として関数を返す関数です。他の関数は一次関数と呼ばれます。 C# は最初から高階関数をサポートしています。一般に、C# 関数は、ほとんどすべてのデータ型と関数型を入力型と出力型として持つことができます。ただし、以下を除きます。

  • インスタンス化できないため、System.Convert、System.Math などの静的型
  • 前述の System.Void などの特殊な型

一次関数は、入力と出力として通常のデータ値を取ることができます:

internal partial class Data { }

internal static partial class Functions
{
    internal static Data FirstOrder(Data value)
    {
        return value;
    }

    internal static void CallFirstOrder()
    {
        Data input = default;
        Data output = FirstOrder(input);
    }
}

高階関数は、上記のデータ型を関数型に置き換えることで定義できます:

internal delegate void Function();

internal static partial class Functions
{
    internal static Function NamedHigherOrder(Function value)
    {
        return value;
    }

    internal static void CallHigherOrder()
    {
        Function input = default;
        Function output = NamedHigherOrder(input);
    }
}

Above HigherOrder は名前付きの高階関数です。無名の高階関数もラムダ式で簡単に表すことができます:

internal static void LambdaHigherOrder()
{
    Action firstOrder1 = () => nameof(LambdaHigherOrder).WriteLine();
    firstOrder1(); // LambdaHigherOrder

    // (() -> void) -> void
    // Input: function of type () -> void. Output: void.
    Action<Action> higherOrder1 = action => action();
    higherOrder1(firstOrder1); // firstOrder1
    higherOrder1(() => nameof(LambdaHigherOrder).WriteLine()); // LambdaHigherOrder

    Func<int> firstOrder2 = () => 1;
    firstOrder2().WriteLine(); // 1

    // () -> (() -> int)
    // Input: none. Output: function of type () -> int.
    Func<Func<int>> higherOrder2 = () => firstOrder2;
    Func<int> output2 = higherOrder2();
    output2().WriteLine(); // 1

    // int -> (() -> int)
    // Input: value of type int. Output: function of type () -> int.
    Func<int, Func<int>> higherOrder3 = int32 =>
        (() => int32 + 1);
    Func<int> output3 = higherOrder3(1);
    output3().WriteLine(); // 2

    // (() -> void, () -> int) -> (() -> bool)
    // Input: function of type () -> void, function of type () -> int. Output: function of type () -> bool.
    Func<Action, Func<int>, Func<bool>> higherOrder4 = (action, int32Factory) =>
    {
        action();
        return () => int32Factory() > 0;
    };
    Func<bool> output4 = higherOrder4(firstOrder1, firstOrder2); // LambdaHigherOrder
    output4().WriteLine(); // True
    output4 = higherOrder4(() => nameof(LambdaHigherOrder).WriteLine(), () => 0); // LambdaHigherOrder
    output4().WriteLine(); // False
}

これらの高階関数は、IIFE 構文で定義して呼び出すことができ、関数名は関係ありません:

internal static void AnonymousHigherOrder()
{
    // (() -> void) -> void
    new Action<Action>(action => action())(
        () => nameof(AnonymousHigherOrder).WriteLine());

    // () -> (() -> int)
    Func<int> output2 = new Func<Func<int>>(() => (() => 1))();
    output2().WriteLine(); // 1

    // int -> (() -> int)
    Func<int> output3 = new Func<int, Func<int>>(int32 => (() => int32 + 1))(1);
    output3().WriteLine(); // 2

    // (() -> int, () -> string) -> (() -> bool)
    Func<bool> output4 = new Func<Action, Func<int>, Func<bool>>((action, int32Factory) =>
    {
        action();
        return () => int32Factory() > 0;
    })(() => nameof(LambdaHigherOrder).WriteLine(), () => 0);
    output4().WriteLine();
}

.NET は、Array.FindAll のような組み込みの高階関数を多数提供します:

namespace System
{
    public abstract class Array : ICollection, IEnumerable, IList, IStructuralComparable, IStructuralEquatable
    {
        public static T[] FindAll<T>(T[] array, Predicate<T> match);
    }
}

入力配列のすべての値を反復し、値ごとに一致関数を呼び出します。一致関数が true を返す場合、値が結果配列に追加されます:

internal static void FilterArray(Uri[] array)
{
    Uri[] notNull = Array.FindAll(array, uri => uri != null);
}

多くの LINQ クエリ メソッドは、前述の Where、OrderBy、Select などの高階関数です。

namespace System.Linq
{
    public static class Enumerable
    {
        public static IEnumerable<TSource> Where<TSource>(
            this IEnumerable<TSource> source, Func<TSource, bool> predicate);

        public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
            this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);

        public static IEnumerable<TResult> Select<TSource, TResult>(
            this IEnumerable<TSource> source, Func<TSource, TResult> selector);
    }
}

ここでも、LINQ クエリ メソッドについては、LINQ to Objects の章で詳しく説明します。

カレー関数

次の例では、一次関数 add2 は単純に 2 つの int 値を加算します。この関数を他の高階関数と比較してくださいhigherOrderAdd2:

internal static void FirstOrderHigherOrder()
{
    // (int, int) -> int
    Func<int, int, int> add2 = (a, b) => a + b;
    int add2Result = add2(1, 2);
    // int -> (int -> int)
    Func<int, Func<int, int>> higherOrderAdd2 = a => new Func<int, int>(b => a + b);
    Func<int, int> add1 = higherOrderAdd2(1); // Equivalent to: b => 1 + b.
    int curriedAdd2Result = add1(2);
}

(int, int) –> int 型の一次関数は簡単です。最初と 2 番目の int 値を受け入れ、それらの合計を返します。 int –> (int –> int) 型の高階関数は、最初の int 値のみを受け入れ、2 番目の int 値を受け入れて合計を返す int –> int 型の別の関数を返します。これらの関数の呼び出しも異なります。一次関数を呼び出すには、1 番目と 2 番目の int 値を指定する必要があり、結果は直接返されます。高階関数を呼び出すには、最初の int 値のみが必要であり、その int 値のクロージャーである関数を返します。次に、返された関数を呼び出すには、2 番目の int 値を指定する必要があり、結果が返されます。

実際、高階関数の場合、返される関数型は高階関数型から推測できます。したがって、次のように簡略化できます:

internal static void TypeInference()
{
    // (int, int) -> int
    Func<int, int, int> add2 = (a, b) => a + b;
    int add2Result = add2(1, 2);
    // int -> (int -> int)
    Func<int, Func<int, int>> curriedAdd2 = a => b => a + b;
    int curriedAdd2Result = curriedAdd2(1)(2);
}

これら 2 つの関数は同じアルゴリズムを表しますが、形式が異なります。 (T1, T2) –> TResult) 型の 2 アリティの 1 次関数から T1 –> (T2 –> TResult) 型の 1 アリティの高次関数へのこの種の変換は、カリー化と呼ばれます。 「カリー化」という用語は、1967 年に Christopher Strachey によって導入されました。これは、数学者で論理学者の Haskell Curry の姓です。

同様に、3 つのパラメーターを持つ次の関数は、3 つの 1 アリティ関数のシーケンスにカリー化できます。

internal static void CurryFunc()
{
    // (int, int, int) -> int
    Func<int, int, int, int> add3 = (a, b, c) => a + b + c;
    int add3Result = add3(1, 2, 3);
    // int -> int -> int -> int
    Func<int, Func<int, Func<int, int>>> curriedAdd3 = a => b => c => a + b + c;
    int curriedAdd3Result = curriedAdd3(1)(2)(3);
}

一般に、値を返す任意の N-アリティ関数は、N 個の 1-アリティ関数のシーケンスにカリー化できます:

internal static void CurryFunc<T1, T2, T3, TN, TResult>()
{
    // (T1, T2, T3, ... TN) -> TResult
    Func<T1, T2, T3, /* T4, ... */ TN, TResult> function =
        (value1, value2, value3, /* ... */ valueN) => default;
    // T1 -> T2 -> T3 -> ... TN -> TResult
    Func<T1, Func<T2, Func<T3, /* Func<T4, ... */ Func<TN, TResult> /* ... */>>> curriedFunction =
        value1 => value2 => value3 => /* value4 => ... */ valueN => default;
}

上記の変換は、すべての Func デリゲート型の次の Curry 拡張メソッドとしてラップできます:

public static partial class FuncExtensions
{
    // Transform (T1, T2) -> TResult
    // to T1 -> T2 -> TResult.
    public static Func<T1, Func<T2, TResult>> Curry<T1, T2, TResult>(
        this Func<T1, T2, TResult> function) => 
            value1 => value2 => function(value1, value2);

    // Transform (T1, T2, T3) -> TResult
    // to T1 -> T2 -> T3 -> TResult.
    public static Func<T1, Func<T2, Func<T3, TResult>>> Curry<T1, T2, T3, TResult>(
        this Func<T1, T2, T3, TResult> function) => 
            value1 => value2 => value3 => function(value1, value2, value3);

    // Transform (T1, T2, T3, T4) => TResult
    // to T1 -> T2 -> T3 -> T4 -> TResult.
    public static Func<T1, Func<T2, Func<T3, Func<T4, TResult>>>> Curry<T1, T2, T3, T4, TResult>(
        this Func<T1, T2, T3, T4, TResult> function) => 
            value1 => value2 => value3 => value4 => function(value1, value2, value3, value4);

    // ...
}

Curry メソッドを呼び出すだけで、任意の関数をカリー化できるようになりました:

internal static void CallCurry()
{
    // (int, int) -> int
    Func<int, int, int> add2 = (a, b) => a + b;
    int add2Result = add2(1, 2);
    // int -> (int -> int)
    Func<int, Func<int, int>> curriedAdd2 = add2.Curry();
    int curriedAdd2Result = curriedAdd2(1)(2);

    // (int, int, int) -> int
    Func<int, int, int, int> add3 = (a, b, c) => a + b + c;
    int add3Result = add3(1, 2, 3);
    // int -> int -> int -> int
    Func<int, Func<int, Func<int, int>>> curriedAdd3 = add3.Curry();
    int curriedAdd3Result = curriedAdd3(1)(2)(3);
}

void を返す関数もカリー化できます:

internal static void CurryAction()
{
    // (int, int) -> void
    Action<int, int> traceAdd2 = (a, b) => (a + b).WriteLine();
    traceAdd2(1, 2);
    // int -> int -> void
    Func<int, Action<int>> curriedTraceAdd2 = a => b => (a + b).WriteLine();
    curriedTraceAdd2(1)(2);

    // (int, int, int) -> void
    Action<int, int, int> traceAdd3 = (a, b, c) => (a + b + c).WriteLine();
    traceAdd3(1, 2, 3);
    // int -> int -> int -> void
    Func<int, Func<int, Action<int>>> curriedTraceAdd3 = a => b => c => (a + b + c).WriteLine();
    curriedTraceAdd3(1)(2)(3);
}

一般に、void を返す N-arity 関数は、N 個の 1-arity 関数のシーケンスにカリー化できます:

internal static void CurryAction<T1, T2, T3, TN>()
{
    // (T1, T2, T3, ... TN) -> void
    Action<T1, T2, T3, /* T4, ... */ TN> function =
        (value1, value2, value3, /* ... */ valueN) => { };
    // T1 -> T2 -> T3 -> ... TN -> void
    Func<T1, Func<T2, Func<T3, /* Func<T4, ... */ Action<TN> /* ... */>>> curriedFunction =
        value1 => value2 => value3 => /* value4 => ... */ valueN => { };
}

同様に、上記の変換は、すべてのアクション デリゲート タイプの次の Curry 拡張メソッドとしてラップできます。

public static partial class ActionExtensions
{
    // Transform (T1, T2) -> void
    // to T1 => T2 -> void.
    public static Func<T1, Action<T2>> Curry<T1, T2>(
        this Action<T1, T2> function) =>
            value1 => value2 => function(value1, value2);

    // Transform (T1, T2, T3) -> void
    // to T1 -> T2 -> T3 -> void.
    public static Func<T1, Func<T2, Action<T3>>> Curry<T1, T2, T3>(
        this Action<T1, T2, T3> function) => value1 => value2 => value3 => function(value1, value2, value3);

    // Transform (T1, T2, T3, T4) -> void
    // to T1 -> T2 -> T3 -> T4 -> void.
    public static Func<T1, Func<T2, Func<T3, Action<T4>>>> Curry<T1, T2, T3, T4>(
        this Action<T1, T2, T3, T4> function) =>
            value1 => value2 => value3 => value4 => function(value1, value2, value3, value4);

    // ...
}

ラムダ演算子の結合性

上で示したように、ラムダ式では、=> 演算子の右側に別のラムダ式がある場合、右側のラムダ式の括弧を省略できます。例:

internal static void OperatorAssociativity()
{
    // int -> (int -> int)
    Func<int, Func<int, int>> curriedAdd2 = a => (b => a + b);
    // int -> (int -> (int -> int))
    Func<int, Func<int, Func<int, int>>> curriedAdd3 = a => (b => (c => a + b + c));
}

上記の関数は、括弧なしの次の関数と同じです:

internal static void OperatorAssociativity()
{
    // int -> int -> int
    Func<int, Func<int, int>> curriedAdd2 =  a => b => a + b;
    // int -> int -> int -> int
    Func<int, Func<int, Func<int, int>>> curriedAdd3 = a => b => c => a + b + c;
}

=> 演算子を右結合として表示できるようにします。

他のいくつかの関数型言語では、関数はデフォルトでカリー化されています。たとえば、F# では、関数をカリー化として明示的に定義する必要はありません。

let curriedAdd2: int -> (int -> int) = fun a -> (fun b -> a + b)
let add1: int -> int = curriedAdd2 1
let curriedAdd2esult: int = add1 2

この関数はデフォルトでカリー化されています。上記のコードは次と同等です:

let add2: int -> int -> int = fun a b -> a + b
let add2Result: int = add2 1 2

カリー化されていない関数を明示的に定義するには、タプルを使用して一度に複数の値を渡すことができます:

let add2Tuple: int * int -> int = fun (a, b) -> a + b
let add2TupleResult = add2Tuple (1, 2) // add2Tuple(Tuple.Create(1, 2)

Haskell (Haskell Curry の最初の名前) は F# と同様に機能します:

-- curriedAdd2 :: Num a => a –> (a –> a)
curriedAdd2 = \a –> (\b -> a + b)
add1 = curriedAdd2 1
curriedAdd2Result = add1 2

-- add2 :: Num a => a -> a -> a
add2 a b = a + b
add2Result = add2 1 2

-- add2Tuple :: Num a => (a, a) -> a
add2Tuple (a, b) = a + b
add2TupleResult = add2Tuple (1, 2)

部分適用機能

1 つの引数でカリー化された関数を呼び出す (または適用する) ことは、部分適用と呼ばれます。任意の N-アリティ関数をカリー化できるため、任意の N-アリティ関数を部分的に適用することもできます:

public static partial class FuncExtensions
{
    public static Func<T2, TResult> Partial<T1, T2, TResult>(
        this Func<T1, T2, TResult> function, T1 value1) => 
            value2 => function(value1, value2);

    public static Func<T2, Func<T3, TResult>> Partial<T1, T2, T3, TResult>(
        this Func<T1, T2, T3, TResult> function, T1 value1) => 
            value2 => value3 => function(value1, value2, value3);

    public static Func<T2, Func<T3, Func<T4, TResult>>> Partial<T1, T2, T3, T4, TResult>(
        this Func<T1, T2, T3, T4, TResult> function, T1 value1) => 
            value2 => value3 => value4 => function(value1, value2, value3, value4);

    // ...
}

public static partial class ActionExtensions
{
    public static Action<T2> Partial<T1, T2>(
        this Action<T1, T2> function, T1 value1) =>
            value2 => function(value1, value2);

    public static Func<T2, Action<T3>> Partial<T1, T2, T3>(
        this Action<T1, T2, T3> function, T1 value1) =>
            value2 => value3 => function(value1, value2, value3);

    public static Func<T2, Func<T3, Action<T4>>> Partial<T1, T2, T3, T4>(
        this Action<T1, T2, T3, T4> function, T1 value1) =>
            value2 => value3 => value4 => function(value1, value2, value3, value4);

    // ...
}

例:

internal static void PartialApplication()
{
    Func<int, int, int> add2 = (a, b) => a + b;
    Func<int, int> add1 = add2.Partial(1);
    int add2Result = add1(2);

    Action<int, int> traceAdd2 = (a, b) => (a + b).WriteLine();
    Action<int> traceAdd1 = traceAdd2.Partial(1);
    traceAdd1(2);
}

関数がデフォルトでカリー化されている他の関数型言語では、関数もデフォルトで部分的に適用されます。

アンカリー関数

N 個の 1 アリティ関数のシーケンスを変換して N アリティ関数に戻すこともできます。これは uncurrying と呼ばれ、一般に Func および Action デリゲート タイプに対して次のように実装できます。

public static partial class FuncExtensions
{
    // Transform T1 -> T2 -> TResult
    // to (T1, T2) -> TResult.
    public static Func<T1, T2, TResult> Uncurry<T1, T2, TResult>(
        this Func<T1, Func<T2, TResult>> function) => 
            (value1, value2) => function(value1)(value2);

    // Transform T1 -> T2 -> T3 -> TResult
    // to (T1, T2, T3) -> TResult.
    public static Func<T1, T2, T3, TResult> Uncurry<T1, T2, T3, TResult>(
        this Func<T1, Func<T2, Func<T3, TResult>>> function) => 
            (value1, value2, value3) => function(value1)(value2)(value3);

    // Transform T1 -> T2 -> T3 -> T4 -> TResult
    // to (T1, T2, T3, T4) -> TResult.
    public static Func<T1, T2, T3, T4, TResult> Uncurry<T1, T2, T3, T4, TResult>(
        this Func<T1, Func<T2, Func<T3, Func<T4, TResult>>>> function) => 
            (value1, value2, value3, value4) => function(value1)(value2)(value3)(value4);

    // ...
}

public static partial class ActionExtensions
{
    // Transform T1 -> T2 -> void
    // to (T1, T2) -> void.
    public static Action<T1, T2> Uncurry<T1, T2>(
        this Func<T1, Action<T2>> function) => (value1, value2) =>
            function(value1)(value2);

    // Transform T1 -> T2 -> T3 -> void
    // to (T1, T2, T3) -> void.
    public static Action<T1, T2, T3> Uncurry<T1, T2, T3>(
        this Func<T1, Func<T2, Action<T3>>> function) =>
            (value1, value2, value3) => function(value1)(value2)(value3);

    // Transform T1 -> T2 -> T3 -> T4 -> void
    // to (T1, T2, T3, T4) -> void.
    public static Action<T1, T2, T3, T4> Uncurry<T1, T2, T3, T4>(
        this Func<T1, Func<T2, Func<T3, Action<T4>>>> function) =>
            (value1, value2, value3, value4) => function(value1)(value2)(value3)(value4);

    // ...
}

例:

internal static void CallUncurry()
{
    // int -> int -> int -> int
    Func<int, Func<int, Func<int, int>>> curriedAdd3 = a => (b => (c => a + b + c));
    // (int -> int -> int) -> int
    Func<int, int, int, int> add3 = curriedAdd3.Uncurry();
    int add3Result = add3(1, 2, 3);

    // int -> int -> int -> void
    Func<int, Func<int, Action<int>>> curriedTraceAdd3 = a => b => c => (a + b + c).WriteLine();
    // (int -> int -> int) -> void
    Action<int, int, int> traceAdd3 = curriedTraceAdd3.Uncurry();
    traceAdd3(1, 2, 3);
}

一級関数

示されているように、C# は関数を第一級市民として扱います。これは、C# オブジェクトと並べて比較できます。まず、オブジェクトと関数の両方に型とインスタンスがあり、インスタンスを変数に割り当て/バインドできます:

internal static partial class Functions
{
    internal static void Object()
    {
        Data value = new Data(0);
    }

    internal static void Function()
    {
        Function value1 = Function; // Named function.
        Function value2 = () => { }; // Anonymous function.
    }
}

オブジェクトと関数の両方をデータ フィールドとして保存できます:

internal static partial class Functions
{
    private static Data dataField = new Data(0);

    private static Function namedFunctionField = Function;

    private static Function anonymousFunctionField = () => { };
}

オブジェクトと関数は、関数の入力と出力の両方にすることができます:

internal static partial class Functions
{
    internal static Data Function(Data value) => value;

    internal static Function Function(Function value) => value;
}

オブジェクトと関数の両方がスコープ外のデータにアクセスできます:

internal class OuterClass
{
    const int Outer = 1;

    class AccessOuter
    {
        const int Local = 2;
        int sum = Local + Outer;
    }
}

internal static void OuterFunction()
{
    const int Outer = 1;

    void AccessOuter()
    {
        const int Local = 2;
        int sum = Local + Outer;
    }

    Function accessOuter = () =>
    {
        const int Local = 2;
        int sum = Local + Outer;
    };
}

オブジェクトと関数の両方をネストできます:

internal partial class Data
{
    internal Data Inner { get; set; }
}

internal static partial class Functions
{
    internal static void NestedObject()
    {
        Data outer = new Data(0)
        {
            Inner = new Data(1)
        };
    }

    internal static void NestedFunction()
    {
        void Outer()
        {
            void Inner() { }
        }

        Function outer = () =>
        {
            Function inner = () => { };
        };
    }
}

オブジェクトと関数はどちらも同等性テスト可能です:

internal static void ObjectEquality()
{
    Data value1;
    Data value2;
    value1 = value2 = new Data(0);
    object.ReferenceEquals(value1, value2).WriteLine(); // True
    object.Equals(value1, value2).WriteLine(); // True
    (value1 == value2).WriteLine(); // True

    value1 = new Data(1);
    value2 = new Data(1);
    object.ReferenceEquals(value1, value2).WriteLine(); // False
    object.Equals(value1, value2).WriteLine(); // True
    (value1 == value2).WriteLine(); // True
}

internal static void FunctionEquality()
{
    Function value1;
    Function value2;
    value1 = value2 = () => { };
    object.ReferenceEquals(value1, value2).WriteLine(); // True
    object.Equals(value1, value2).WriteLine(); // True
    (value1 == value2).WriteLine(); // True

    value1 = new Function(Function);
    value2 = new Function(Function);
    object.ReferenceEquals(value1, value2).WriteLine(); // False
    object.Equals(value1, value2).WriteLine(); // True
    (value1 == value2).WriteLine(); // True
}

したがって、C# にはファースト クラスの関数があります。概要は次のとおりです:

オブジェクト 機能
タイプ クラス デリゲート タイプ
インスタンス クラス インスタンス デリゲート インスタンス
変数 変数に代入可能 変数に代入可能
フィールド データ フィールドとして保存できます データ フィールドとして保存できます
入力 関数のパラメータにすることができます 高階関数のパラメータにできます
出力 関数の戻り値にすることができます 高階関数の戻り値にできる
外部変数 アクセス可能 クロージャー経由でアクセスできます
ネスト ネスト可能 ネスト可能
平等 テスト可能 テスト可能