[LINQ via C#-Reihe]

[Eingehende Serie zur funktionalen Programmierung in C#]

Neueste Version:https://weblogs.asp.net/dixin/functional-csharp-higher-order-function-currying-and-first-class-function

Funktion erster und höherer Ordnung

Eine Funktion höherer Ordnung ist eine Funktion, die einen oder mehrere Funktionsparameter als Eingabe akzeptiert oder eine Funktion als Ausgabe zurückgibt. Die anderen Funktionen werden als Funktionen erster Ordnung bezeichnet. C# unterstützt von Anfang an Funktionen höherer Ordnung. Im Allgemeinen kann eine C#-Funktion fast jeden Datentyp und Funktionstyp als Eingabetyp und Ausgabetyp haben, außer:

• Statische Typen wie System.Convert, System.Math usw., da sie nicht instanziiert werden können.
• Spezielle Typen, wie das oben erwähnte System.Void.

Eine Funktion erster Ordnung kann normale Datenwerte als Eingabe und Ausgabe annehmen:

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);
    }
}

Eine Funktion höherer Ordnung kann definiert werden, indem der obige Datentyp durch einen Funktionstyp ersetzt wird:

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);
    }
}

Oben HigherOrder ist eine benannte Funktion höherer Ordnung. Anonyme Funktionen höherer Ordnung können auch einfach mit dem Lambda-Ausdruck dargestellt werden:

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
}

Diese Funktionen höherer Ordnung können mit IIFE-Syntax definiert und aufgerufen werden, ohne dass ein Funktionsname beteiligt ist:

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 bietet viele eingebaute Funktionen höherer Ordnung, wie Array.FindAll:

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

Es iteriert alle Werte im Eingabearray und ruft die Match-Funktion für jeden Wert auf. Wenn die Match-Funktion wahr zurückgibt, wird der Wert zum Ergebnis-Array hinzugefügt:

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

Viele LINQ-Abfragemethoden sind Funktionen höherer Ordnung, wie die oben erwähnten 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);
    }
}

Auch hier werden LINQ-Abfragemethoden ausführlich im Kapitel LINQ to Objects besprochen.

Curry-Funktion

Im folgenden Beispiel addiert die Funktion erster Ordnung add2 einfach 2 int-Werte. Vergleichen Sie diese Funktion mit der anderen höherwertigen Funktion 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);
}

Die Funktion erster Ordnung vom Typ (int, int) –> int ist unkompliziert. Es akzeptiert den ersten und den zweiten int-Wert und gibt ihre Summe zurück. Die Funktion höherer Ordnung vom Typ int –> (int –> int) akzeptiert nur den ersten int-Wert und gibt eine andere Funktion vom Typ int –> int zurück, die den zweiten int-Wert akzeptiert und die Summe zurückgibt. Der Aufruf dieser Funktionen ist ebenfalls unterschiedlich. Der Aufruf der Funktion erster Ordnung erfordert die Bereitstellung des ersten und zweiten int-Werts, und das Ergebnis wird direkt zurückgegeben. Das Aufrufen der Funktion höherer Ordnung erfordert nur den ersten int-Wert, sie gibt eine Funktion zurück, die eine Schließung dieses int-Werts ist. Dann erfordert der Aufruf der zurückgegebenen Funktion die Bereitstellung des zweiten int-Werts, und das Ergebnis wird zurückgegeben.

Tatsächlich kann der zurückgegebene Funktionstyp für die Funktion höherer Ordnung der von dem Funktionstyp höherer Ordnung abgeleitete sein. Es kann also vereinfacht werden als:

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);
}

Diese 2 Funktionen stellen denselben Algorithmus dar, jedoch in unterschiedlicher Form. Diese Art der Transformation von einer 2-stelligen Funktion erster Ordnung vom Typ (T1, T2) –> TResult) in eine 1-stellige Funktion höherer Ordnung vom Typ T1 –> (T2 –> TResult), wird Currying genannt. Der Begriff "Currying" wurde 1967 von Christopher Strachey eingeführt, der der Nachname des Mathematikers und Logikers Haskell Curry ist.

