Abstractions, composition, and modularity

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

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.

Some examples:
* 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.

Abstractions

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 TypeScript, a 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.

Functions

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:

export type Fun<Args extends any[], Result> = (...args: Args) => Result;

We basically have used 2 generic arguments (Args and Result) to define a Fun type, which represents a function. There's an additional constraint on the generic argument type Arg that it has to be a tuple type (a heterogenous array, as JavaScript allows) - we do that by saying it 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 Result.

Predicates

We definitely can see that the solving the leap problem involves a bunch of conditional logic. A predicate is just a function that returns true or false. Given we have an abstraction (type) for a function, it's easy to define a type for a predicate:

import { Fun } from "./function";

export type Predicate<Args extends any[]> = Fun<Args, boolean>;

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 Args is, 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?

declare const isLeap: Predicate<[number]>;

We can also add a name for the argument using a named tuple type:

declare const isLeap: Predicate<[year: number]>;

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 and, or, and not to combine different predicates together. They are usually boolean operators. Maybe we can build them up?

Boolean logic

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 and, or, and not, as they're the basic logical operators:

export const and = <Args extends boolean[]>(
  ...args: Args
): boolean => args.reduce((a, b) => a && b, true);

export const or = <Args extends boolean[]>(
  ...args: Args
): boolean => args.reduce((a, b) => a || b, false);

export const not = (value: boolean): boolean => !value;

and and 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 and and or are only defined for an input type Args with some conditions on the type of Args.

However, there's a problem: and and or now take 0 or 1 arguments, which shouldn't be defined. How can we solve that? We basically want to say that and and or take 2 or more arguments.

We can explain it supports 2 or more arguments by simply making the first 2 arguments explicit:

export const and = <Args extends boolean[]>(
  a: boolean,
  b: boolean,
  ...args: Args
): boolean => [a, b, ...args].reduce((a, b) => a && b);

export const or = <Args extends boolean[]>(
  a: boolean,
  b: boolean,
  ...args: Args
): boolean => [a, b, ...args].reduce((a, b) => a || b);

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 Args:

export const and = <
  Args extends [boolean, boolean, ...boolean[]]
>(
  ...args: Args
): boolean => args.reduce((a, b) => a && b, true);

export const or = <
  Args extends [boolean, boolean, ...boolean[]]
>(
  ...args: Args
): boolean => args.reduce((a, b) => a || b, false);

Arrays in JavaScript also support a short-circuiting version (which means it only does minimal work and exits as soon as possible) to do minimum work given a list or arguments (reduce runs through all the elements and doesn't short-circuit):

export const and = <
  Args extends [boolean, boolean, ...boolean[]]
>(
  ...args: Args
): boolean => args.every(Boolean);

export const or = <
  Args extends [boolean, boolean, ...boolean[]]
>(
  ...args: Args
): boolean => args.some(Boolean);

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 reduce.

That was simple enough, now how do we build up predicate logic?

Function application

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.

export type Fun<Args extends any[], Result> = (...args: Args) => Result;

export const apply =
  <Args extends any[]>(...args: Args) =>
  <Result>(f: Func<Args, Result>) =>
    f(...args);

In addition, we also want to compose functions. Function composition is defined by f . g where if g is a function that takes parameter x, 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 (g(f(x))):

export type UnaryFun<A, Result> = Fun<[A], Result>;

export const compose =
  <Args extends any[], Intermediate, Result>(
    f: UnaryFun<Intermediate, Result>,
    g: Fun<Args, Intermediate>
  ): Func<Args, Result> =>
  (...args) =>
    f(g(...args));

export type BinaryFun<A, B, Result> = Fun<[A, B], Result>;

export const flip =
  <A, B, Result>(f: BinaryFun<A, B, Result>): BinaryFun<B, A, Result> =>
  (b, a) =>
    f(a, b);

export const pipe = flip(compose);

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 pipe using compose itself. Because we used generic types to define both compose and flip, we get the type information of pipe for free. If we hover over it in an IDE we can easily inspect its type:

const pipe: <Args extends any[], Intermediate, Result>(
  args_0: Fun<Args, Intermediate>,
  args_1: UnaryFun<Intermediate, Result>
) => Fun<Args, Result>;

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?

Predicate logic

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:

import * as F from "./function";
import * as B from "./boolean";

export type Predicate<Args extends any[]> = F.Fun<Args, boolean>;

export const and =
  <Args extends any[]>(
    ...predicates: [
      Predicate<Args>,
      Predicate<Args>,
      ...Predicate<Args>[]
    ]
  ): Predicate<Args> =>
  (...args) =>
    predicates
      .map(F.apply(...args))
      .reduce(B.and<[boolean, boolean]>, true);

export const or =
  <Args extends any[]>(
    ...predicates: [
      Predicate<Args>,
      Predicate<Args>,
      ...Predicate<Args>[]
    ]
  ): Predicate<Args> =>
  (...args) =>
    predicates
      .map(F.apply(...args))
      .reduce(B.or<[boolean, boolean]>, false);

export const not = <Args extends any[]>(
  predicate: Predicate<Args>
): Predicate<Args> => F.pipe(predicate, B.not);

Notice how we use map and reduce to define our and and 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.

Performance

While our composition of map, reduce, and the boolean operators and and 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 and or or to cause significant concern.

export const and =
  <Args extends any[]>(
    ...predicates: [
      Predicate<Args>,
      Predicate<Args>,
      ...Predicate<Args>[]
    ]
  ): Predicate<Args> =>
  (...args) =>
    predicates.every(F.apply(...args));

export const or =
  <Args extends any[]>(
    ...predicates: [
      Predicate<Args>,
      Predicate<Args>,
      ...Predicate<Args>[]
    ]
  ): Predicate<Args> =>
  (...args) =>
    predicates.some(F.apply(...args));

Predicate creation

A simple predicate to construct will be useful, so let's add one:

export type UnaryPredicate<Arg> = Predicate<[Arg]>;

export const equals =
  <A>(x: A): UnaryPredicate<A> =>
  (y) =>
    x === y;

There are a lot more predicate constructors we can think of, like isLessThan and isGreaterThan and the like: I'm sure we'll know when we need them.

Leap

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:

import * as F from "./function";
import * as P from "./predicate";

const remainder = (divisor: number) => (dividend: number) =>
  dividend % divisor;

const isDivisibleBy = (divisor: number) =>
  F.pipe(remainder(divisor), P.equals(0));

export const isLeap: P.Predicate<[year: number]> = P.and(
  isDivisibleBy(4),
  P.or(P.not(isDivisibleBy(100)), isDivisibleBy(400))
);

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 and and or by using a P namespace for predicate imports, even in the absence of TypeScript language server help with the right type hints.

Conclusion

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