The Strange Art of Code Reuse, Part 3
Tags: computerscience
Published: 2022-07-05 23:41:20

---
title: The Strange Art of Code Reuse, Part 3
published: true
description: After going through the Wild West of dynamic typing, then the taxonomic world of object-oriented programming, it's now time to climb the ivory tower of category-theoretic typing. While the gold standard of category types is found in Haskell, this is also the type system used in Rust.
tags: #computerscience
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/csh5y068pw7ff4jqnczu.png
# Use a ratio of 100:42 for best results.
---

The first two parts of this series talked about [dynamic typing](https://dev.to/armousness/the-strange-art-of-code-reuse-part-1-dbc), then [object-oriented programming](https://dev.to/armousness/the-strange-art-of-code-reuse-part-2-h39). Along the way, I tried to get across some notions of what polymorphism is. When you have a function take an argument of some type, there are two issues: first, what operations can be done with that type, and second, what are the semantics of that type?

The semantics of primitive types have been ingrained in us since elementary school. Integers are for counting, rational numbers are for ratios, booleans are for logic, and strings are for reading and writing. Once you start structuring data, you need to come up with your own semantics: vec3 is a position in a three-dimensional vector space, array is an ordered list of things, Person is information about a person in the real world.

I dislike dynamic typing because it has sloppy semantics, and you can even see that at the primitive level. JavaScript coerces all numbers to `double`, which degrades its use for counting. This also means that you don't know off hand whether a number in JavaScript is for counting or for ratios.

Object-oriented programming encodes semantics, particularly for structured data, into a sort of data taxonomy. If your data don't rigidly conform to your taxonomy, then you either have to refactor, or you have to hack. Interfaces ease the restrictiveness of class hierarchies, but in my experience this fact isn't appreciated as much as it should be. Even then, interfaces have the problem that you can't generally tack them onto classes you bring in from the outside (i.e., from an API).

This brings us to Haskell, the ivory tower of programming languages. It's [not the tallest tower out there](https://www.idris-lang.org/), but that doesn't make it any less ivory.

## `eat :: ∀t, t ∈ Edible: t → IO ()`

For lack of a better term, I'll be referring to the Haskell-style type system as category programming. At first blush, category programming is focused on interfaces, though they're called typeclasses. The caveat is that interfaces can be implemented on existing types, including primitive types. For example, the Haskell analog of `ToString` is a typeclass called `Show`, defined as follows:

```
class Show t where
    show :: t -> String
```

While the syntax may be unfamiliar, you probably already know everything going on here. `t` is a generic type parameter, much like `std::vector<'t>` in C++ or `List<'t>` in C#. Like interfaces, the typeclass `Show` defines one or more function "templates," so all we specify here is a signature. `::` is a type annotation, and `->` indicates a function.

So `Show` is a typeclass containing one function, `show`, which takes a value of type `t` and returns a `String`. We can then add types to a typeclass with `instance`. For example,

```
-- Define a Vec2 type, which just contains two doubles
-- Don't stress the syntax right now
data Vec2 = Vec2 Double Double

instance Show Vec2 where
    show (Vec2 a b) = "(" ++ show a ++ ", " ++ show b ++ ")"
```

The basic Haskell library already implements `Show` on many types, including `Double`—much like how Dotnet defines `ToString` on `double`. Let's dive into the original example problem, of making a generic function to add elements to a collection:

```
{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
import Data.Set as Set

class AddToCollection c e where
   add_to_collection :: e -> c e -> c e

instance AddToCollection [] t where
    add_to_collection e c = e : c

instance Ord t => AddToCollection Set t where
    add_to_collection e c = Set.insert e c
```

Okay so there's a lot going on here. Let's agree to ignore `FlexibleInstances` and `MultiParamTypeClasses` and focus on the meat. First and foremost, we had no difficulty putting basic API types into this class, which is great. But what's going on with these type signatures?

Let's start from a more basic point, which is "currying." In ML-style languages (including Haskell and F#), you don't surround arguments to function calls in parentheses. Instead, functions have "free variables," and applying a value to a function "closes" one of them. So `Set.insert` is a function with two free variables, `t -> Set t -> Set t`. We apply a value `e` to it, which closes it to `Set t -> Set t`, then we apply a value `c` to it, which closes it all the way to just `Set t`.

This same logic applies to types. Dotnet `Generic.List` is a *type function*, while `Generic.List<int>` is a type. `Generic.List` has a free type parameter; passing it the type `int` gives us a concrete type. Dotnet requires you to surround type arguments in angle-brackets, while Haskell allows type arguments to be curried.

So let's look at

```
class AddToCollection c e where
   add_to_collection :: e -> c e -> c e
```

again. `c` is a type function, and `e` is a concrete type. The `add_to_collection` function takes an element (of type `e`), and a collection (of type `c e`). At this point, this isn't very different from a C# function taking arguments of type `int` and `List<int>`. The difference is, to my knowledge, C# doesn't let you define interfaces with type functions as generics.

And what about this:

```
instance Ord t => AddToCollection Set t where
    add_to_collection e c = Set.insert e c
```

The default `Data.Set` is tree-based, and operations on sorted trees require the elements of the tree to be comparable, with `>` and `<`. Since Haskell was made by mathematicians, the class of types that define less-than and greater-than is called ordinal, meaning, they can be ordered. `Ord t` is a type constraint: we say that `t` must be ordinal.

This also lets us take a glimpse at the formality behind all of this. The reason we need the `Ord t` constraint is because of the type of `Set.insert`:

```
insert :: Ord t => t -> Set t -> Set t
```

The `add_to_collection` function, as defined for `Set t`, applies the `Set.insert` function to `e` and `c`. `Set.insert` requires that its first argument be of an ordinal type, and that its second argument be a `Set` of ordinal types. This requirement gets re-imposed on our function, `add_to_collection`.

Now, what exactly is `t`? Let's again compare it to something more familiar: what is an integer, or maybe, what is a 32-bit integer? The answer to that is, it's a whole number between -2,147,483,648 and 2,147,483,647. So int32 isn't a particular value, but it's a range of values. Better said, int32 is a *set*, and a value of type int32 is a member of that set.

`t` is similar: `t` is the set of all possible types. `Ord t =>` narrows this down, where `t` is any type in the set `Ord`. Remember, `Ord` is a typeclass, and types can be added to a typeclass with `instance`. Many types are in there by default (including `Int` and `Char`), and we can add any other types we want.

Earlier we defined a type of two-dimensional vectors. As it stands, this doesn't work:

```
data Vec2 = Vec2 Double Double

vec2set = add_to_collection (Vec2 5 2) Set.empty
-- error: No instance for (Ord Vec2) arising from a use of 'add_to_collection'
```

Okay, so we need `Vec2` to provide an instance of `Ord`...

```
instance Ord Vec2 where
    compare (Vec2 a1 b1) (Vec2 a2 b2) =
        if a1 == a2 then compare b1 b2 else compare a1 a2
-- error: No instance for (Eq Vec2) arising from the superclasses of an instance declaration
```

It turns out, classes can require other classes, and `Ord` requires `Eq`, which defines equality. Okay, so...

```
instance Eq Vec2 where
    (Vec2 a1 b1) == (Vec2 a2 b2) = a1 == a2 && b1 == b2
```

And now we're good, we can now have a `Set` of `Vec2` since we've satisfied all the requirements (including the earlier definition of `Show`, which is required to pass something to `print`):

```
main :: IO ()
main = print (add_to_collection (Vec2 5 2) Set.empty)
-- output: fromList [(5.0, 2.0)]
```

This probably shows you why Haskell has the reputation it does: To explain object-oriented programming, I just gestured at the idea of taxonomy and your intuition did the rest of the work. To really explain category programming, we had to get knee-deep in theory. The plus side is, this is a system of such staggering flexibility that, as long as you keep your distance from the [Entscheidungsproblem](https://en.wikipedia.org/wiki/Entscheidungsproblem), you can do nearly anything you want.

I'm going to close out on one cool feature that you kind of need this level of complexity to tackle. I mentioned way back at the beginning that dictionaries are weird. If you have a dictionary that contains an entry `"a": 5` and you add `"a": 3`, what's the correct thing to do? As usual this depends on your dictionary's semantics, but often the best thing to do is to set `"a"` to `8`.

But let's think big: what I'm really talking about is having insertion semantics that are specific to the type of the dictionary's values. The dictionary type in Haskell is called `Map`, and as in Dotnet's `Generic.Dictionary`, it has two type parameters. Because of this, let's sidestep an even more obscure issue called "higher-kinded polymorphism" and define a new typeclass:

```
class AddToMap k v where
    add_to_map :: k -> v -> Map k v -> Map k v
```

`Map` defines a function `insertWith`: we pass it a function, and if a key is already present in the Map, it combines the old and new values using that function; otherwise it inserts the value. We can use it to create instances of `AddToMap` that are specialized to particular value types:

```
instance Ord k => AddToMap k String where
    add_to_map k v c = Map.insertWith (++) k v c

instance Ord k => AddToMap k Int where
    add_to_map k v c = Map.insertWith (+) k v c
```

`++` is string/list concatenation, while `+` has the usual meaning. So if we have a Map of Strings, overwriting an existing key instead concatenates, while if we have a Map of Ints, overwriting an existing key instead adds:

```
main :: IO ()
main = do
    print (add_to_map "a" (5::Int) (add_to_map "a" 3 Map.empty))
    print (add_to_map "message" "hello" (add_to_map "message" " world" Map.empty))

-- output:
-- fromList [("a",8)]
-- fromList [("message","hello world")]
```

## Conclusion

There's no question that category polymorphism is the most powerful of the type systems considered here. This doesn't mean I think everyone should use Haskell, or that you should try to convince your company to switch to Haskell, or anything like that. The point of this series was to be informative, not persuasive. Indeed, in practice, there are enormous drawbacks to using Haskell, but *understanding* Haskell can teach you a lot about computer science.

That is the one thing I'll definitively say about all this: I don't care whether you *use* Haskell, but you should absolutely *learn* it. I mean, I hardly ever use it, but the knowledge I gained from learning it is indispensable.

This is also the core reason that Rust is my current favorite language: Rust's traits are very similar to Haskell's typeclasses, but I think Rust has better handling of other stuff, particularly mutable state. Also Rust is incredibly fast.

Now all it needs is a good GUI library...

In any case, if you made it through all this, I hope you gained a deeper appreciation for polymorphism, and the three-way trade-off between code reusability, semantic stability, and language complexity.