In ähnlicher Weise kann die folgende Funktion mit 3 Parametern in eine Folge von 3 1-stelligen Funktionen umgewandelt werden:

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);
}

Im Allgemeinen kann jede N-stellige Funktion, die einen Wert zurückgibt, in eine Folge von N 1-stelligen Funktionen umgewandelt werden:

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;
}

Die obige Transformation kann als die folgenden Curry-Erweiterungsmethoden für alle Func-Delegattypen verpackt werden:

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);

    // ...
}

Jetzt kann jede Funktion durch Aufrufen der Curry-Methode kuriert werden:

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);
}

Die Funktion, die void zurückgibt, kann auch kuriert werden:

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);
}

Im Allgemeinen kann jede N-stellige Funktion, die void zurückgibt, in eine Folge von N 1-stelligen Funktionen umgewandelt werden:

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 => { };
}

Auf ähnliche Weise kann die obige Transformation als die folgenden Curry-Erweiterungsmethoden für alle Action-Delegattypen verpackt werden:

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);

    // ...
}

Lambda-Operator-Assoziativität

Wie oben gezeigt, kann in einem Lambda-Ausdruck, wenn auf der rechten Seite des Operators => ein weiterer Lambda-Ausdruck vorhanden ist, die Klammer für den Lambda-Ausdruck auf der rechten Seite weggelassen werden. Zum Beispiel:

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));
}

Die obigen Funktionen sind identisch mit den folgenden Funktionen ohne Klammern:

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;
}

Damit der =>-Operator als rechtsassoziativ angesehen werden kann.

In einigen anderen funktionalen Sprachen werden Funktionen standardmäßig kuriert. Beispielsweise ist es in F# nicht erforderlich, eine Funktion explizit als Curry zu definieren:

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

Die Funktion ist standardmäßig curry. Der obige Code entspricht:

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

Um eine uncurried-Funktion explizit zu definieren, kann ein Tupel verwendet werden, um mehrere Werte gleichzeitig zu übergeben:

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

Haskell (das ist der Vorname von Haskell Curry) funktioniert ähnlich wie 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)

Teilanwendungsfunktion

Das Aufrufen (oder Anwenden) einer Curry-Funktion mit einem Argument wird als partielle Anwendung bezeichnet. Da jede N-stellige Funktion kuriert werden kann, kann jede N-stellige Funktion auch partiell angewendet werden:

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);

    // ...
}

Zum Beispiel:

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);
}

In einigen anderen funktionalen Sprachen, in denen Funktionen standardmäßig Curry sind, werden Funktionen teilweise auch standardmäßig angewendet.

Uncurry-Funktion

Eine Folge von N 1-stelligen Funktionen kann auch in eine N-stellige Funktion zurücktransformiert werden. Dies wird als „uncurrying“ bezeichnet und kann im Allgemeinen für die Delegate-Typen „Func“ und „Action“ wie folgt implementiert werden:

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);

    // ...
}

Zum Beispiel:

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);
}

Erstklassige Funktion

Wie gezeigt, behandelt C# die Funktion als Bürger erster Klasse. Dies kann mit C#-Objekt nebeneinander verglichen werden. Zunächst einmal haben Objekt und Funktion beide Typ und Instanz, und Instanz kann an Variable zugewiesen/gebunden werden:

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.
    }
}

Objekt und Funktion können beide als Datenfeld gespeichert werden:

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

    private static Function namedFunctionField = Function;

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

Objekt und Funktion können sowohl Ein- als auch Ausgang der Funktion sein:

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

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

Objekt und Funktion können beide auf Daten außerhalb des Geltungsbereichs zugreifen:

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;
    };
}

Objekt und Funktion können beide verschachtelt werden:

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 = () => { };
        };
    }
}

Objekt und Funktion können beide auf Gleichheit testbar sein:

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# hat also erstklassige Funktionen. Hier ist die Zusammenfassung: