[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# にはファースト クラスの関数があります。概要は次のとおりです:
オブジェクト | 機能 | |
タイプ | クラス | デリゲート タイプ |
インスタンス | クラス インスタンス | デリゲート インスタンス |
変数 | 変数に代入可能 | 変数に代入可能 |
フィールド | データ フィールドとして保存できます | データ フィールドとして保存できます |
入力 | 関数のパラメータにすることができます | 高階関数のパラメータにできます |
出力 | 関数の戻り値にすることができます | 高階関数の戻り値にできる |
外部変数 | アクセス可能 | クロージャー経由でアクセスできます |
ネスト | ネスト可能 | ネスト可能 |
平等 | テスト可能 | テスト可能 |