Functional Collections

Next up in 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 offers these.

Most collections are enumerable, the ones that aren't implement IContainable<TElement>, 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!

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 intends to support these in their entirety. Currently defined are functions like Map():

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:

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.

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.

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

Comments

[Patrick Kelly]

I've since fixed the C# callsite for Map() to where everything implicitly resolves.