Foldr in C#

Do you know Foldr? Foldr is a function we can find in most of functional programming languages like Haskell (Foldr) or F# (List.Fold_r). It is useful when you need to process all elements in a list and return just one result value (not list), such as ’sum all numbers in a list’.

Foldr is not part of .NET framework, implementation of this function you can find at the end of this article.

Foldr takes list of elements (list), default value (def) which behaves like a last value of the list and function (fun) which is applied to every two adjacent elements.

form:           Foldr ( list, def, fun )

How does it work? Let’s say you need to sum all elements in the list…

Theory

form:           Foldr (  list,                 def,  fun )
code:           Foldr ( { 1,   2,   3,   4 },  0,    + )
execution:                1 + (2 + (3 + (4 +   0)))      = 10

Foldr in C#

In C# our sum sample looks like this:



    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

In C#, we have to define generic types of input elements (T) and return type (R)

List.Foldr<T, R>( … )

Examples

Multiply elements in the list


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

    // result: 24

Print elements in the list


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

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

Implementation of 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