In my last post, I wrote about a solution to the Leap problem on Exercism. A reader and I had a discussion around what predicates are, sparking the idea for another post. This time, we'll look at abstractions, composition, and modularity. If you don't want to visit the aforementioned links, and still want to be able to follow, here's a quick recap:
Leap is a problem where we want to find if the year passed in is a leap year or not. There are simple rules provided as a direction:
A leap year (in the Gregorian calendar) occurs:
* In every year that is evenly divisible by 4.
* Unless the year is evenly divisible by 100, in which case it's only a leap year if the year is also evenly divisible by 400.
* 1997 was not a leap year as it's not divisible by 4.
* 1900 was not a leap year as it's not divisible by 400.
* 2000 was a leap year!
Your task is to determine whether a given year is a leap year.
One way to think about problems and their solutions is to break down the problem into smaller problems, and then solve those, and combine those to create a solution for the larger problem. It's when we break things down and build them up that abstractions become useful.
What's an abstraction? Anything that represents an idea and doesn't go into details about its implementation. In
type is an abstraction, at its very basic level. It serves to refer to a simple idea of something that has a specific structure. They're reusable, and generally, composable. We can use a type in another type definition, that's what makes it composable. In fact, in
TypeScript, we can use a type in its own definition, a special case called recursive types!
In general, it's a good exercise to try to learn things and express things with type definitions and usages in
TypeScript, and it's something we'll dabble with in our post. By extension, functions (and classes) are also abstractions - we usually refer to them and not often reach for their definitions when we're building things with them.
As an example, let's define a type for a function. A function can have any number of arguments, and its arguments can be of any type. But it always has one return type. So, to define a type for a function, we need to specify the type of its arguments, and the return type. We can write:
We basically have used 2 generic arguments (
Result) to define a
Fun type, which represents a function. There's an additional constraint on the generic argument type
extends any. An
extends clause on a type argument is called a type constraint. Together, the definition for the type makes it clear that it refers to any function that takes arguments of type
Args (which needs to be an array) and a return type
We definitely can see that the solving the leap problem involves a bunch of conditional logic. A predicate is just a function that returns
false. Given we have an abstraction (type) for a function, it's easy to define a type for a predicate:
We have now defined a predicate type using a single generic type argument
Args. There's a type constraint on
Args that it has to be an array. But for whatever
Predicate<Args> is just a
Fun<Args, boolean> which means a predicate is just a function that returns a boolean. It can take any number and any types of arguments, just like a function.
This is an example where we use an idea to build up another. Here, we used the idea of a function that takes arguments and returns a value of a specific type, to build up the idea of a predicate that is just a function that returns a boolean. It's simple to see and understand just from the types. As we get better at TypeScript, we can describe a lot of ideas with types. This is one of the ways we can harvest the power of abstractions. Watch out for further abstractions we build!
What makes this abstraction useful? We know that testing whether a given year is a leap year or not is itself a predicate that takes a single number (year) as the argument. What would it's predicate type be?
We can also add a name for the argument using a named tuple type:
It's not necessary but useful to know.
To check whether a year is a leap year though, we need to check several conditions. Each of those can be a predicate, which when combined (in the right way and order), results in us being able to test whether a given year is a predicate. Can we model it likewise? It looks like we need operations like
not to combine different predicates together. They are usually boolean operators. Maybe we can build them up?
Given we're on the lookout for effective composition, let's try to build up predicate logic from boolean logic. We'll define 3 simple functions
not, as they're the basic logical operators:
or both can take any number of
boolean arguments, and return a single
boolean. We collect the arguments with the
... (spread operator) into an array, and then do an
Array.prototype.reduce that simply uses the logical operators. These are both generic functions, defined with a generic type argument
Args, with a type constraint that it should be an array of
booleans. This means that
or are only defined for an input type
Args with some conditions on the type of
However, there's a problem:
or now take
1 arguments, which shouldn't be defined. How can we solve that? We basically want to say that
or take 2 or more arguments.
We can explain it supports 2 or more arguments by simply making the first 2 arguments explicit:
Here, we collect the rest of the arguments into an array, and then allocate another array where we prepend the first 2 boolean arguments. Notice that we don't need a default accumulator value anymore for the
reduce, as the array always has at least 2 elements.
We can still do better. Here's a way that makes use of a type constraint we can place on the arguments type
reduce runs through all the elements and doesn't short-circuit):
Given that the arguments always have at least 2 elements, it makes sense to not have to think about a default initial argument like we had to for the version with
That was simple enough, now how do we build up predicate logic?
If we're intent on composing predicates, we definitely need function application. Function application is simply applying a function to a value, getting its result.
In addition, we also want to
compose functions. Function composition is defined by
f . g where if
g is a function that takes parameter
f . g is
f(g(x)). Let's write it out, and also use a
pipe which is just compose but in the opposite order (
Notice that we also introduced additional types and functions. We have a unary function, which takes a single argument, and a binary function that takes any 2 arguments, and they both are simply functions. We also added a simple
flip function that was used to build up
compose itself. Because we used generic types to define both
flip, we get the type information of
pipe for free. If we hover over it in an IDE we can easily inspect its type:
It should now be clear what
pipe does simply from its signature - I hope you're used to reading types by now. It takes as its first argument a function that takes any arguments and returns a value of type
Intermediate, and as its second argument a function that takes a single argument of type
Intermediate and returns a value of type
Result, and returns a function that takes arguments of type
Args and returning a value of type
Result. We can see that there's only one way to implement that function that makes the types agree - pass the arguments to the first function, and pass the resulting value of type
Intermediate into the second function to get a return value of type
Intermediate. Wasn't that simple?
Now that we have all the ingredients, writing predicate logic using the boolean logic should be simple. Given we have several imports and we need to disambiguate, let's use an alias for our imports. We don't want it to be too verbose since we may be using the imports a lot:
Notice how we use
reduce to define our
or. And we have no conflicts with similar functions in our
boolean import because we used a
B namespace for the imports. Also note that we use
pipe to implement our
not for the predicate logic.
While our composition of
reduce, and the boolean operators
or are neat, it's not necessarily the most performant. We can create short-circuiting versions by using in-built methods. It's useful to know but not necessary to worry about as we're probably not using too many predicates as arguments to
or to cause significant concern.
A simple predicate to construct will be useful, so let's add one:
There are a lot more predicate constructors we can think of, like
isGreaterThan and the like: I'm sure we'll know when we need them.
Now that we have predicate logic, let's try to implement our solution. It can also be built up. I'd encourage you to have a look at our ordering of arguments so far, and whether they've been useful:
It's interesting that when we have functions like
remainder with arguments in a certain order, it becomes very easy to compose things together. We are also trying to disambiguate between a boolean
or by using a
P namespace for predicate imports, even in the absence of
TypeScript language server help with the right type hints.
While by no means this is the only way to solve the problem or even approach it, it was helpful to discuss ideas like abstraction, composition, and modularity. Hopefully that helped you appreciate an idea or two about the power of composition, modularity, and overall: abstractions.
It's very helpful to build up an idea from small pieces that work well independently but also better together. We represent ideas in code as abstractions. But as I've mentioned before, abstractions always come with a cost. Despite it, there may be places where an explicit identification and expression of abstractions helps more than it hurts. Hopefully we create useful abstractions when required!
Fun Fact: A similar approach is discussed as "overkill" in the Exercism video on different approaches to solve Leap