Follow

Follow

# Composition with the S-Combinator

## AKA The Substitution or Starling combinator

Mr Rampage
·Mar 18, 2021· Photograph by Noel Feansderivative work: Snowmanradio, CC BY 2.0, via Wikimedia Commons

# The S-Combinator

Combinators are functional patterns that glue (AKA compose) together functions. These patterns promote single responsibility and decoupling. Today's story is the story of my journey into learning and using the S-Combinator in a functional code base. I'll be using pseudo-code to explain.

The problem I had to solve was to generate 2D thumbnails from a 3D volume. The 3D volume itself was made up of a three dimensional container of 2D images, so each 2D image could be found by it's axis and index. If you're familiar with medical imaging, this is a DICOM image.

Several functions were required to get this job done:

1. A function to get the number of images along an axis
2. A function to get the index of the image in the middle of an axis
3. A function to extract the image by index

The implementation details of each of these aren't important (they're also very specific to medical imaging). However, the interfaces are extremely important when it comes to gluing things together.

Pro-tip: Always design your interfaces first and keep them as simple and symmetrical as possible. It'll reveal patterns that you won't see if you do the implementation first.

The functional interfaces for this problem were defined as follows:

``````// Using lambda notation
let CountSlices = (axis: Axis) => (image: Image) => (count: uint)
let GetMidSliceIndex = (axis: Axis) => (image: Image) => (index: uint)
let Slice2D = (axis: Axis) => (index: uint) => (image: Image)
=> (image: Image)

// Using object oriented notation
function uint CountSlices(Axis axis, Image image) {...}
function uint GetMidSliceIndex(Axis axis, Image image) {...}
function Image Slice2D(Axis axis, uint index, Image image) {...}
``````

Looking at these functional interfaces a few things jumped out to me:

1. `CountSlices` and `GetMidSliceIndex` are tightly coupled and feed into `Slice2D`.
2. The input parameters are almost symmetrical - all requiring an Axis and an Image

Are there any other things that stand out for you?

## Compose/Pipe

From my previous post, we discussed that the Compose and Pipe Combinators are used to glue successive functions together. In this case, `CountSlices` needs to be calculated before `GetMidSliceIndex`. Whenever I see the word before, it almost always refers to the Pipe Combinator. Using the Pipe Combinator, `GetMidSliceIndex` turned into the following composition:

``````let DivideBy = denominator => numerator => int(numerator) / denominator
let GetMidSliceIndex = axis => Pipe (CountSlices(axis)) (DivideBy(2))

// Another implementation
let GetMidSliceIndex = axis => image => int(CountSlices(axis)(image)) / 2
``````

The Pipe Combinator returns a function that takes in an `Image` and passes it to the first function `CountSlices axis` and then it divides the result by 2. Whether or not one implementation is better than the other is up for debate, but in this case, it's an example of the Pipe Combinator in action.

## Enter the S-Combinator

The S-Combinator is also known as the Substitution Combinator or Starling Combinator. As it's other name implies, The S-Combinator is used to substitute arguments in a function by computing them with other functions. This is really handy when one or more of your arguments depend on the value of another argument.

In this case, `Slice2D` depends on `GetMidSliceIndex` to compute the index. Both of these functions also have dependencies to the `axis` and `image`. There are several S-Combinators, but here are the two that I used:

``````// AKA the Chain Combinator
let S_ = f => g => x => f(g(x))(x)

// AKA the Converge Combinator
let S2 = f => g => h => x => f(g(x))(h(x))
``````

The S_-Combinator (From now on referred to as the Chain Combinator) basically computes the first argument for the function f with g using the input argument x. It then applies x as the second argument.

The S2-Combinator (From now on referred to as the Converge Combinator) is almost the same except that it takes in a third function h to compute the second argument for f.

### Chain Combinator in Practice

So how does this work in practice. Let's first consider the Chain Combinator. If we assume that `GetMidSliceIndex` already has it's `axis` applied, we essentially get a function with the signature `(image: Image) => (index: uint)`. Using the Chain Combinator as a base, we can see the following:

``````let Chain = f => g => x => f(g(x))(x);

let CreateThumbnail = axis => image
=> Chain(Slice2D(axis))(GetMidSliceIndex(axis))(image)
``````

In the above example `Slice2D(axis)` represents `f`, `GetMidSliceIndex(axis)` represents `g`, and `image` represents `x`. With those in place, we can see that `Chain` applies `image` to `GetMidSliceIndex(axis)` and pass that into `Slice2D` as the second argument because `axis` is partially applied. Finally, `image` is then applied to `Slice2D` to create the thumbnail.

This was good, but I didn't like how `axis` had to be partially applied. If you're keen enough, you can see that the we end up with three functions here: `Chain`, `Slice2D` and `GetMidSliceIndex`. What's more coincidental is that the argument for `Slice2D` and `GetMidSliceIndex` are both `axis`. This matches the functional interface of the Converge Combinator! Coincidence? I think not!

### Converge Combinator in Practice

Given the following:

• `Chain` as `f`
• `Slice2D` as `g`
• `GetMidSliceIndex` as `h`
• `axis` as `x`

the above code can be refactored to the following:

``````let Chain = f => g => x => f(g(x))(x);
let Converge = f => g => h => x => f(g(x))(h(x))

let CreateThumbnail = axis => image =>
Converge(Chain)(Slice2D)(GetMidSliceIndex)(axis)(image)
``````

The project I'm working on uses F#, so there's even more interesting things that can be done. Two things that F# will give us:

1. We can remove the brackets
2. Since image is an argument that gets applied, we can drop this argument as the result of `Converge` will return a function

The final implementation in F# is as follows:

``````let Pipe f g x = g(f x)
let Chain f g x = f(g x)(x)
let Converge f g h x = f(g x)(h x)
...
let DivideBy denominator numerator = int(numerator) / denominator
let GetMidSliceIndex axis = Pipe (CountSlices axis) (DivideBy 2)
let CreateThumbnail axis = Converge Chain Slice2D GetMidSliceIndex axis
``````

## Conclusions

So what are the pro's and con's of this? By having the individual functions fully unit tested and using commonly known functional patterns to compose this logic together, the compositions of these functions are guaranteed to work. This kind of programming produces extremely robust code with very little code. Less code usually leads to fewer bugs.

For this project, I'm the sole owner and supporter of it, but if this was a team effort, this code probably wouldn't fly. Is the code robust? Hell, yeah! Is the code maintainable? Yes, it is! Is the code readable? That depends. For a team of senior functional programmers, this would be fine, but if the team is made up of non-functional programmers, then this probably wouldn't work.

Combinator patterns exist in pretty much all the code we write. Recognizing these patterns are extremely useful and can help you design better interfaces. However, at the end of the day, if the code doesn't communicate well with your team, it doesn't matter how robust or well proven the patterns are because your team won't support it.