Foldables in C#, F#, and TypeScript

Foldable.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace funsharp
{
    // Demo data class
    internal class Blarg
    {
        private readonly double _d;
        private readonly long _i;
        private readonly string _s;

        public Blarg(long i, double d, string s)
        {
            _i = i;
            _d = d;
            _s = s;
        }

        public override string ToString()
        {
            return string.Format("i: {0}, d: {1}, s: {2}", _i, _d, _s);
        }
    }

    internal static class Extensions
    {
        // Function composition
        // f.Compose(g)(x) == g(f(x))
        public static Func<TA, TC> Compose<TA, TB, TC>(
            this Func<TA, TB> f,
            Func<TB, TC> g)
        {
            return x => g(f(x));
        }

        // Flip arguments of a function
        // f.Flip()(b, a) == f(a, b)
        public static Func<TB, TA, TC> Flip<TA, TB, TC>(this Func<TA, TB, TC> fn)
        {
            return (b, a) => fn(a, b);
        }

        // Apply for folds in a natural order
        public static IFold<TA, Tuple<TX, TY>, TC> Apply<TA, TB, TX, TY, TC>(
            this IFold<TA, TY, Func<TB, TC>> fst,
            IFold<TA, TX, TB> snd)
        {
            return snd.Apply(fst);
        }

        // Bridge enumerables to foldables
        public static IFoldable<T> ToFoldable<T>(this IEnumerable<T> source)
        {
            return new EnumerableFoldable<T>(source);
        }

        // Fold a foldable using the given fold
        public static TB Fold<TA, TX, TB>(this IFoldable<TA> foldable, IFold<TA, TX, TB> fold)
        {
            return fold.Fold(foldable);
        }

        // Curry a 2-arity function
        public static Func<TA, Func<TB, TC>> Curry<TA, TB, TC>(this Func<TA, TB, TC> fn)
        {
            return a => b => fn(a, b);
        }

        // Curry a 3-arity function
        public static Func<TA, Func<TB, Func<TC, TD>>> Curry<TA, TB, TC, TD>(
            this Func<TA, TB, TC, TD> fn)
        {
            return a => b => c => fn(a, b, c);
        }
    }

    // Adapter for enumerables to foldables
    internal class EnumerableFoldable<T> : IFoldable<T>
    {
        private readonly IEnumerable<T> _source;

        public EnumerableFoldable(IEnumerable<T> source)
        {
            _source = source;
        }

        public TFolded Fold<TFolded>(TFolded seed, Func<T, TFolded, TFolded> fn)
        {
            return _source.Aggregate(seed, fn.Flip());
        }
    }

    internal class Program
    {
        private const int Size = 100000;
        private const int NumRuns = 1000;

        public static readonly IFold<long, long, long> LongSum =
            new FoldImpl<long, long, long>(0L, (x, y) => x + y, Id);

        public static readonly IFold<long, double, double> DoubleProduct =
            new FoldImpl<long, double, double>(1, (x, y) => x * y, Id);

        // Internal field to fool the compiler into not removing otherwise
        // unused locals
        // ReSharper disable once NotAccessedField.Local
        private static object _stash;

        public static IFold<long, StringBuilder, string> StringConcat()
        {
            return new FoldImpl<long, StringBuilder, string>(new StringBuilder(),
                                                             (i, builder) => builder.Append(i),
                                                             builder => builder.ToString());
        }

        // Identity function
        // ReSharper disable once MethodNamesNotMeaningful
        public static T Id<T>(T t)
        {
            return t;
        }

        // Blarg data object constructor function
        public static Func<long, double, string, Blarg> BlargMaker()
        {
            return (i, d, s) => new Blarg(i, d, s);
        }

        // Fold using applicative notion
        private static void CombinedFold()
        {
            var foldable = Enumerable.Range(1, Size).Select(a => (long) a).ToList().ToFoldable();
            var fold = LongSum.Select(BlargMaker().Curry()).
                               Apply(DoubleProduct).
                               Apply(StringConcat());
            var folded = foldable.Fold(fold);
            _stash = folded.ToString();
        }

        // Fold using separate available aggregations
        private static void SeparateFolds()
        {
            var foldable = Enumerable.Range(1, Size).Select(a => (long) a).ToList();
            var longSum = foldable.Sum();
            var doubleProduct = foldable.Aggregate(1d, (x, y) => x * y);
            var stringConcat = foldable.Aggregate(new StringBuilder(),
                                                  (builder, i) => builder.Append(i));
            var folded = BlargMaker()(longSum, doubleProduct, stringConcat.ToString());
            _stash = folded.ToString();
        }

        // Fold using a simple custom loop
        private static void CustomLoop()
        {
            var foldable = Enumerable.Range(1, Size).Select(a => (long) a).ToList();
            var longSum = 0L;
            var doubleProduct = 1d;
            var stringConcat = new StringBuilder();

            foreach (var a in foldable)
            {
                longSum += a;
                doubleProduct *= a;
                stringConcat.Append(a);
            }

            var folded = BlargMaker()(longSum, doubleProduct, stringConcat.ToString());
            _stash = folded.ToString();
        }

        // Benchmarking helper
        private static TimeSpan RunTimed(Action block)
        {
            var watch = new Stopwatch();

            watch.Start();

            for (var i = 0; i < NumRuns; i++)
            {
                block();
            }

            watch.Stop();

            return watch.Elapsed;
        }

        private static string FormatResult(string name, TimeSpan time)
        {
            return String.Format(
                "{0}, {1} runs: total {2}ms, per run {3}ms",
                name, NumRuns, time.TotalMilliseconds,
                TimeSpan.FromTicks(time.Ticks / NumRuns));
        }

        // ReSharper disable once UnusedParameter.Local
        private static void Main(string[] args)
        {
            var combinedFolds = RunTimed(CombinedFold);
            var separateFolds = RunTimed(SeparateFolds);
            var customLoop = RunTimed(CustomLoop);

            Console.WriteLine(FormatResult("Combined folds", combinedFolds));
            Console.WriteLine(FormatResult("Separate folds", separateFolds));
            Console.WriteLine(FormatResult("Custom loop", customLoop));

            Console.ReadKey();
        }
    }

    /// <summary>
    ///     An interface to allow reducing a container to a single element using
    ///     an accumulator function.
    /// </summary>
    /// <typeparam name="TFoldable">The type of objects in the container</typeparam>
    internal interface IFoldable<out TFoldable>
    {
        TFolded Fold<TFolded>(TFolded seed, Func<TFoldable, TFolded, TFolded> fn);
    }

    /// <summary>
    ///     A generalized fold for folding foldable objects.
    /// </summary>
    /// <typeparam name="TA">The type of value to fold</typeparam>
    /// <typeparam name="TX">The type of the accumulator</typeparam>
    /// <typeparam name="TB">The result of the folding operation</typeparam>
    internal interface IFold<TA, TX, out TB>
    {
        // Fold a foldable using this fold
        TB Fold(IFoldable<TA> foldable);

        // (<$>), map a function over the fold
        IFold<TA, TX, TC> Select<TC>(Func<TB, TC> fn);

        // (<*>), applicative instance function
        // Arguments are reversed to allow type-safe implementation at all
        // TC can also be another curried Func<TIn, TOut> to allow further
        // chaining
        IFold<TA, Tuple<TX, TY>, TC> Apply<TC, TY>(IFold<TA, TY, Func<TB, TC>> fold);
    }

    // Implementation for folds
    internal sealed class FoldImpl<TA, TX, TB> : IFold<TA, TX, TB>
    {
        // Extract function for transforming the result of the fold
        private readonly Func<TX, TB> _extractFn;

        // Folding function
        private readonly Func<TA, TX, TX> _foldFn;

        // Initial argument for the folding function
        private readonly TX _seed;

        public FoldImpl(TX seed, Func<TA, TX, TX> foldFn, Func<TX, TB> extractFn)
        {
            _foldFn = foldFn;
            _seed = seed;
            _extractFn = extractFn;
        }

        public TB Fold(IFoldable<TA> foldable)
        {
            var folded = foldable.Fold(_seed, _foldFn);
            return _extractFn(folded);
        }

        public IFold<TA, TX, TC> Select<TC>(Func<TB, TC> fn)
        {
            return new FoldImpl<TA, TX, TC>(_seed,
                                            _foldFn,
                                            _extractFn.Compose(fn));
        }

        public IFold<TA, Tuple<TX, TY>, TC> Apply<TC, TY>(IFold<TA, TY, Func<TB, TC>> fold)
        {
            // Cast to concrete class to allow internal field access
            var innerFold = (FoldImpl<TA, TY, Func<TB, TC>>) fold;

            // Pair of initial folding values
            var seeds = Tuple.Create(_seed, innerFold._seed);

            // Combine the two folding functions into a single function
            // operating on pairs
            Func<TA, Tuple<TX, TY>, Tuple<TX, TY>> foldFn =
                (a, t) => Tuple.Create(_foldFn(a, t.Item1), innerFold._foldFn(a, t.Item2));

            // Combine the extract functions into a single function
            // innerFold._extractFn returns a function which is applied to the
            // result of the extract function of this fold
            Func<Tuple<TX, TY>, TC> extractFns =
                t => innerFold._extractFn(t.Item2)(_extractFn(t.Item1));

            // Create a new fold from the combined seeds, folding and extract
            // functions
            return new FoldImpl<TA, Tuple<TX, TY>, TC>(
                seeds,
                foldFn,
                extractFns);
        }
    }
}

