Real Traits in C#

What if I told you traits were introduced in C# and even the language designers didn't realize it? Furthermore, that it was introduced with C# 3.0 back in 2007! Yes, I'm actually claiming no one realized this for 13 whole years. You're not likely to believe me, and I don't blame you one bit.

public static Int64 IndexOf<TElement, TCollection>
    (this TCollection collection, TElement item)
    where TElement : IEquatable<TElement>
    where TCollection : IEnumerable<TElement>,
        IReadOnlyIndexable<Int64, TElement>
{
    Int64 i = 0;
    foreach (TElement element in collection) {
        if (element.Equals(item)) {
            return i;
        }
        i++;
    }
    return -1;
}

I'm actually expecting you to beleive this is a universal implementation of IndexOf() that has nothing to do with the actual collection, and will work with any collection that has the required traits.

Unbelievable, I know.

But it works!

And fascinatingly, there's no pseudo-trait trickery with classes that your type includes like every other "hey this is possible, kind, if you squint your eyes and wave a lot" claim out there. These are actual traits. The DynamicArray<> type shown in the passing test does not implement IndexOf() in any capacity. Here's even the full method list as of that test run:

Clearly, we need to break down what's going on, how and why this works, and why I think no one, myself included, realized this had been possible.

What's a trait?

Let's make sure we're all on the same page about what a trait is. This will also be useful in explaining why this approach works.

A trait is a specific feature of a type. A method it supports. A property. Whatever. It's just saying: "I have this thing".

So, we need a way that C# supports for saying types have something. That sounds an awful lot like interfaces. In fact, if we model the interface around that specific feature, instead of going the shadow-class way that most .NET developers go, we have, very close to, traits as they are seen in other languages. We can't add them to existing types like we can in a language with proper traits, but that's the only limitation we have, so that's good.

What's a C# trait?

How does this look like in C# then?

public interface IReadOnlyIndexable<in TIndex, TElement> {
    ref readonly TElement this[TIndex index] { get; }
}

The trait is hopefully obvious: "Hey, I'm indexable by a type you specify, and will return a read-only reference to the element at that index".

In a similar vein, IEnumerable<> is also a trait, and since it's part of the standard library I'm not going to explain it.

Implementing traits

How do we go about implementing this now? Remember, traits, by this pattern, are just interfaces, so you'd implement it like any other interface. DynamicArray<> looks like this:

public partial class DynamicArray<TElement> :
    IAddable<TElement>,
    IClearable,
    ICloneable<DynamicArray<TElement>>,
    ICountable,
    IDequeueable<TElement>,
    IEnqueueable<TElement>,
    IEnumerable<TElement>,
    IReverseEnumerable<TElement>,
    IEquatable<DynamicArray<TElement>>,
    IEquatable<TElement[]>,
    IIndexable<Int64, TElement>,
    IReadOnlyIndexable<Int64, TElement>,
    IInsertable<Int32, TElement>,
    IPoppable<TElement>,
    IPushable<TElement>,
    IRemovable<TElement>,
    IReplaceable<TElement>,
    IResizable,
    IShiftable,
    ISliceable<TElement>,
    IReadOnlySlicable<TElement>
    where TElement : IEquatable<TElement> {
}

Yeah, there's a lot of interfaces when you follow this pattern. Just go through and implement your interfaces like you normally would.

Programming for traits

Now here's where things deviate greatly from what everyone else has been doing. We're going to use generics and extension methods, not type composition, to bring this all together. After all, a major point of traits is supposed to be simplifying your implementations. And what better way of simplifying your implementations than providing single implementations of functions, which then appear on all supported types for free!?

Let's take a look at that IndexOf() I showed you at the beginning.

public static Int64 IndexOf<TElement, TCollection>
    (this TCollection collection, TElement item)
    where TElement : IEquatable<TElement>
    where TCollection : IEnumerable<TElement>,
        IReadOnlyIndexable<Int64, TElement>
{
    // Does stuff
}

Here's what's going on with this signature:

where TCollection : IEnumerable<TElement>,
        IReadOnlyIndexable<Int64, TElement>

This says that TCollection has to be an enumerable of TElement and read-only indexable by Int64 who's elements are TElement. In both traits, we're saying the collection is of TElement.

Typically, things are easier to explain when not abstract, so let's degeneralize this whole thing, and explain through a DynamicArray<Char>. Here's the relevant traits:

