[LINQ tramite serie C#]

[Serie di approfondimento programmazione funzionale C#]

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

Funzione di primo ordine e di ordine superiore

La funzione di ordine superiore è una funzione che accetta uno o più parametri di funzione come input o restituisce una funzione come output. Le altre funzioni sono dette funzioni del primo ordine. C# supporta la funzione di ordine superiore dall'inizio. In genere, la funzione C# può avere quasi tutti i tipi di dati e di funzione come tipi di input e tipi di output, ad eccezione di:

• Tipi statici, come System.Convert, System.Math e così via, perché non possono essere istanziati.
• Tipi speciali, come sopra menzionato System.Void.

Una funzione del primo ordine può assumere valori di dati normali come input e output:

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

Una funzione di ordine superiore può essere definita sostituendo il tipo di dati sopra con un tipo di funzione:

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 è una funzione di ordine superiore denominata. Le funzioni anonime di ordine superiore possono anche essere facilmente rappresentate con l'espressione lambda:

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
}

Queste funzioni di ordine superiore possono essere definite e chiamate con la sintassi IIFE, senza alcun nome di funzione coinvolto:

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 fornisce molte funzioni integrate di ordine superiore, come Array.FindAll:

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

Itera tutti i valori nell'array di input e chiama la funzione di corrispondenza per ogni valore. Se la funzione di corrispondenza restituisce true, il valore viene aggiunto all'array dei risultati:

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

Molti metodi di query LINQ sono funzioni di ordine superiore, come indicato in precedenza 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);
    }
}

Anche in questo caso, i metodi di query LINQ verranno discussi in dettaglio nel capitolo LINQ to Objects.

Funzione curry

Nell'esempio seguente, la funzione del primo ordine add2 aggiunge semplicemente 2 valori int. Confronta questa funzione con l'altra funzione di ordine superiore upperOrderAdd2:

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

La funzione del primo ordine di tipo (int, int) –> int è semplice. Accetta il primo e il secondo valore int e restituisce la loro somma. La funzione di ordine superiore di tipo int –> (int –> int) accetta solo il primo valore int e restituisce un'altra funzione di tipo int –> int, che accetta il secondo valore int e restituisce la somma. Anche le chiamate a queste funzioni sono diverse. Per chiamare la funzione del primo ordine è necessario fornire il primo e il secondo valore int e il risultato viene restituito direttamente. La chiamata alla funzione di ordine superiore richiede solo il primo valore int, restituisce la funzione che è una chiusura di quel valore int. Quindi, chiamare la funzione restituita richiede di fornire il secondo valore int e viene restituito il risultato.

In realtà, per la funzione di ordine superiore, il tipo di funzione restituito può essere dedotto dal tipo di funzione di ordine superiore. Quindi può essere semplificato come:

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

Queste 2 funzioni rappresentano lo stesso algoritmo ma in forma diversa. Questo tipo di trasformazione da una funzione di primo ordine a 2 arità di tipo (T1, T2) –> TResult) a una funzione di ordine superiore a 1 arità di tipo T1 –> (T2 –> TResult), è chiamato currying. Il termine "currying" è stato introdotto da Christopher Strachey nel 1967, che è il cognome del matematico e logico Haskell Curry.

Allo stesso modo, la seguente funzione con 3 parametri può essere inserita in una sequenza di 3 funzioni 1-arity:

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

In genere, qualsiasi funzione di N-arità che restituisce un valore può essere inserita in una sequenza di N funzioni di ariità 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;
}

La trasformazione precedente può essere racchiusa come i seguenti metodi di estensione Curry per tutti i tipi di delegati Func:

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

    // ...
}

Ora è possibile eseguire il curry di qualsiasi funzione semplicemente chiamando il metodo 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);
}

Anche la funzione che restituisce void può essere curata:

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

In generale, qualsiasi funzione di N-arità che restituisce void può essere inserita in una sequenza di N funzioni di ariità 1:

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

Allo stesso modo, la trasformazione precedente può essere racchiusa come i seguenti metodi di estensione Curry per tutti i tipi di delegati Action:

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

    // ...
}

Associatività operatore Lambda

Come dimostrato sopra, in un'espressione lambda, se sul lato destro dell'operatore => è presente un'altra espressione lambda, la parentesi per l'espressione lambda sul lato destro può essere omessa. Ad esempio:

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

Le funzioni precedenti sono identiche alle seguenti funzioni senza parentesi:

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

In modo che l'operatore => possa essere visto come associativo destro.

In alcuni altri linguaggi funzionali, le funzioni sono gestite per impostazione predefinita. Ad esempio, in F#, non è necessario definire esplicitamente una funzione come curried:

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

La funzione viene eseguita per impostazione predefinita. Il codice sopra è equivalente a:

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

Per definire in modo esplicito una funzione non controllata, la tupla può essere utilizzata per passare più valori contemporaneamente:

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

Haskell (che è il primo nome di Haskell Curry) funziona in modo simile a 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)

Funzione di applicazione parziale

La chiamata (o l'applicazione) di una funzione sottoposta a curry con un argomento viene chiamata applicazione parziale. Poiché qualsiasi funzione di N-arità può essere sottoposta a curry, qualsiasi funzione di N-arietà può anche essere applicata parzialmente:

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

    // ...
}

Ad esempio:

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 alcuni altri linguaggi funzionali in cui le funzioni sono gestite per impostazione predefinita, anche le funzioni sono parzialmente applicate per impostazione predefinita.

Funzione Uncurry

Una sequenza di N funzioni di ariità può anche essere riconvertita in una funzione di N-arietà. Questo è chiamato uncurrying, che può essere generalmente implementato per i tipi delegati For Func e Action come:

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

    // ...
}

Ad esempio:

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

Funzione di prima classe

Come dimostrato, C# considera la funzione come cittadino di prima classe. Questo può essere confrontato con l'oggetto C# fianco a fianco. Prima di tutto, oggetto e funzione hanno entrambi tipo e istanza e l'istanza può essere assegnata/associata a una variabile:

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

Sia l'oggetto che la funzione possono essere memorizzati come campo dati:

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

    private static Function namedFunctionField = Function;

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

Oggetto e funzione possono essere sia input che output di funzione:

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

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

Sia l'oggetto che la funzione possono accedere ai dati fuori dall'ambito:

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

Sia l'oggetto che la funzione possono essere nidificati:

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

L'oggetto e la funzione possono essere entrambi verificabili per l'uguaglianza:

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
}

Quindi C# ha funzioni di prima classe. Ecco il riassunto: