Foldr funkce v C#

go to english version »

Znáte Foldr? Foldr je funkce, kterou najdeme ve většině funkcionálních jazycích jako je například Haskell (Foldr) či F# (List.Fold_r). Jedná se o velice užitečnou funkci pokud potřebujete zpracovat jednotlivé prvky pole a vrátit jako jeden výsledek (ne pole). Takovým příkladem by mohlo být například sečtení všech čísel v poli.

Foldr není součástí .NET frameworku! Implementaci této funkce najdete na konci tohoto článku.

Funkce Foldr má 3 parametry, první je zpracovávané pole (list), pak defaultní hodnota (def), která je použita jako poslední prvek pole a funkce (fun), která je volána na každé dva sousední prvky pole.

forma:          Foldr ( list, def, fun )

Jak to tedy funguje? Řekněme, že potřebujete sečíst všechna čísla v poli…

Teorie

forma:          Foldr (  list,                 def,  fun )
kód:            Foldr ( { 1,   2,   3,   4 },  0,    + )
sečtení:                  1 + (2 + (3 + (4 +   0)))      = 10

Foldr v C#

V C# sečtení všech prvků bude vypadat následovně:



    int[] list = { 1, 2, 3, 4 };
    int result = List.Foldr<int, int>(list, 0, (x, y) => x + y);


    // T is int (elements in list are int) and R is int (return value is int)
    // result: 10

U Foldr funkce musím určit datové typy vstupních prvků (T) a výsledku (R)

List.Foldr<T, R>( … )

Příklady

Vynásobení elementů v poli s použitím Foldr funkce vypadá následovně:


    int[] list = { 1, 2, 3, 4 };
    int result = List.Foldr<int, int>(list, 0, (x, y) => x * y);

    // result: 24

A velice jednoduše můžeme také například vypsat všechny prvky pole:


    int[] list = { 1, 2, 3, 4 };
    string result = List.Foldr<int, string>(list, "", (x, y) => x.ToString() + "," + y);

    // result: “1,2,3,4,”

Implementace Foldr

namespace System.Collections
{
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// List functions
    /// </summary>
    public static class List
    {
        public delegate R FoldHandler<T, R>(T item, R items);

        /// <summary>
        /// Implementation of classic Foldr function popular in functional languages
        /// </summary>
        /// <typeparam name="T">Type of items in the list</typeparam>
        /// <typeparam name="R">Return type</typeparam>
        /// <param name="list">List of items those will be processed</param>
        /// <param name="default_">Default value</param>
        /// <param name="f">Function applied to every two adjacent elements of list</param>
        /// <returns>Foldr result</returns>
        public static R Foldr<T, R>(IEnumerable<T> list, R defaultValue, FoldHandler<T, R> fun)
        {
            // last item
            if (list.Count() == 0) return defaultValue;

            // recursion
            return fun(list.First(), Foldr(list.Skip(1), defaultValue, fun));
        }
    }
}

Leave a Reply