Foldable.fs

open Microsoft.FSharp.Collections
open System
open System.Text

type Fold<'a, 'x, 'b> =
    | Fold of ('a -> 'x -> 'x) * 'x * ('x -> 'b)

let flip f a b = f b a

let fold (fold: Fold<'a, 'x, 'b>) (foldable: List<'a>) =
    match fold with
        Fold (step, seed, extract) ->
            List.fold (flip step) seed foldable |> extract

let (<@>) (fn: 'b -> 'c) (fold: Fold<'a, 'x, 'b>) =
    match fold with
        Fold (step, seed, extract) -> Fold(step, seed, extract >> fn)

let (<*>) (foldL: Fold<'a, 'x, ('b -> 'c)>) (foldR: Fold<'a, 'y, 'b>) =
    match (foldL, foldR) with
        (Fold (stepL, seedL, extractL), Fold(stepR, seedR, extractR)) ->
            let step a (xL, xR) = (stepL a xL, stepR a xR)
            let seed = (seedL, seedR)
            let extract (xL, xR) = extractR xR |> extractL xL
            Fold(step, seed, extract)

let intSum = Fold((fun a x -> a + x), 0, fun x -> x)

let doubleProduct = Fold((fun (a: int) (x: float) -> (float a) * x),
                          1.0, fun x -> x)

let stringConcat () =
    Fold((fun (i: int) (sb: StringBuilder) -> sb.Append(i)),
                       new StringBuilder(), fun sb -> sb.ToString())

type Blarg =
    | Blarg of int * float * string

let blarg i f s = Blarg(i, f, s)

let blargFold = blarg <@> intSum <*> doubleProduct <*> stringConcat()

[<EntryPoint>]
let main argv = 
    printfn "%A" argv

    let list = [1..10000]
    match fold blargFold list with
        | Blarg(i, f, s) -> printfn "%A %A %A" i f s.Length

    Console.ReadKey()
    0

Foldable.ts

class Fold<A, X, B> {   
    constructor(private seed: X,
                private step: (a: A) => (x: X) => X,
                private done: (x: X) => B) { }
    
    fold(foldable: Foldable<A>): B {
        var folded = foldable.fold(this.seed, this.step);
        return this.done(folded);
    }
    
    map<C>(fn: (b: B) => C): Fold<A, X, C> {
        return new Fold(this.seed,
                        this.step,
                        (x: X) => fn(this.done(x)));
    }
    
    apply<C, Y>(foldR: Fold<A, Y, (b: B) => C>): Fold<A, Pair<X, Y>, C> {
        var seeds = new Pair<X, Y>(this.seed, foldR.seed);
        var step = (a: A) => (p: Pair<X, Y>) =>
            new Pair<X, Y>(this.step(a)(p.fst), foldR.step(a)(p.snd));
        var done = (p: Pair<X, Y>) => foldR.done(p.snd)(this.done(p.fst));
        return new Fold<A, Pair<X, Y>, C>(seeds, step, done);        
    }
}

class Pair<A, B> {
    constructor(public fst: A, public snd: B) { }
}

interface Foldable<A> {
    fold<X>(seed: X, step: (a: A) => (x: X) => X): X;
}

class ListFoldable<A> implements Foldable<A> {
    constructor(private list: A[]) { }
    
    fold<X>(seed: X, step: (a: A) => (x: X) => X): X {
        var cb = (x: X, a: A) => step(a)(x);
        return this.list.reduce(cb, seed);
    }
}

class Blarg {
    constructor(public i: number, public f: number, public s: string) { }
    
    toString(): string {
        return "Blarg(i: " + this.i + ", f: " + this.f + ", s: " + this.s + ")";
    }

    static create = (i: number) => (f: number) => (s: string): Blarg => new Blarg(i, f, s); 
}

var sumFold = new Fold<number, number, number>(0, (a) => (x) => a + x, (x) => x);
var productFold = new Fold<number, number, number>(1, (a) => (x) => a * x, (x) => x);
var stringConcat = new Fold<number, string, string>("", (a) => (x) => x + a, (x) => x);

var foldable = new ListFoldable([1,2,3,4,5,6,7,8,9,10]);
var fold = stringConcat.apply(productFold.apply(sumFold.map(Blarg.create)));
var folded = fold.fold(foldable);

console.log(folded);

Foldable.vb

Option Strict On

Namespace Data.Foldable
    Public Interface IFold(Of TA, TX, Out TB)

        Function Fold _
            (foldable As IFoldable(Of TA)) _
            As TB

        ''' <summary>
        '''     Creates a new fold where the result of the fold is transformed using the given
        '''     selector function.
        ''' </summary>
        ''' <typeparam name="TC"></typeparam>
        ''' <param name="selector"></param>
        ''' <returns></returns>
        Function [Select](Of TC) _
            (selector As Func(Of TB, TC)) _
            As IFold(Of TA, TX, TC)

        ''' <summary>
        '''     Create an new fold where each element is transformed before the fold using the
        '''     given selector function.
        ''' </summary>
        ''' <typeparam name="TC"></typeparam>
        ''' <param name="selector"></param>
        ''' <returns></returns>
        Function ContraSelect(Of TC) _
            (selector As Func(Of TC, TA)) _
            As IFold(Of TC, TX, TB)

        ''' <summary>
        '''     Create a new fold where only the values passing the predicate are folded.
        ''' </summary>
        ''' <param name="predicate"></param>
        ''' <returns></returns>
        Function Where _
            (predicate As Func(Of TA, Boolean)) _
            As IFold(Of TA, TX, TB)

        Function Apply(Of TC, TY) _
            (fold As IFold(Of TA, TY, Func(Of TB, TC))) _
            As IFold(Of TA, Tuple(Of TX, TY), TC)
    End Interface
    
    Friend NotInheritable Class FoldImpl(Of TA, TX, TB)
        Implements IFold(Of TA, TX, TB)

        ' Extract function for transforming the result of the fold
        Private ReadOnly _extractFn As Func(Of TX, TB)

        ' Folding function
        Private ReadOnly _foldFn As Func(Of TA, TX, TX)

        ' Initial argument for the folding function
        Private ReadOnly _seed As TX

        Public Sub New _
            (seed As TX,
             foldFn As Func(Of TA, TX, TX),
             extractFn As Func(Of TX, TB))

            Check.NotNull(foldFn, NameOf(foldFn))
            Check.NotNull(extractFn, NameOf(extractFn))

            _extractFn = extractFn
            _foldFn = foldFn
            _seed = seed
        End Sub

        Public Function Fold _
            (foldable As IFoldable(Of TA)) _
            As TB _
            Implements IFold(Of TA, TX, TB).Fold

            Check.NotNull(foldable, NameOf(foldable))

            Dim folded = foldable.Fold(_seed, _foldFn)

            Return _extractFn(folded)
        End Function

        Public Function [Select](Of TC) _
            (selector As Func(Of TB, TC)) _
            As IFold(Of TA, TX, TC) _
            Implements IFold(Of TA, TX, TB).Select

            Check.NotNull(selector, NameOf(selector))

            Return New FoldImpl(Of TA, TX, TC)(
                _seed,
                _foldFn,
                _extractFn.Compose(selector))
        End Function

        Public Function ContraSelect(Of TC) _
            (selector As Func(Of TC, TA)) _
            As IFold(Of TC, TX, TB) _
            Implements IFold(Of TA, TX, TB).ContraSelect

            Check.NotNull(selector, NameOf(selector))

            Return New FoldImpl(Of TC, TX, TB)(
                _seed,
                Function(current As TC, acc As TX) _foldFn(selector(current), acc),
                _extractFn)
        End Function

        Public Function Where _
            (predicate As Func(Of TA, Boolean)) _
            As IFold(Of TA, TX, TB) _
            Implements IFold(Of TA, TX, TB).Where

            Check.NotNull(predicate, NameOf(predicate))

            Return New FoldImpl(Of TA, TX, TB)(
                _seed,
                Function(current As TA, acc As TX) If(predicate(current),
                                                      _foldFn(current, acc),
                                                      acc),
                _extractFn)
        End Function

        Public Function Apply(Of TC, TY) _
            (fold As IFold(Of TA, TY, Func(Of TB, TC))) _
            As IFold(Of TA, Tuple(Of TX, TY), TC) _
            Implements IFold(Of TA, TX, TB).Apply

            Check.NotNull(fold, NameOf(fold))

            ' Cast to concrete class to allow internal field access
            Dim innerFold = DirectCast(fold, FoldImpl(Of TA, TY, Func(Of TB, TC)))

            ' Pair of initial folding values
            Dim seeds = Tuple.Create(_seed, innerFold._seed)

            ' Combine the two folding functions into a single function
            ' operating on pairs
            Dim foldFn As Func(Of TA, Tuple(Of TX, TY), Tuple(Of TX, TY)) =
                    Function(a, t) Tuple.Create(_foldFn(a, t.Item1), innerFold._foldFn(a, t.Item2))

            ' Combine the extract functions into a single function
            ' innerFold._extractFn returns a function which is applied to the
            ' result of the extract function of this fold
            Dim extractFns As Func(Of Tuple(Of TX, TY), TC) =
                    Function(t) innerFold._extractFn(t.Item2)(_extractFn(t.Item1))

            ' Create a new fold from the combined seeds, folding and extract
            ' functions
            Return New FoldImpl(Of TA, Tuple(Of TX, TY), TC)(
                seeds,
                foldFn,
                extractFns)
        End Function
    End Class
End Namespace

Note to self: port to F#

Performance measurements (Debug mode, target platform x64, optimizations enabled, .NET 4.5):

Combined folds, 1000 runs: total 17152,0704ms, per run 17,152ms
Separate folds, 1000 runs: total 13858,9862ms, per run 13,8589ms
Custom loop, 1000 runs: total 11597,2656ms, per run 11,5972ms

F# port feature complete -- missing, however, is a Foldable type class