public class DynamicArray<Char> :
    IEnumerable<Char>,
    IReverseEnumerable<Char>,
    IIndexable<Int64, Char>,
    IReadOnlyIndexable<Int64, Char>,
    ISliceable<Char>,
    IReadOnlySlicable<Char>
{
}

IEnumerable<Char> you already know, and IReverseEnumerable<Char> exists in the library I'm utilizing traits for, but does exactly what you'd expect. You saw the IReadOnlyIndexable<Int64, Char> interface earlier, and IIndexable<Int64, Char> works the same way, but returns a ref Char rather than a readonly ref Char; in both cases, it allows an index of Int64 to return the Char at that position. ISlicable<Char> and IReadOnlySlicable<Char> are similar to I*Indexable<Char>, but also include an indexer that takes a Range type, and three Slice() operations, with all three returning *Span<Char>. Because both Range and Slice() work with Int32, I*Slicable<Char> implies I*Indexable<Int32, Char> as well. This should actually make sense as Char[] is actually indexable by Int32 or Int64.

Out of these, we have two relevant features: DynamicArray<Char> can have it's Char enumerated forward or reverse, and can have it's Char indexed by Int32 or Int64. Now let's take one last look at IndexOf()

public static Int64 IndexOf<TElement, TCollection>
    (this TCollection collection, TElement item)
    where TElement : IEquatable<TElement>
    where TCollection : IEnumerable<TElement>,
        IReadOnlyIndexable<Int64, TElement>
{
    Int64 i = 0;
    foreach (TElement element in collection) {
        if (element.Equals(item)) {
            return i;
        }
        i++;
    }
    return -1;
}

What was used in the implementation? An enumerator of the elements in the collection. No indexer was used, but because it's counting and incrementing an integer, and this would make no sense for other indexables, like an associative array, we, the human, understand that the type also needs to be indexable by integer. We actually didn't need to know a single thing about the collection itself, only that it had those two traits.

I've been utilizing this approach to greatly simplify a code base that can't be simplified through polymorphism and inheritance alone.

So yes, true, proper, trait programming in C# is possible, with the only limitation that you can't add trait implementations for existing types. Yet.

Why did everyone miss this?

People are afraid of generics. They're complicated and signatures of generic functions can get really verbose. They aren't utilized much outside of very simple templating in most cases. Ask most programmers how they'd combine multiple interfaces, and they'll suggest another interface. That works, but isn't helpful for trait programming.

Comments

[Tooster]

A lot of people seem to be confusing Traits, Extension Methods, Mixins, Interfaces and Algebraic Data Types.

• Interfaces don't define implementation nor state.
• Traits don't hold state, but provide implementation
• Mixins provide both state and implementation
• Interface with default implementation works like a Trait, but it's not external to the type implementing it, so it's not, in fact, a real Trait. For a trait to be really called a trait, it has to be defined externally without a need to modifying the existing type hierarchy of types in code (you have to implement ISliceable on some type to give it it's capability).
• Extension methods don't change the shape of Type, they are just syntax sugar. You can't narrow let's say a function parameter to "Type with this extension method". In your case you can only accept things like ISliceable but you used composition on the original type.

and Algebraic Data Type system allows for writing things like sum and intersection of types, which you can't do in C# for now, for example use something like foo(ISliceble & IIndexable bar). Rust traits (which don't define state) should be capable of representing interesection types by trait compositions.

For now the best (robust, expressive and DX friendly) type system I've seen is in TypeScript - structural and types are treated as expressions which allows using things like conditional types, mapped types, ADTs etc. (yes, Haskell and others exist, but I went with TS as it's a) something I use and b) mainstream, contrary to the more powerful but niche/academic languages).

[E. Zacarias]

I have seen a lot of extension methods applied to generics in Unity world, I wouldn't call it a feature people miss. But one of the thing traits are able to do is to introduce variables in a class. You can see it a lot in PHP framework "Laravel". How would you do that with extension methods?

For example, see Unity "GetComponent" method. You could have a trait "WithRigidbody" and the first time you request a "rigidbody" property it would get the component, and future calls would read from a variable, improving performance and cleaning the behaviour class. How would that be possible with extensions?

[Zachary Patten]

This style of interfacing is likely going to be obsoleted if/when Shapes are added to C#, especially if Shape extension methods are added to C#. github.com/dotnet/csharplang/issue...

[Patrick Kelly]

Yeah, and I hope that's the case. Dedicated syntax is preferrable to patterns, especially as convoluted as the generic signatures can get.