Data Types and Complexity

So today I learned something cool, tried to find more information about it but either it doesn’t exist (probably impossible in this day in age) or it’s not “trending” or I can’t use Google 😊

Either way, I thought it was pretty cool and it brought me back to those horrid complexity classes in college, where you sat there thinking “when in the world am I ever going to use this stuff?”. So maybe I’m getting old or maybe I’m really getting into this FP stuff (found this while sat down with a cuppa reading my favorite FP book).

Enough mumble, jumble, let’s get into it. A few key terms before we get started (in case you’re somewhat newbie like me and new to using these terms daily)

A product: includes all of it’s given types

A co-product: materializes one of it’s given types

Totality: call a function with any input and it will always produce a valid value — no matter how many times you do it, it should not break production 😉

Total function: enforces totality, it is designed for all possible input types

Counting Complexity

So all values have built-in complexity as per below:

Unit => 1 value
Boolean => 2 values
Int => 4,294,967,295 (in other words a lot)
String => let's call it infinite 

So to find the complexity of a product = multiply the complexity of each part

Let’s have a look at some examples

(Boolean, Boolean) => 4 (2*2)
(Boolean, Boolean, Boolean) => 8 (2*2*2)

What about the complexity of co-products? Well we add the complexity of each part

Again, some super simple examples

(Boolean |: Boolean) => 4 values (2+2)
(Boolean |: Boolean |: Boolean) => 6 (2+2+2)

Do you sort of see where I’m going with this? After all, adding complexity is much better than multiplying it… (I know math genius in the house)

Let’s have a look at an ADT with a parameter type = we multiple each part by the complexity of the type parameter

Option[Boolean] => 3 values (2+1)
....
Some[Boolean] => 2
None => 1

I know, mind blowing stuff 😉

Now let’s talk functions.

As a general rule of thumb (or so I hear), a badly designed function is one which has a higher complexity of the functions return than the product of it’s inputs.

The complexity of a total function is the output to the power of the input

Let’s see it in action

Unit => Boolean : 2 (2^1)
Boolean => Boolean : 4 (2^2)
Option[Boolean] => Option[Boolean] : 27 (3^3)
Boolean => Int : hell of a lot
Int => Boolean : hell of a lot * a lot more

When you think about it, a function like Int => Boolean is probably something simple, like isEven or isOdd . This function could potentially be replaced with a co-product by limiting the set of functions that are relevant. I haven’t come across much use of co-products in my day to day yet but with this new information, I hope to try and spot some improvements.

I’ve just learned about these new refined libraries which provides a suite of restrictions to the contents of a data type. I haven’t used it yet myself but hope to experiment with it soon.

I’ll link it here below in case anybody else is interested.

fthomas/refined