Functional Collections
Tags: computerscience, functional, csharp, dotnet
Published: 2020-10-11 17:47:51

Next up in [**Collectathon**](https://github.com/Entomy/Collectathon) is something I've seen quite a large amount of programmers express a desire for, although I didn't quite implement it to the extent they express. I'll explain why as I explain what this is.

Functional Programming is a small but very vocal and influential paradigm. I'll admit, I have mixed feelings about it. It's rife with performance problems, and puts the burden of knowledge on the downstream programmer which I consider an unreasonably UX. I feel like it's the wrong level of abstraction in most cases, with either declarative or imperative being more suitable. But it does have some fantastic parts, and it'd be great to incorporate them. Of especial interest here is higher-order functions. [**Collectathon**](https://github.com/Entomy/Collectathon) offers these.

Most collections are enumerable, the ones that aren't implement [`IContainable<TElement>`](https://entomy.github.io/Collectathon/api/Collectathon.Traits.IContainable-1.html), and in many cases, both are true. No matter what, this means that a collection has a `Contains()` method supplied from _somewhere_. Every collections library out there supports testing if a collection contains a specific element. That's simple and straightforward. I don't think a collections library would be very usable without it. But what about whether a collection has any elements that meet some specific criteria? Collections are generic, far too generic for a declarative API to be possible. This is Functional Programming's ideal niche!

~~~~csharp
DoublyLinkedList<Int32> list = DoublyLinkedList<Int32>() { 2, 4, 6, 8 };
Assert.True(list.Contains(IsPrime)); // Assuming IsPrime() exists
~~~~

This example is a bit contrived, but it can be especially useful. Consider seeing if a collection of customers has any customers of a specific geographic region.

In fact, any method where accepting a predicate makes sense should have an overload that accepts a predicate. Methods like `IndexOf()`, `Occurrences()`, `Remove()`, and `Replace()` already have higher-order variants defined.

Functional Programming also defines some well understood conventional functions as well though, and [**Collectathon**](https://github.com/Entomy/Collectathon) intends to support these in their entirety. Currently defined are functions like `Map()`:

~~~~csharp
DynamicArray<Int32> array = new Int32[] { 1, 2, 3, 4, 5 };
array.Map<Int32, DynamicArray<Int32>>((x) => x * 2);
Assert.Equal<Int32>(new Int32[] { 2, 4, 6, 8, 10 }, array);
~~~~

It works! I'm not happy about the callsite in C#. It's ugly and there's no other way to put that. I'm still looking into options to get that to resolve without being explicitly told what the types are. Maybe `Map()` must be supported via its own trait rather than implemented with existing traits (It currently requires `ICountable` and `IIndexable<Int64, TElement>`).

However, this is a fantastic opportunity to bring up what I've been doing for the people most likely to be using a functional paradigm anyways: F# bindings!

That same operation in F# looks like this:

~~~~fsharp
let array = DynamicArray<Int32>(8)
            |> add [| 1; 2; 3; 4; 5 |]
            |> map (fun (x) -> x * 2)
Assert.Equal([| 2; 4; 6; 8; 10 |], array)
~~~~

No explicit types! Which makes total sense as F# is meant for this kinda stuff. And these F# functions aren't their own implementations; they _are_ the existing definitions, just with a little marshalling as appropriate.

~~~~fsharp
let inline Add< ^t, ^a, ^b when (^t or ^a)
    : (static member Add : ^a * ^b -> unit)> collection element =
    ((^t or ^a) : (static member Add : ^a * ^b -> unit 
    (collection, element))

let inline add (element) (collection) =
        Add<Collection, _, _> collection element
        collection

let inline map (func) (collection) =
        Collection.Map(collection, Func<_, _>(func))
        collection
~~~~

Similarly, `Fold()` is supported right now, but `FoldLeft()` and `FoldRight()` aren't. How does that work? Well, `Fold()` requires the delegate to be a magma, while the other two require left-associative or right-associative respectively. The most common case of folding is the magma fold, so it made sense to implement this first.

~~~~fsharp
let array = DynamicArray<Int32>(8)
            |> add [| 1; 2; 3; 4; 5 |]
let sum = array |> fold (fun (a)(b) -> a + b) 0
Assert.Equal(15, sum)
~~~~

There's still that nagging part of me that wants this to be declarative even though that requires an exponential amount of work. A single magma `Fold()` can support all kinds of operations, whereas a declarative `Sum()` only works for the single numeric type for which it was defined. It does conveniently express intent better, and not require the downstream programmer to know what the delegates identity is (`0` for addition). In some cases, determining identity is remarkably difficult. But I'm glad this exists. This is a hugely powerful, and to reiterate, appropriate for this level of abstraction.

Consider all this another tool in the toolbox [**Collectathon**](https://github.com/Entomy/Collectathon) provides.