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.