When implementing React Optimization techniques for Raytracing on the Web, I had a requirement that the loop not start from start to end, but start in the middle and go sideways. Implement the following effect
Images are presented incrementally, not from top to bottom, but from the middle.
At first, I toggled with a for loop plus various variables, which was a pain to debug and eventually made me lose patience. Maybe there was a straightforward solution to this need, but I didn’t think of it at the time.
So I took out a powerful weapon from the Programming Arsenal and solved this little problem. And found that this anti-aircraft gun hit the mosquito scene, very suitable as an example to explain. Hence this article.
Combinator Pattern is a common Pattern in Functional Programming. Parsec, a well-known Parser library in Haskell, adopts this Pattern, also known as Parser Combinator.
The word Combinator has many meanings. Here, the Combinator Pattern describes a computational structure that is combined Primitives and Combinators.
I’d like to emphasize the term “computational architecture”, which I think has great dissemination value even though it’s not really a term. We’re all familiar with the idea that programs are data structures plus algorithms, and they’re really useful when it comes to writing underlying code. But for application-level code, we need a different perspective, so I want to emphasize computational structure.
Computational structure, in my opinion, is a special way of writing algorithms. There are many different ways to write the same algorithm. Some have good performance, some have less code, some are intuitive and easy to read; And there are some that are more combinable, more deductible, that can present a hierarchical process.
Let’s take the middle unfolding loop algorithm as an example. Demonstrate how the Combinator Pattern can present an elegant computational hierarchy.
Let’s start with the first component of Combinator Pattern, Constructor. It’s responsible for putting an ordinary piece of data into a computational structure. This is equivalent to constructing a calculation that looks like this: a -> m a.
A is any value, m a is the calculation that can be generated based on a.
The Constructor method in ES2015 Classes and the Constructor method in function Prototype is an embodiment of the Constructor method in ES2015 Classes. Constructor expresses a generic construct, and class Constructor is one of the generic constructs used to construct instances of the class.
And the second component of Combinator Pattern, Combinators. It’s responsible for converting one computational structure into another, or combining two computational structures into one. Anyway, it’s a transition from computational structure to computational structure. The function type looks like this: m a -> m b.
M a is the calculation based on what a can produce, m b is the calculation based on what B can produce. M a -> m b converts computations that can be generated based on A to computations that can be generated based on B.
If you find this abstract and strange, look at the following example to get a feel for it.
As mentioned above, Constructor and Combinators have no fixed idea. It’s up to us to define them and meet the criteria. Instead of using Class, we’ll define an iterator to represent a computation structure that, when called next, evaluates the next value.
Iterator can be thought of as {next}, which has a next method to produce the actual computation.
Constructor, then, is what turns an A into an iterator. All Generator functions here are natural Constructor. Since the argument to Generator Function is A, the return value is iterator. So it satisfies: a -> {next}.
Our incre function is an iterator computed structure Constructor. You give it the start, end, and step arguments and it returns an iterator computed structure that, on repeated calls to next, evaluates each of the qualified values.
Our decre function is also a Constructor for iterator, which contains the reverse of the incre function, one from small to large and one from large to small.
Our range Function is also a Constructor, although it is not a Generator Function, although other constructors are used inside it. This does not change its function type; it still constructs an iterator from the start, end, and step arguments. It contains a calculation structure such that if start < end is a small to large calculation, and if it is a small to large calculation.
Our toggle function, however, is more than Constructor. It takes two iterator computations and returns a new iterator computations. The new structure involves calculations that keep switching between a and B until they run out of values.
React calls it Higher Order Constructor, if you like. But Combinator is a better word for me.
Constructor and Combinator, both functions, return a computational structure (in this case iterator). The difference is that Constructor’s arguments are non-computational structures, whereas Combinator’s arguments contain computational structures. This is a useful distinction.
Constructor :: a -> m a
Combinator :: m a -> m b
With range and toggle, we can easily combine a new Constructor. Spread is internally based on range and toggle, realizing the computing structure of toggle between middle -> start and middle -> top.
This is exactly what we want for the middle unfolding loop algorithm.
As you can see, we don’t have a bunch of local variables in a function, change the values in a for loop for various conditions, and then solve one-time problems. We simply implement the behavior described by function names such as Incre, Decre, range, toggle, spread, etc.
We gradually solved several kinds of problems. They are generic and can be reused in other scenarios. And incre, Decre, range, toggle, spread, any function, all conform to the programming principle of only doing one thing and doing it well; Any one of them, they’re individually testable.
We no longer get lost in tracking local variables inside complex functions, wasting a lot of debugging time. We can easily extend new Constructor and Combinator based on our needs. Such as:
In just three lines of code, map implements the Combinator, which returns a calculation specified by the f parameter function. In the example above, double the number.
Is there an RXJS deja vu at this point?
Yes, you can also easily implement operators in RXJS, such as Filter and Take.
When multiple Combinators work together, we need to write a helper function called PIPE to make it look easier to read. After finalized the future Pipeline Operators characteristics, which can eliminate pipe, use | > symbol instead.
As you can see, the Map, Filter, Take, etc. Combinators code is concise and just does what it’s supposed to do.
Concat, for example, is simpler, with just two for-of + brainless yields.
So what does this iterator have to do with RXJS? Why are their apis so consistent?
It can be very simple to answer this question. RXJS is also a Combinator Pattern. As Pattern, it is normal for their apis to be similar.
RXJS of, Observable.create, etc., belong to Constructors. Functions like concat, Merge, combineLatest, etc., are Combinators. All Rxjs Operators are Combinators.
Operators is of type A -> M b -> M C. Concat is (m a, m b) -> m C. It seems different. In fact, the higher order function of multiple single-parameter, as a special case of multi-parameter function. Or think of a multi-parameter function as a special case of a number of higher-order single-parameter functions. They’re consistent. You curry or uncurry each other, and this process produces no actual computation (i.e. the final output is the same).
Also, if you compare RXJS to our iterator’s computational structure. You’ll notice that iterator only has {next} calculations. RXJS contains a much more complex structure. First, its a -> {subscribe} returns a subscriptable structure.
Subscribe ({next, completed, error}) passes in a structure containing the next, completed, and error calculations, and returns unsubscription.
As a result, RXJS contains far more layers and capabilities than iterator. To implement complex calculations in RXJS using Iterator, you have to do a lot of extra processing yourself.
As you can see, from the perspective of computational structures, we have a solid way of analyzing the actual expressiveness of a library. We know that just because two apis look alike doesn’t mean they are equally capable.
Primitives are Primitives and Constructor, and Primitives are Primitives.
It’s the most interesting part of the Combinator Pattern.
As we saw in the previous section, new Constructor and Combinator can be written continuously. As long as they meet the type and behavior requirements of A -> A and A -> B. It’s an open perspective. We have also seen that you can use other constructors and Combinators in one Constructor or Combinator. At this point, we have a convergent perspective.
What Constructor and Combinator cannot be combined by other constructors and Combinators?
Can we find a group of Constructors and Combinators from which other Constructors and Combinators can be constructed?
If we can, we can call it Primitives.
For example, our Incre and Decre programs are so similar that which one is Primitives?
And the answer is, with reverse Combinator, you implement either incre or decre, one implements the other.
Primitives are not all Primitives. In many cases, it has to do with our own choices. This is not capricious or playful; it is a valuable trait. Some Primitives are harder to achieve, while others are simpler and can express each other. So we have the opportunity to choose the easy one.
More interestingly, we can sometimes implement a Constrcutor manually, even if Primitives and Combinators can be combined.
For example, when we implement decre with incre and reverse, it gets the same output but different overhead. All calculations in Incre are fully enabled internally in Reverse and then printed in reverse. It can’t say that the first one only produces one calculation. Decre, which is implemented manually, can be calculated on demand.
We can assume that Primitives and Combinators have given us some Free apis that allow us to create more complex computational structures for Free or for less. But Free comes at a price. In the rapid prototype development stage, we can use Combinator Pattern to quickly get the usable computational structure; Once the function is stable, some of the Constrcutor and Combinators are manually optimized for refactoring.
As shown above, instead of using range and toggle to construct the spread, we directly inline the calculation procedures they contain, reducing the performance overhead.
We were surprised to find that this refactoring is exactly what we wanted with local variables and loops in the first place. While we were debugging for a long time and getting nothing, today we can easily get it by unpacking some Constructor and Combinators. It’s really an amazing process.
On reflection, we find that directly using multiple local variables and loops is essentially a process of trial and error by brute force to figure out how many calculations are needed for spread. The interaction of multiple local variables makes the code difficult to debug.
By using the Combinator Pattern, we can isolate many Constructor and Combinator structures, which have less code, can be tested separately, and can combine more complex computational structures. When we use them to combine spread, we know what the necessary calculations are in spread, and then perform a clear, rhythmic, planned refactoring optimization.
And with our knowledge of the Primitives relationship, we can deduce a new idea. For example, we already know that incre and Decre can implement each other through reverse. Therefore, instead of tracing two local variables incre and decre, we simply trace one and derive the other through reverse/ reverse etc.
As shown above, we only trace the local variable count, and obtain incre and decre through reciprocal reverse operation of +offset and -offset, realizing the same algorithm.
From scratching our heads and blindly trying and failing, we can now implement the spread function in three different ways. This is the strength of the Combinator Pattern. As a methodology, it can lead and inspire us to solve previously unsolvable problems and better solve solved problems.
This article is just the tip of the iceberg in functional programming. More useful weapons, waiting for us to learn. You can learn more by studying functional languages like Haskell. And then applied to front-end development and other daily work to optimize our code.
If you’re wondering what it looks like to write in Haskell, here’s a rough translation. Translate the JS version to Haskell.
For more application cases of Combinator Pattern, you can click on “Revealing the Most promising API of VUE-3.0” to view the content, where reactivity value is regarded as a computational structure. And a combination of reactivity View and other more complex computing structures.