2024-04-06
A combinator is a kind of function. Specifically, it’s a function that applies
its arguments—and only its arguments—to each other in a particular shape
and order. The number of possible shapes is of course infinite; but in practice
a few fairly simple shapes crop up more often than others, and those specific
shapes have names. A very few of them are so common and so famous that their
names and shapes are already well-known to programmers; because they’re
well-known there are often functions available in standard libraries that apply
their arguments in shapes corresponding to them. Function composition is one:
many languages available today recognize that f(g(x)) is a sufficiently
common pattern, and that, for instance, writing xs.map(x => f(g(x))) is
sufficiently common, inconvenient, and at times error-prone, that they allow
the programmer to write xs.map(compose(f, g)) instead.
It therefore seems worthwhile to push at the boundaries of this set of well-known shapes; are there others that crop up often enough that we can give them names, and in so doing abstract away some of the repetitive guts of our code?
Combinatory logic—the field from which we draw the name and, loosely, the concept of combinators—is adjacent to computer programming in several different directions. It’s often of interest to computer programmers, though usually because those programmers are interested in logic itself, recreational mathematics, or programming language design; thus much of the available material, if you squint, can be applied to how we write our programs and whether we can write them better—but you’ve got to squint. The material is rarely straightforwardly applicable for the everyday programmer.
It is, for instance, often written in a minimal lambda calculus syntax—\(\lambda{}xy.xyy\) and the like—which is more readable to the theorist. It often also dwells on minimal systems, like the SKI calculus, whose simple elements are sufficient for the construction of arbitrarily complex expressions. A useful and intriguing theoretical basis but no more useful to the working programmer than learning how to write programs for a Turing machine.
We must also talk about The Bird Book. Smullyan’s To Mock a Mockingbird is doubtless the most popular treatment of combinatory logic. It’s beloved to many people who love math and logic puzzles, programmers and non-programmers. In it, we’re introduced to the various combinators under the guise of birds whose names begin with the same letter as their traditional academic names. 𝝟, for instance, is introduced as the Kestrel. Instead of dealing with function application, Smullyan’s birds say each other’s names.
Is this a good idea? From a pedagogical perspective, I’m not sure; the metaphor has absolutely never landed with me and the actual book is written with lots of other logical and mathematical verbiage, so I don’t know how far it gets you.
Where I do feel on firmer footing is to claim that whatever the merits of calling \(\lambda{}xy.x\) “Kestrel” in the context of recreational mathematics, that name becomes even less useful in the context of writing computer programs.
In the modern era, Conor Hoekstra has probably done the most to document and popularize the use of combinators within computer programming—or at least to view computer programming and programming languages according to the extent to which they enable the use of combinatory function application forms, and the extent to which that use results in more concise, more elegant programs. He is the maintainer of https://combinatorylogic.com, which has quite a few resources worth reading, listening to, and watching (many of which he himself has produced).
Hoekstra is an array language enthusiast. This is not a coincidence: one of the most dramatic effects obtainable in programs through the use of combinators is that of tacit programming, that is, code that “does not refer to values by name”, and it’s in the discourse around the array languages—starting with J and expanding to the wider family of so-called “Iversonian” languages—that one most reliably encounters discussion and celebration of tacit forms.
And it’s Hoekstra who has most effectively beat the drum that the array languages’ so-called trains—one of the critical ways that those languages enable tacit code—are best understood as extremely concise syntactic realizations of particular and particularly useful combinators—in the case of J, for instance, the 𝗦 and 𝝫 combinators, among others.
The work that follows can be understood as an attempt to continue in the direction in which he has set out; in part by embracing that particular class of functions as worthy of consideration in the writing of computer programs, and in part by more completely separating the topic of combinators from the array-language context in which Hoekstra most often discusses them.
Hoekstra is an array language enthusiast (as am I) and holds that the array languages are by far the best place to make full use of combinators in programming; I don’t disagree, but I think that in order to present them clearly to the wider community and to hopefully convince that community of their utility, it’s worth going further than he has in presenting them in as “neutral” a context as possible; the array languages are fascinating and powerful, but also forbidding and at times obscure.
I want to try to isolate these concepts not just to make them as accessible as possible: it also remains an open question whether a function for 𝝫 would be of use to the programmer in a more “generic” context like, say, a Javascript codebase that made sufficient use of higher-order functions—or whether its utility only emerges in the full syntactic and operational context of a language like J.
I want to propose that the value of tacit programming is analogous to the value of functional programming: when applied in the right places, it allows the programmer to “abstract away” repetitive behaviours consisting of many moving parts into operations that are conceptually simpler, more uniform, and can be applied to a wide variety of situations. When those core operations have been intuitively grasped, the resulting code is easier to understand; and the appearance of fewer of those moving parts means fewer places for bugs.
Stripped of all of its theoretical apparatus, the higher-order function
map—well-known to many programmers, functional and otherwise—is “just”
the simplest form of structure-preserving iteration. Nevertheless, its value in
an everyday programming context is that this form of iteration is easy to
conceptualize, form a mental model of, and predict the behaviour of.
Critically, incorporating the universal name map into our vocabulary allows
us greater economy with names inside of our code. Observing a paradigmatic
invocation of map:
const adjustedScores = []
for (const score of scores) {
adjustedScores.push(Math.abs(score))
}
becomes
const adjustedScores = scores.map(Math.abs)
We see that we have saved quite a bit of typing. But we have also eliminated
one name, score, entirely; the conceptual inventory of our code has
decreased by precisely one. We might even then say that the number of names
eliminated from our code, without any of its sense being lost, is a crude
measure of the degree to which we have been able to abstract it.
Just as map—once we can recognize the patterns in our code that it can
replace—allows us to simplify both the code’s text and its conceptual
inventory, so too do the combinators: giving universal names to certain fixed
patterns of function application, in exchange for a greater economy of the
local, domain-specific names in our code.
So we come to the problem of names. I’ve been using bold sans-serif single
letters up till now, because that’s what Haskell Curry and WVO Quine did in the
literature of combinatory logic, following Schönfinkel. These are all well and
good in a theoretical context. But to our purposes, the name 𝗕 is no better
than Smullyan’s Bluebird. Neither one gives us the slightest conceptual
toehold when it comes to remembering what it does. So we call it function
composition instead; the relationship between “composition” and f(g(x)) is
not unimpeachably pellucid but it’s a start.
The way forward is less obvious with the more exotic patterns. In J, we call 𝝫
a “fork”, because that’s what a diagram of its function application looks like;
in Haskell, they call it liftA2, for category-theoretic reasons that we won’t
go into. Fork isn’t that bad, but it’s not terribly suggestive; and it also
means something rather concrete in most computer systems.
Of the many, many combinators in the forest, there are some that are
useful to programmers. These are the ones that correspond to the most common
patterns of function application that your average programmer tends to
encounter, and thus, the ones that it’s worthwhile to give names to. A very
few—I count identity and compose—are so common that they have names
that are widespread and sufficiently meaningful. As to the rest: we might
imagine a world where, someday, they’re part of the standard library of every
programming language. To get there, their corresponding patterns need to be
trivially recognizable by any programmer, as trivially as x => x. To get
there: I can’t escape the conclusion that we need to give them better names.
Names that relate concretely, or as concretely as possible, to what they do;
names that are concise but not at the expense of their meanings.
To go with those names:
x => x above), not because I particularly like it, but because
it’s widespread.What follows is such an attempt. In cases where a combinator already has a common name, or where some literature—the Haskell standard library, array language discourse—has established a sufficiently reasonable candidate, I’ll use that; otherwise I’ll try to come up with something myself.
For some existing motivating examples, see:
If convenient, I will reproduce them shamelessly here.
Further, I’m indebted to the members of the APL Farm for additional motivating examples.
const identity = x => x
identity is easily understood as a no-op; it’s in the context of other
functional programming techniques that the need for such a function arises.
Whereas, in a less functional style, we might have an if statement combined
with a mutating operation, when using techniques from functional programming we
can easily find ourselves needing a function which means “do nothing”.
const maybeAbs = shouldNormalizeNegatives ? Math.abs : identity
return nums.map(maybeAbs)
function constant(x) {
return y => x
}
The case for constant is similar to that for identity; in an imperative
context, it is almost always superfluous. In a context making use of
higher-order functions, it often has a role to play.
const maybeRedact = shouldRedactNames ? constant("**REDACTED**") : identity
return names.map(maybeRedact)
function compose(f, g) {
return x => f(g(x))
}
The following example is restricted in scope, but only because for simplicity’s sake
we’ve defined compose to take exactly two arguments. An industrial strength
compose should probably take any number of functions, where the extension
from 2 to \(n\) is hopefully self-evident.
const cleanDatum = compose(removeUndefineds, coalesceNaNs)
const cleanedData = dirtyData.map(cleanData)
Just as we can imagine a variadic compose, where compose(f, g, h) is
equivalent to compose(f, compose(g, h)), and so on: we can also imagine that
an industrial strength compose might return a variadic function, that is,
that the result of compose should pass not just x to the innermost function
but ...x, with all subsequent functions expecting a single argument.
function composeN(f, g) {
return (...x) => f(g(...x))
}
const absoluteDifference = composeN(Math.abs, _.subtract)
return absoluteDifference(9, 13) // => 4
function apply(f) {
return xs => f(...xs)
}
When applied to a single argument, apply is redundant; apply(f)(x) is
equivalent to f(x). When f is a function that takes multiple arguments,
there’s often syntactic sugar to apply it to some variable xs that contains
multiple values: as seen above, in Javascript, it’s the spread operator ...
(there’s also the appropriately-named prototype method apply). In
Janet, it’s splice, spelled ;, as in (f ;xs). The functional form apply, on the
other hand, allows tacit forms to be used in a functional style.
const basesAndExponents = [[0, 1], [1, 2], [3, 5], [8, 13]]
return basesAndExponents.map(apply(Math.pow)) // => [ 0, 1, 243, 549755813888 ]
function flip(f) {
return (x, y) => f(y, x)
}
We could imagine standalone functions to permute any number of arguments; in practice, three or more arguments that need to be rearranged should probably be bound to local variables and called explicitly. On the other hand, when two arguments need to be reversed, the effect is quite intuitive.
const exponentsAndBases = [[0, 1], [1, 2], [3, 5], [8, 13]]
return exponentsAndBases.map(apply(flip(Math.pow))) // => [ 1, 2, 125, 815730721 ]
function duplicate(f) {
return x => f(x, x)
}
const square = duplicate(_.multiply)
return square(6) // => 36
const left = (x, y) => x
const right = (x, y) => y
function recombine(f, g, h) {
return x => f(g(x), h(x))
}
recombine can be seen as a generic form for functions that need to reuse
their arguments in more than one position.
We’ll appropriate the canonical example from demonstrations of J: the arithmetic mean of a sequence of values is the sum of those values divided by the length of the sequence.
const mean = recombine(_.divide, _.sum, _.size)
return mean([0, 1, 1, 2, 3, 5, 8, 13]) // => 4.125
const minMax = recombine(Array.of, _.min, _.max)
const spanOfValues = recombine(_.subtract, _.max, _.min)
const values = [1, 1, 2, 3, 5, 8, 13]
return minMax(values) // => [ 1, 13 ]
return spanOfValues(values) // => 12
In the same way that we can imagine a variadic extension of the higher-order
function produced by compose, we can imagine one for the higher-order
function produced by recombine. It can be extended to pass ...x to both g
and h, while preserving the existing behaviour.
function recombineN(f, g, h) {
return (...x) => f(g(...x), h(...x))
}
const plusOrMinus = recombineN(Array.of, _.add, _.subtract)
return plusOrMinus(13, 8) // => [ 21, 5 ]
In researching this example, I was astonished to learn that there’s no native way in the Javascript standard library to split an array at a given index.
const splitAt = recombineN(Array.of, _.take, _.drop)
return splitAt([0, 1, 1, 2, 3, 5, 8, 13], 5) // => [ [ 0, 1, 1, 2, 3 ], [ 5, 8, 13 ] ]
There’s a special case of of recombine that we might see cropping up fairly
often: an operation between some value, and a function of that same value.
If we like, we could spell that thus:
x => f(x, g(x))
But we can also spell it as an application of recombine that has identity as
either g or h. This has the same behaviour:
const isPalindrome = recombine(_.isEqual, _.reverse, identity)
return isPalindrome([0, 1, 0])
/**
* A harshad number is any number that is divisible by the sum of its digits.
*/
const isHarshadNumber = recombine(isDivisible, identity, sumOfDigits)
const eachValueIsUnique = recombine(_.isEqual, identity, _.uniq)
return eachValueIsUnique([0, 1, 1, 2, 3, 5, 8, 13]) // => false
return eachValueIsUnique([0, 1, 2, 3, 5, 8, 13]) // => true
Since there’s no great and widespread name for this special case, I’ll prefer
to spell it in terms of recombine and identity.
The left and right functions are fairly specialized but can come in handy
in the cases covered by combineN:
const percentageDifference = recombineN(_.divide, _.subtract, right)
return percentageDifference(12, 10) // => 0.2
As with duplicate: to go with left and right we can imagine functions
that return the third, fourth, etc. argument that they’re given, but it might
get unwieldy for functions of three arguments or more.
function under(f, g) {
return (x, y) => f(g(x), g(y))
}
const isAnagram = under(_.isEqual, _.sortBy)
return isAnagram("live", "evil")
Because under applies the same g to each argument passed to the resulting
higher-order-function, it’s also fairly intuitive to generalize that function
from 2 arguments to \(n\).
function underN(f, g) {
return (...xs) => f(...xs.map(g))
}
const areAnagrams = underN(_.isEqual, _.sortBy)
return areAnagrams("live", "evil", "veil")
Javascript syntax is widespread and often-understood; unfortunately, the base Javascript ecosystem, by itself, is not great for functional programming. Many of its functions are either operators or object methods, that can’t easily be passed in to higher-order functions.
In these examples we’ll often make use of the lodash library to fill in some of these gaps. ↩
The name for this combinator, which the literature calls 𝝫
and which J calls fork, is a novel suggestion of Nate Pinsky. ↩
The name for this combinator, which the literature calls 𝝭,
collides—unfortunately—with some existing nomenclature in J. J’s
Under has an analogous function, in that it applies some g to
one or more arguments and then applies some f to the results. The
difference is that J’s then attempts to undo g by calling the so-called
obverse of g on the result of the call to f.
The collision is regrettable, but nevertheless the most suggestive metaphor
for 𝝭 seems to be that it calls f under g. ↩
2024-04-14
In Combinatory Programming, we attempt to provide motivating examples for the various combinators identified as useful to everyday programmers.
The aim of that piece was to extract the basic concept of combinators from as much its context as possible, and present certain particularly useful combinators as higher-order functions callable inside of nearly any programming language, applicable to most styles of programming. In practice, of course, tacit forms—the style of programming that we can use combinator functions to achieve—are more at home in certain languages and certain contexts than others, and compose most nicely with other features of a programming environment: plentiful pure, first-class functions; partial application; and terse combinator syntax, among others.
In this supplement, we can dig deeper into some of those examples; where useful, expressing the same logic in multiple styles, and at times commenting on features of different styles or languages and the effects they produce.
const maybeAbs = n => shouldNormalizeNegatives ? Math.abs(n) : n
return nums.map(maybeAbs)
Here, maybeAbs is a function which either calls Math.abs on n or returns
it directly, depending on the value of shouldNormalizeNegatives. This is the
most explicit, referring directly to n by name three times, but also the
easiest to read.
const maybeAbs = shouldNormalizeNegatives ? Math.abs : identity
(def maybe-abs (if should-normalize-negatives math/abs identity))
(map mayb-abs nums)
The JavaScript and Janet versions behave the same: we bind either the
absolute-value function or identity to our new symbol depending on the
value of the conditional. In later examples, we’ll see less trivial usages of
identity.
is_between_negative_3_and_0 =: (<&0)*.(>&_4)
maybe_abs =: [`| @. is_between_negative_3_and_0
maybe_abs _5 _4 _3 _2 _1 0 1 2 3
_5 _4 3 2 1 0 1 2 3
Though we haven’t put it into our personal library of combinators, we can
imagine a function agenda that behaves like this:
function agenda(p, f, g) {
return x => {
if (p(x)) {
return f(x)
} else {
return g(x)
}
}
In other words, we can imagine a simple combinator that lets us express
conditional logic tacitly. J’s Agenda @. is such a function. In the slightly
silly J example above, we are able to reproduce behaviour closer to the
JavaScript example: rather than using a conditional to choose a function f or
g, which is then applied to some values, our J code takes a verb
between_negative_3_and_0, which is then called on every element of the
argument to maybe_abs. Thus we can use both f and g within a single
call. In this example, identity is spelled [.
const cleanData = datum => removeUndefineds(coalesceNaNs(datum))
const cleanedData = dirtyData.map(cleanData)
In the case of composed functions (as opposed to the minimal identity example
above), explicit code rarely has many advantages over tacit code. We have to
refer to datum twice, so:
But in addition to that, the explicit version is structurally complex. Nested function calls are difficult to read.
const cleanData = compose(removeUndefineds, coalesceNaNs)
(def clean-data (comp remove-undefineds coalesce-nans))
In both tacit versions, we avoid an unnecessary name in addition to obtaining a simpler structure, with less nesting.
clean_data =: remove_undefineds @ coalesce_nans
In J, function composition is an infix operator.
const absoluteDifference = (x, y) => Math.abs(x - y)
return absoluteDifference(9, 13) // => 4
const absoluteDifference = compose(Math.abs, _.subtract)
In this case, the explicit code requires us to bind to both x and y; in a
case like subtraction, which is so intuitively transparent, this seems
particularly unnecessary.
(def absolute-difference (comp math/abs -))
(absolute-difference 11 24) # => 13
The Janet code also takes advantage of the fact that - is a normal function,
and not an infix operator, while the JavaScript has to rely on Lodash’s
subtract to get a first-class function that does subtraction.
absolute_difference =: |@:-
The J code is another straightforward application of function composition. In
this case, however, the composition of subtraction with absolute value is
spelled |@:-, which is shorter than the variable name absolute_difference.
Array language practitioners will contend that this obviates the need for binding the verb to a name at all; why assign it to a variable name when it would require more characters than simply re-spelling it out each time?
One possible answer: it’s more straightforward to understand the semantics of
absolute_difference than of |@:-. I’m not a very experienced J programmer,
so I can’t argue one way or the other.
It’s worth calling out that function composition is traditionally written “to
the left”; that is, the innermost function is the last argument and the last
function to be applied is the first in the argument list. This maps cleanly to
traditional function call syntax—f(g(x)) has f and g in the same order
as (compose f g)—but ends up being harder to read, as the order of
application isn’t the same as the order of the syntax.
Many newer languages have syntax, or standard library functions, to effectively perform function composition in reverse, so that the call to the “combinator” (such as it is) can be read in the same order as function application.
For instance, in Janet we could natively write
(-> dirty-data (coalesce-nans) (remove-undefineds))
This is not properly a combinator, because it’s not a higher-order function.
It’s syntax for a particular tacit form of control flow; it represents the
actual application of those two functions to dirty-data.
Nevertheless we can imagine a so-called pipe that behaves just like compose
but in reverse order, which might feel more comfortable to those programmers
who have grown used to the conveniences of -> and its cousins.
const basesAndExponents = [[0, 1], [1, 2], [3, 5], [8, 13]]
return basesAndExponents.map(([base, exponent]) => base ** exponent) // => [ 0, 1, 243, 549755813888 ]
Absent apply, we explicitly destructure the two elements of the argument
value and then pass them back to Math.pow. This is relatively verbose, though
still readable. If we couldn’t avail ourselves of destructuring either, we’d be
forced to write
args => {
const base = args[0]
const exponent = args[1]
return base ** exponent
}
Which begins to feel quite clumsy indeed.
return basesAndExponents.map(apply(Math.pow))
(def bases-and-exponents [[0 1] [1 2] [3 5] [8 13]])
(map (apply math/pow) bases-and-exponents)
In the explicit example, we availed ourselves of JavaScript’s infix exponent
operator, **. In the tacit examples, we use their respective languages’
standard library pow function in order to be able to pass a first-class
argument to the apply combinator.
exponentsAndBases: (0 1;1 2;3 5;8 13)
pow: */#
pow .' exponentsAndBases
1 2 125 815730721
The K language isn’t really designed with tacit programming in mind, but, as a
member of the array family, it nevertheless has some features that make certain
tacit forms the most idiomatic way to write programs. One of them is that
apply is spelled .. Here .' means “apply each”, that is, it applies pow
to each pair in the list of pairs exponentsAndBases1.
We have used the flipped form exponentsAndBases here, because the tacit
form pow, without being flipped itself, expects the exponent first.
*/# is itself an example of compose; as a function of two arguments, it
applies # to them, creating an exponent-length array of bases, and then reduces
* over them. In K, unlike J, function composition is not an infix operator;
it’s accomplished simply by juxtaposing the two verbs # and */.
In JavaScript and Janet, juxtaposition is not very meaningful. On the other
hand, we will see later on that J relies heavily on juxtaposition, but assigns
the semantics of combinators more complex than compose to that syntax.
const exponentsAndBases = [[0, 1], [1, 2], [3, 5], [8, 13]]
return exponentsAndBases.map(([exponent, base]) => base ** exponent) // => [ 1, 2, 125, 815730721 ]
return exponentsAndBases.map(apply(flip(Math.pow))) // => [ 1, 2, 125, 815730721 ]
(def exponents-and-bases [[0 1] [1 2] [3 5] [8 13]])
(map (apply (flip math/pow)) exponents-and-bases)
applyThe minimal example for flip includes usage of apply, because that’s the
most natural way to imagine dealing with data consisting of multiple ordered
values, where the order must be changed.
However, we can also imagine cases where our combinator accepts a variadic function such that ordering comes into play. For instance:
function explicit(x, y) {
return [x ** y, y / x]
}
return explicit(2, 3) // => [ 8, 1.5 ]
const tacit = recombine(Array.of, Math.pow, flip(_.divide))
In this slightly artificial example, we want to both take some x to the y,
as well as divide y by x. In a case where the g and h of a recombine
call expect the same arguments, but in different orders, we can use flip with
one of them.
Up until now we’ve excluded from consideration the topic of partial functions; in practice, the easy availability of partial application makes more tacit programming convenient.
(def double (partial * 2))
In Janet, with a built-in partial function, we can trivially use partial
application to define double; we bind the first argument and produce a new
function that takes a single argument and multiplies it by 2.
(defn square [n] (math/pow n 2))
If we would like to define square in terms of math/pow, the same technique
isn’t naively applicable: in this case, the argument we want to bind is the
second one.
(def square (partial (flip math/pow) 2))
In this case, we can work in a tacit style by employing flip; now the
argument we want to bind is the first argument to the function, so we can pass
that flipped function directly to partial.
Another example, from a refactor of bagatto into tacit style. To be
refactored is a higher-order function which takes some attribute name and
returns a function that calls sort by getting that attribute.
(defn attr-sorter
[key &opt descending?]
(defn by [x y] ((if descending? > <) (x key) (y key)))
(fn [items] (sort items by)))
In tacit style, this becomes:
(defn attr-sorter
...
(partial (flip sort) by))
By calling flip on sort, we obtain a function which can easily have our new
by applied as the first argument.
const mean = xs => _.sum(xs) / xs.length
return mean([0, 1, 1, 2, 3, 5, 8, 13]) // => 4.125
const mean = recombine(_.divide, _.sum, _.size)
(def mean (recombine / sum length))
mean =: +/ % #
In the case of J we see perhaps the starkest example of that language’s
orientation towards tacit programming. J combines a few syntactic
characteristics such that simple juxtaposition of verbs, that is, placing
syntactic verbs directly next to each other with no operator, triggers the
behaviour of application combinators. In the case of mean, we see that
creating a so-called 3-train of 3 verbs, f g h, creates a new verb whose
behaviour is analogous to recombine(g, f, h), called a fork in J.
const minMax = xs => [_.min(xs), _.max(xs)]
return minMax([1, 1, 2, 3, 5, 8, 13]) // => [ 1, 13 ]
const minMax = recombine(Array.of, _.min, _.max)
(def min-max (recombine array min-of max-of))
min_max =: <./ , >./
min_max 0 1 1 2 3 5 8 13
0 13
const plusOrMinus = (x, y) => [x + y, x - y]
return plusOrMinus(13, 8) // => [ 21, 5 ]
const plusOrMinus = recombine(Array.of, _.add, _.subtract)
As in Absolute Difference above, we see that functions of two arguments, when
treated explicitly, result in quite a bit of noise. Explicit plusOrMinus
takes two arguments, neither of which has a particularly meaningful name
(judging from the Lodash docs, under addition they should be named augend and
addend; under subtraction, minuend and subtrahend—but what
would we call them when both operations come into play?), each of
which then has to be referred to twice.
(def plus-or-minus (recombine array + -))
(plus-or-minus 13 8)
plus_minus =: - , +
1 plus_minus 2
_1 3
It’s worth noting that in both our JavaScript and Janet examples, the
distinction between a unary recombined function, like minMax, and a variadic
one, like plusOrMinus, is purely semantic: the syntax of application doesn’t
change when the number of arguments expected by g and h do.
In the J example, on the other hand, our application syntax is by default
infix; so while our min_max is written before its argument, our plus_minus
is written in between its two arguments, syntactically identical to its
constituent g and h.
Another example from bagatto shows a real-world refactoring using
recombine, as well as a non-trivial usage of constant.
item-getter is a function which takes a path of keywords and should return a
function that, given two arguments, will retrieve the attribute at that path in
the second argument.
A brief test to demonstrate the expected behaviour:
(deftest item-getter
(let [item {:foo {:bar :baz}}
getter (bagatto/item-getter [:foo :bar])]
(is (== :baz (getter {} item)))))
The explicit version:
(defn item-getter
[path]
(fn [site item] (get-in item path)))
Tacit:
(defn item-getter
[path]
(recombine get-in right (constant path)))
The tacit version, at least with all of the names spelled out, is not
shorter. And if we’re still trying to remember what recombine does, it’s
no easier to read.
But once we have internalized the behaviour of recombine a little bit, the
tacit example has the advantage of not having to introduce any additional names
at all. We can read that it returns a function that calls get-in on its
second argument and path.
function sum(xs) {
return xs.reduce((n, m) => n + m)
}
function std(xs) {
const mean = sum(xs) / xs.length
const squaredDifferences = xs.map((x - mean) ** 2)
const meanSquares = sum(squaredDifferences) / xs.length
return Math.sqrt(meanSquares)
}
return std([0, 1, 1, 2, 3, 5, 8, 13]) // => 4.136348026943574
pow: {*/y#x}
mean: %/ (+/;#:) @\:
std: % mean @ pow[;2]' -/ 1 mean\
In this example, we showcase the effectiveness of partial functions towards programming in a tacit style.
In the first place, it’s important to note that in our K code we’ve defined
pow differently from the apply example: here we’ve opted for an explicit
definition so that the arguments to pow are base, exponent, which is
arguably the more natural ordering.
We have also defined mean using the K translation of recombine: where our J
code in that example took advantage of juxtaposition to create a so-called
3-train, which J defines to behave as recombine, K has no such built-in
support. The only effect of juxtaposition is composition, as we saw in the
example of */#. Instead we’ve used the phrase @\:, which means “apply each
of the functions on the left”, with an array containing sum and length, and
composed %/ to its left, reducing the array containing the results of both
operations with division.
Our final definition, std, is a tacit expression describing the composition
of all the operations performed iteratively in the JavaScript code. In
particular I want to highlight the spelling pow[;2]. This is a so-called
projection, and its semantics are to produce a function which fixes 2 as
the second argument to the function pow.2 K’s primitive and
flexible syntax for projections makes it extremely convenient to describe
partial function application; whereas in our partial example above, we needed
to include flip in order to bind 2 to the second argument of pow: K’s
projection syntax allows partial application in any argument positions.
The resulting function is a juxtaposition of the following functions
1 mean\: produce an array containing x and the mean of x.-/: join those two values with -. Implicit in this step is the map
that’s explicit in the JavaScript; as an array language, K “does the
right thing” when subtracing a single value from an array of values.pow[;2]': square the differences.mean @: take the mean.%: take the square root.In all cases besides the explicit @, the juxtaposition of two verbs is
syntactically treated as function composition, producing a single composed
function.
const eachValueIsUnique = xs => xs === _.uniq(xs)
return eachValueIsUnique([0, 1, 1, 2, 3, 5, 8, 13]) // => false
return eachValueIsUnique([0, 1, 2, 3, 5, 8, 13]) // => true
const eachValueIsUnique = recombine(_.isEqual, identity, _.uniq)
(def each-value-is-unique (recombine deep= identity distinct))
(each-value-is-unique [0 1 2 3 5 8 13])
each_value_is_unique =: -: ~.
each_value_is_unique 0 1 1 2 3 5 8 13
0
each_value_is_unique 0 1 2 3 5 8 13
1
J boasts yet another specialization for tacit programming; whereas we’ve seen
the 3-train create a fork, a 2-train (which we express in terms of
recombine by passing in identity as either g or h) has its own
combinatorial meaning: it creates a hook, such that f g behaves like x => f(x, g(x)).
eachValueIsUnique: ~/ 1 ?:\
eachValueIsUnique 0 1 1 2 3 5 8 13
0
eachValueIsUnique 0 1 2 3 5 8 13
1
Other members of the array family tend to reserve 2-trains for simple function
composition, as we have seen in other K examples. In K, the specialized hook
behaviour can be achieved with n-dos, where 1 g\ x produces an array of
(x;g x), which we can then fold some f over. If f needed to be passed
g(x), x, then we could reverse the array before folding.
Equivalently, we could use eachleft in the same way we did to write mean:
~/ (?:;::) @\: 0 1 1 2 3 5 8 13
0
~/ (?:;::) @\: 0 1 2 3 5 8 13
1
Here, the second of the two functions we apply is ::, the identity function.
const isAnagram = (x, y) => _.sortBy(x) === _.sortBy(y)
return isAnagram("live", "evil")
const isAnagram = under(_.isEqual, _.sortBy)
(def is-anagram (under deep= sort))
(is-anagram @"live" @"evil")
sort =: /:~
is_anagram =: -:&:sort
is_anagram =: -:&:sort
'evil' is_anagram 'live'
1
In J, dyadic under is spelled Appose, &:.
It’s worth noting that with only one argument, under behaves just like
compose: x => _.isEqual(_.sortBy(x)). (Thus, monadic Appose &: is
equivalent to At @:, which we’ve seen above!)
The noteworthy difference, then, is how we want to wield the innermost
function when given two or more arguments. Within A technical detail here: unlike our In practice, this is a distinction without a difference. If we look at
Janet’s native That’s because Janet, like many languages, won’t do implicit partial
application (“currying”) of the We’ve made our job a little more complex here by specifying a
spelling of compose(f, g), all those
arguments are passed to a single application of g, and the result is passed
to f. Within under, g is treated as a single-argument function and each
argument to the composition has g called on it individually.apply combinator, K’s .
doesn’t return a higher-order function; it eagerly applies its left operand
to its right.apply, which behaves similarly, we
see that its eager nature poses a problem for using in a combinatory style:repl:1:> (def bases-and-exponents [[0 1] [1 2] [3 5] [8 13]])
((0 1) (1 2) (3 5) (8 13))
repl:2:> (map (apply math/pow) bases-and-exponents)
error: arity mismatch, expected 2, got 0
in math/pow [src/core/math.c] on line 306
in apply pc=11
in _thunk [repl] (tailcall) on line 2, column 6
apply function. On the other hand, K will
automatically curry any function that hasn’t been given all of its
arguments. Here we see two ways to apply pow to .', both of which
result in a new function rather than an arity mismatch.
↩ pow: */#
pow .'
(*/#).'
.'[pow;]
(*/#).'
pow that goes base, exponent. In fact, this is also a
case that lends some credence to the argument that it’s better to simply spell
out a verb in full than to give that verb a name. The tacit version described
in apply, which takes the exponent first, is not only terser, but in our
example, we precisely want to partially apply the exponent before specifying
the base. Thus we could equivalently spell std:
↩std: % mean @ (*/#)[2;]' -/ 1 mean\