In this article, we’ll explore higher-order functions and think about how we can use them to make our programs more expressive. At the same time, we need to strike a balance between perceived complexity and expressiveness.
What is expressiveness
One of the most basic concepts in programming is that functions can call other functions.
When a function can call other functions, and when a function can be called by more than one other function, we can do a lot of interesting things. Many-to-many relationships between functions make programs more expressive than one-to-many relationships. We can give each function a single responsibility and then name that responsibility; We can also ensure that there is one and only one function that does a particular job.
Many-to-many functional relationships make it possible to have a one-to-one relationship between functions and responsibilities.
Programmers often say that a language is very expressive, yet there is no universal standard for what is expressive. Most programmers agree that an important feature that makes a language “expressive” is that it makes it easy for programmers to avoid unnecessary verbosity in their code. If a function has more than one responsibility, this can make the function itself bulky and unwieldy. If the same responsibility has to be implemented more than once, this creates redundancy in the program.
If the functions in the program have a single responsibility, and all responsibilities are implemented only once by a single function, the program avoids unnecessary prolix.
In summary, the many-to-many relationship between functions makes it possible to write highly expressive programs. Programs that don’t have this feature are very expressive.
The flip side: perceived complexity
However, with great power comes great responsibility. The downside of many-to-many relationships is that as a program grows in size, the number of things it can do increases dramatically. Expressiveness is often in conflict with perceived complexity.
To make the above statement easier to understand, let’s draw a diagram by analogy. Each function is a node, and the calling relationship between functions is a line. Assuming there is no dead code in the program, each structured program forms a connection diagram.
Given a known number of nodes, the number of join graphs that can be drawn at these nodes forms a sequence of integers A001187. (Translator’s Note: This is hardcore math)… (Math, do not understand, omitted translation)… In all, just 10 functions can form more than 34 trillion program combinations…
The explosion in program flexibility has forced programmers to exercise restraint. The benefits of a one-to-one relationship between functions and responsibilities are offset by the resulting infinite complexity. Imagine how difficult it is to understand a program of this complexity.
JavaScript provides tools to help alleviate this problem. Its blocks create namespaces, as do ES Modules. It will soon have private object properties. (Translator’s note: Public and private class attributes are already in State 3 draft)
Namespaces restrict potentially large diagrams to smaller diagrams, and each diagram can be connected to other smaller diagrams (modules) in a controllable number of ways. This way, you still get a big picture, but your picture is much less combinable. That way, it’s easier to figure out what it does and how it does it.
We have just described, in an almost intuitive way, a way of designing good software systems that gives the programmer the flexibility that comes with many-to-many relationships between entities, while at the same time giving the programmer the initiative to restrict how entities can be connected.
But notice that we’re not saying there’s a mechanism for doing both. No, we’re just saying that there’s one tool that helps us improve expressiveness, and another tool that helps us limit perceived complexity in our programs; And there is a conflict between the two.
Now that we have an intuition about this, let’s look at some higher-order functions. From these functions, we try to see if expressiveness and perceived complexity exist together.
Higher-order functions
If a function takes several other functions as arguments and/or returns the function as a value, we call it a higher-order function, or HOFs. Languages that support HOFs also support first-class citizen functions, and almost all support dynamically created functions.
Higher-order functions give programmers more ways to deconstruct and combine programs, and as a result, programmers have more responsibility to write in a function-to-function way. Let’s look at an example.
Legend has it that good companies always require graduate applicants to have a coding interview.
For example, merge two sorted lists together. This kind of problem is not too difficult, but also has real-world application scenarios. Here’s a naive answer:
function merge({ list1, list2 }) {
if (list1.length === 0 || list2.length === 0) {
return list1.concat(list2);
} else {
let atom, remainder;
if (list1[0] < list2[0]) {
atom = list1[0];
remainder = {
list1: list1.slice(1),
list2,
};
} else {
(atom = list2[0]),
(remainder = {
list1,
list2: list2.slice(1)}); }const left = atom;
const right = merge(remainder);
return [left, ...right];
}
}
merge({
list1: [1.2.5.8].list2: [3.4.6.7]});//=> [1, 2, 3, 4, 5, 6, 7, 8]
Copy the codeHere is a function that sums a list of numbers:
function sum(list) {
if (list.length === 0) {
return 0;
} else {
const [atom, ...remainder] = list;
const left = atom;
const right = sum(remainder);
return left + right;
}
}
sum([42.3.- 1]);
/ / = > 44
Copy the codeWe deliberately write these two functions in the same structure. This structure is called linear recursion. Can we pull out this common structure?
Linear recursive
Linear recursion is simple:
- Look at the input value of the function, can we pull out one of the elements of that value?
- If not, what value should we return?
- If so, let’s separate the value into one element and the rest.
- Put the rest of the elements into the same linear recursive function, and then
- I’m going to make some sort of connection between what I separated out, and what I’m going to do with linear recursion of what’s left
Both of the functions we just showed you have this form, so let’s write a higher-order function to implement linear recursion. Let’s take one of these functions as an example to extract the common parts:
function sum(list) {
const indivisible = (list) = > list.length === 0;
const value = (a)= > 0;
const divide = (list) = > {
const [atom, ...remainder] = list;
return { atom, remainder };
};
const combine = ({ left, right }) = > left + right;
if (indivisible(list)) {
return value(list);
} else {
const { atom, remainder } = divide(list);
const left = atom;
const right = sum(remainder);
returncombine({ left, right }); }}Copy the codeWe are close to implementing the higher-order functions we want. The key part is to rename several variables:
function myself(input) {
const indivisible = (list) = > list.length === 0;
const value = (a)= > 0;
const divide = (list) = > {
const [atom, ...remainder] = list;
return { atom, remainder };
};
const combine = ({ left, right }) = > left + right;
if (indivisible(input)) {
return value(input);
} else {
const { atom, remainder } = divide(input);
const left = atom;
const right = myself(remainder);
returncombine({ left, right }); }}Copy the codeThe final step is to change these constant functions to parameters of a function that ultimately returns Myself:
function linrec({ indivisible, value, divide, combine }) {
return function myself(input) {
if (indivisible(input)) {
return value(input);
} else {
const { atom, remainder } = divide(input);
const left = atom;
const right = myself(remainder);
returncombine({ left, right }); }}; }const sum = linrec({
indivisible: (list) = > list.length === 0.value: (a)= > 0.divide: (list) = > {
const [atom, ...remainder] = list;
return { atom, remainder };
},
combine: ({ left, right }) = > left + right,
});
Copy the codeNow we can use the same properties between sum and merge. Let’s use Linrec to implement the merge:
const merge = linrec({
indivisible: ({ list1, list2 }) = > list1.length === 0 || list2.length === 0.value: ({ list1, list2 }) = > list1.concat(list2),
divide: ({ list1, list2 }) = > {
if (list1[0] < list2[0]) {
return {
atom: list1[0].remainder: {
list1: list1.slice(1),
list2,
},
};
} else {
return {
atom: list2[0].remainder: {
list1,
list2: list2.slice(1),}}; }},combine: ({ left, right }) = > [left, ...right],
});
Copy the codeWe can go further!
Binary recursive
Let’s implement a function called binrec, which implements binary recursion. The example we started with was merging two sorted lists, and the merge function is often used in merge sort.
Binrec is actually simpler than Linrec. Linrec also divides the input values into single elements and residual elements, and Binrec divides the problem into two parts and applies the same algorithm to both parts:
function binrec({ indivisible, value, divide, combine }) {
return function myself(input) {
if (indivisible(input)) {
return value(input);
} else {
let { left, right } = divide(input);
left = myself(left);
right = myself(right);
returncombine({ left, right }); }}; }const mergeSort = binrec({
indivisible: (list) = > list.length <= 1.value: (list) = > list,
divide: (list) = > ({
left: list.slice(0, list.length / 2),
right: list.slice(list.length / 2),}),combine: ({ left: list1, right: list2 }) = > merge({ list1, list2 }),
});
mergeSort([1.42.4.5]);
//=> [1, 4, 5, 42]
Copy the codeA little more imaginative, based on binary recursion, we can also extend multivariate recursion, where the problem is divided into an arbitrary number of symmetric parts:
function mapWith(fn) {
return function* (可迭代) {
for (const element of iterable) {
yieldfn(element); }}; }function multirec({ indivisible, value, divide, combine }) {
return function myself(input) {
if (indivisible(input)) {
return value(input);
} else {
const parts = divide(input);
const solutions = mapWith(myself)(parts);
returncombine(solutions); }}; }const mergeSort = multirec({
indivisible: (list) = > list.length <= 1.value: (list) = > list,
divide: (list) = > [
list.slice(0, list.length / 2),
list.slice(list.length / 2)],combine: ([list1, list2]) = > merge({ list1, list2 }),
});
Copy the codeWe could go on exploring an infinite number of higher-order functions, but the ones I’ve just shown are enough. Let’s go back and think about expressiveness and perceived complexity.
The relationship between higher order functions, expressiveness, and complexity
. (too wordy, repeat the previous content, do not translate)…… If two functions fulfill the same responsibility, our program is not DRY enough (don’t repeat yourself) and expressive enough.
What does a higher-order function have to do with this? As we just saw, sum and merge have different responsibilities in the solution domain, one for merging lists and the other for summing lists. But they share the same implementation structure, which is linear recursion. So, they’re both responsible for implementing linear recursive algorithms.
By extracting the linear recursion algorithm, we ensure that there is one and only one entity — Linrec — responsible for implementing linear recursion. Thus, we find that first-class citizen functions do help us achieve greater expressiveness by creating many-to-many relationships between functions.
However, we also know that this use of higher-order functions can increase the perceived complexity of a program if it does not take advantage of some language feature or architectural design to group functions. After grouping, the functions within a group still have rich relationships, but the relationships between groups are limited.
One-to-many and many-to-many
Let’s compare mergeSort with binrec and multirec respectively:
const mergeSort1 = binrec({
indivisible: (list) = > list.length <= 1.value: (list) = > list,
divide: (list) = > ({
left: list.slice(0, list.length / 2),
right: list.slice(list.length / 2),}),combine: ({ left: list1, right: list2 }) = > merge({ list1, list2 }),
});
const mergeSort2 = multirec({
indivisible: (list) = > list.length <= 1.value: (list) = > list,
divide: (list) = > [
list.slice(0, list.length / 2),
list.slice(list.length / 2)],combine: ([list1, list2]) = > merge({ list1, list2 }),
});
Copy the codeThe functions we passed to linrec and multirec are interesting. Let’s give them names:
const hasAtMostOne = (list) = > list.length <= 1;
const Identity = (list) = > list;
const bisectLeftAndRight = (list) = > ({
left: list.slice(0, list.length / 2),
right: list.slice(list.length / 2)});const bisect = (list) = > [
list.slice(0, list.length / 2),
list.slice(list.length / 2)];const mergeLeftAndRight = ({ left: list1, right: list2 }) = >
merge({ list1, list2 });
const mergeBisected = ([list1, list2]) = > merge({ list1, list2 });
Copy the codeLooking at the function names and the actual functions, you can see that some functions, such as hasAtMostOne, Identity, and Bisect, feel like generic purpose functions that we use when writing current applications or other applications. In fact, these functions can be found in some general purpose function libraries. They express common operations on lists. The identity function in Ramda is the same as here. The identity function and similar const always => x => y => x are not trivial, they only make sense in a particular context.)
BisectLeftAndRight and mergeLiftAndRight are more purposeful. They are unlikely to be used elsewhere. MergeBisected is a little bit more blended, and we may or may not use it somewhere else.
As emphasized at the beginning of this article, this many-to-many functional relationship can help us improve code expressiveness and create a one-to-one relationship between program entities and responsibilities. Bisect’s job, for example, is to split the list into two parts. We can have all other parts of the code call Bisect instead of doing this over and over again.
The more generic the interface or “behavior protocol” a function provides, and the more centralized and simple the responsibilities a function undertakes, the greater the function’s ability to create many-to-many relationships. Therefore, when we write higher-order functions like multirec, we should design these functions in such a way that they take as arguments generic purpose functions that do only simple duties.
We can also write functions like bisectLeftAndRight and mergeLeftAndRight. When we write like this, we have one-to-many relationships in our programs, because they have no general function other than being useful in the merge function. This limits the expressiveness of our program.
Unfortunately, this limitation does not necessarily mean a reduction in the perceived complexity of a program. Looking through the code, we can see that functions like bisectLeftAndRight don’t have much use elsewhere in the program. If we don’t use additional mechanisms such as module scope to limit the scope of these functions and make them easy to find, we can’t reduce the perceived complexity of the program.
Thus, it can be observed that certain programming techniques, such as writing highly specialized interfaces for functions or assigning complex responsibilities to functions, reduce the expressiveness of a program, but not its perceived complexity.
What do higher-order functions have to do with frameworks and libraries
Roughly speaking, frameworks and libraries are simply collections of classes, functions, and other code. The difference is that frameworks are designed to call our code, libraries are designed to be called by our code.
Frameworks often expect us to write functions or other program entities with very specific and specific interfaces and behavior protocols. For example, Ember requires us to extend its base classes to create components, rather than using the normal ES6 Class. As we have explained above, when we write specialized interfaces, we limit the expressiveness of our programs without reducing their complexity.
This means that we are writing code for the framework so that the framework author does not have to worry about creating a many-to-many relationship between the framework code and the user code. For example, we can’t use JavaScript mixins, subclass Factories, and Method Advice when writing an Ember class. We had to use specific meta-programming tools that Ember provided, or plug-ins developed specifically for Ember.
Frame-oriented code is more one-to-many than many-to-many, which reduces its expressiveness.
Libraries, by contrast, are designed to be called by our code. Most importantly, libraries are called by many, many teams with very different programming styles, giving library authors an incentive to write functions with common interfaces and simple responsibilities.
Library-oriented code is more many-to-many than one-to-many, which makes it more expressive.
Is framework-oriented code all bad? In fact, not necessarily, just a choice. Frameworks provide a standard way of doing things. The framework promises to help us do more, especially when it’s very complex.
Ideally, although our code will become less expressive under the framework, our goal is to write less code. We use other tools to reduce the perceived complexity of our programs.
From our exploration of higher-order functions such as Linrec, Binrec, and multirec, we discovered the contrast between specialized and generic interfaces, and the choice between frameworks and libraries.
【 译 文】From higher-order Functions to Libraries And Frameworks
Translation postscript
The higher-order functions exemplified in this article are implemented recursively. In most cases, merge and sum are implemented iteratively. So, what else do these examples do? What are the use scenarios for multirec multivariate recursion? Stay tuned for the next translation: Recursive Data Structures and Image Processing
About us
We are ant Insurance experience technology team, from ant Financial Insurance business group. We are a young team (no historical technical stack baggage), the current average age of 92 years (excluding a maximum score of 8x years – team leader, excluding a minimum score of 97 years – intern junior brother). We support almost all of Ali Group’s insurance businesses. In 18 years, our mutual treasure made a stir in the insurance industry, and in 19 years, we have several heavyweight projects in preparation and mobilization. Now with the rapid development of the business group, the team is also expanding rapidly, welcome to join us
We want you to be: technically solid, in-depth in a field (Node/ interactive marketing/data visualization, etc.); Good at precipitation and continuous learning in learning; Optimistic and outgoing personality.
If you are interested in joining us, please send your resume to [email protected]
Author: Ant Insurance – Experience Technology Group – Kusatsu
Gold nuggets address: Serialcoder