Functional in the wild: typeclasses

One thing that I always though was great about Haskell, which bothered me in OO languages, is the idea of a typeclass. It allows you to implement a common interface for a myriad of types and then implictly create higher order functions; after all, you don't pass the functions themselves, but they can be derived from the type the function is instantiated with. Let me give an example. A very common pattern in all languages is the ability to convert an object to its string representation. Haskell comes with a 'Show' typeclass, that defines the common interface:

class Show a where
    show :: a -> String

if we then create for example a currency datatype, we can define the show function for all it's constructors.

data Currency = Euro Int | Dollar Int

instance Show Currency where
    show (Euro x) = "€" <> show x
    show (Dollar x) = "$" <> show x

The object oriented approach

If you are familiar with C#, where the use of interfaces is very much a core principle of the language, we could create an interface like the following:

interface IShow 
{
    string Show();
}

And then inherit from that interface in our specific currency classes:

class Euro : IShow 
{
    int x;
    override string Show() {
        // Not an ideal example since toString already exists, but oh well.
        return "€" + x.toString()
    }
}

class Dollar : IShow 
{
    int x;
    override string Show() {
        return "$" + x.toString()
    }
}

For C# this is a fairly canonical and reasonable approach. But when we transition to C++, we have a better alternative.

c++ means you care about performance

It's the main selling point of the language: it can be fast. C++ also does not have interfaces. However, because multiple inheritance is allowed we could quite easily do the same as in C#, but there is a big drawback: virtual functions. Virtual functions can incur a costly performance overhead; there will need to be a runtime lookup into the vtable to see what function has been implemented for this specific type. This also means that the compiler cannot inline the function call, which is an essential optimization.

This same problem may exist in C# but it is unlikely that performance will be high on your priority list. If that were the case, you should have started with c++ from the start anyway. So, how can we do better than virtual functions? Templating!

template<typename T>                                                            
struct show_class {                                                             
    std::string operator() (const T& obj) const;                                
};
                                                                                
struct Euro {                                                                   
    int x;                                                                      
};                                                                              

struct Dollar {
    int x;
};
                                                                                
template<>                                                                      
struct show_class<Euro> {                                                       
    std::string operator() (const Euro& obj) const {                            
        return "€" + std::to_string(obj.x);                                     
    }                                                                           
};

template<>                                                                      
struct show_class<Dollar> {                                                       
    std::string operator() (const Dollar& obj) const {                            
        return "€" + std::to_string(obj.x);                                     
    }                                                                           
};

We can know use call upon the typeclass in some polymorphic function:

template<typename T>
void printToConsole(const T& obj) {
    printf("%s\n", show_class<T>()(obj).c_str());
}

Whenever we pass a T for which the typeclass is not implemented, we will get a compile time error. If the typeclass is implemented, compiler will know at compile time which function to use and is free to inline it. Invalid usage will unfortunately not always result in very readable error message:

/usr/bin/ld: /tmp/ccPSfC80.o: in function `void printToConsole<int>(int const&)'
:                                                                               
test.cpp:(.text._Z14printToConsoleIiEvRKT_[_Z14printToConsoleIiEvRKT_]+0x33): un
defined reference to `show_class<int>::operator()[abi:cxx11](int const&) const' 
collect2: error: ld returned 1 exit status

Especially annoying is the fact that language servers and IDE's will likely also not pickup on this problem. What they see is that the function generally does exist in the typeclass definition, and it'll only be the linker that realizes that the function is never implemented for any type. It seems however that there is experimental solutions for this in the pipeline: https://en.cppreference.com/w/cpp/experimental/is_detected. Although I myself was not skilled enough to get it working just yet.

Cool hack, but I write professional software

Great, this stuff is not a hack, this is actually being used, even in STL! If I want to create an unordered_map of say pairs, you will run into the problem that STL has not implemented a hash function for that type and will refuse it as a map key. However, there is a templated hash struct very similar to our show_class that we can specialize with a generic pair type to allow for this:

struct pair_hash {
    template<class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &p) const {
        auto h1 = std::hash<T1>()(p.first);
        auto h2 = std::hash<T1>()(p.second);
        return h1 ^ h2;
    }
};

int main(int argc, char** argv) {
    // this is now allowed
    std::unordered_map<std::pair<int, int>, int, pair_hash> veryNiceMap;
    return 0;
}

Very professional friendly I'd say :)

last modified: May 29, 2023 at 13:07