Higher-order algorithms

Question

Most of the well-known algorithms are first-order, in the sense that their input and output are "plain" data. Some are second-order in a trivial way, for example sorting, hashtables or the map and fold functions: they are parameterized by a function, but they don't really do anything interesting with it except invoke it on pieces of other input data.

Some are also second-order but somewhat more interesting:

• Fingertrees parameterized by monoids
• Splitting a fingertree on a monotonous predicate
• Prefix sum algorithms, again usually parameterized by a monoid or a predicate etc.

Finally, some are "truly" higher-order in the sense that is most interesting to me:

• The Y combinator
• Difference lists

Do there exist other nontrivial higher-order algorithms?

In attempt to clarify my question, under "nontrivial higher-order" I mean "using higher-order facilities of the computational formalism in a critical way in the algorithm's interface and/or implementation"

Answer 1

There are a lot of higher order functions on http://math.andrej.com/, for example in the post about double exponentials, the following Haskell type appears (with the type synonyms expanded):

shift :: Bool -> ((Int -> Bool) -> Bool) -> ((Int -> Bool) -> Bool)

You can also have a lot of fun with the post A Haskell Monad for Infinite Search in Finite Time - for example:

newtype S a = S ((a -> Bool) -> a)
bigUnion :: S (S a) -> S a

I guess the type of bigUnion is 4th or 5th order!

Answer 2

there are a bunch of algorithms that are "truly 2nd order" although usually not explicitly described in these terms. Whenever we have sub-linear time algorithms, implicit is some kind of oracle access to the input, i.e. really treating the input as a function.

Examples:

(1) The Ellipsoid algorithms when working with a "separation oracle" (eg http://math.mit.edu/~vempala/18.433/L18.pdf )

(2) Submodular function minimization (eg http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf )

(3) The whole field of property testing is really of this form ( http://www.wisdom.weizmann.ac.il/~oded/test.html )

(4) Combinatorial auctions in the query model (eg http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf )

Answer 3

There is another answer to this question: there aren't any. More specifically, any such (implementable!) higher-order algorithm is mechanically equivalent to a first-order algorithm, using defunctionalization.

Let me be more precise: while there are indeed actual higher-order algorithms, in practice it is always possible to rewrite each instance as a purely first-order program. In other words, there are no saturated higher-order programs -- essentially because the input/output of programs are bit strings. [Yes, those bit strings can represent functions, but that's the point: they represent functions, they are not functions].

The answers already given are excellent, and my answer should not be considered as contradicting them. It should be considered as answering the question from within a slightly larger context (complete programs instead of stand-alone algorithms). And this change of context changes the answer quite radically. The point of my answer is to remind people of this, which is all too easy to forget.

Answer 4

In parser combinator libraries the order of the function is generally fairly high. Check out Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function? by Chris Okasaki. Journal of Functional Programming, 8(2):195-199, March 1998.

Answer 5

Computable analysis characterises real numbers programmatically, since real numbers contain an unbounded amount of information, and so operations on real numbers are higher-order in the questions sense. Typically, real numbers are presented using a topological view on the infinite stream of bits, the Cantor space, lending interest to the wider field of computable topology.

Klaus Weihrach has talked of this as the Type Two Hierarchy of Effectivity of computable topology. For more about this, look at Weihrach & Grubba, 2009, Elementary Computable Topology, and at John Tucker's research page, Computation with Topological Data. I mention Tucker's page in my question, Applications of Cantor Space.

Answer 6

A modulus of continuity functional is a map m which accepts a (continuous) functional F : (nat -> nat) -> nat and outputs a number k such that F f = F g whenever f i = g i for all i < k. There are algorithms for computing the modulus of continuity (not very efficient ones), so that makes it an instance of a 3rd order algorithm.

Answer 7

To complement Noam's answer, there are also several situations where it's important to have the output be (an explicit representation of) a function.

One interesting example is the definition of a list-decodable code. Let $C: \\{0,1\\}^n \rightarrow \\{0,1\\}^m$ be a code. We say that a probabilistic algorithm $A$ $(\alpha,L,\epsilon)$ list-decodes $C$ if on input $n$, $A$ outputs probabilistic machines $M_1,\dots,M_L$ such that:

$\begin{align}\forall w \in \\{0,1\\}^m, Pr_A [&\forall m,~(Ag(C(m),w) \geq \alpha \Rightarrow \\\ &\exists i \in [L],~\forall j \in [n],~Pr_{M_i}[M_i(j) = m_j] \geq 1-\epsilon)] \geq 2/3\end{align}$

Here, $Ag$ denotes the fraction of coordinates that the two strings agree on. In other words, for every received word, the output of $A$ must contain, with probability at least $2/3$, a machine that $\epsilon$-approximates $m$ for every message $m$ whose encoding agrees with at least $\alpha$ fraction of the coordinates of the received word.

Answer 8

In graph algorithms, vertices and edges are usually thought of as being plain data but they can actually be productively generalized so that they are programmatically generated on-demand.

During my PhD (in computational chemistry) I implemented many graph algorithms in higher-order form in order to apply them to the analysis of implicit graphs, mainly because my actual graphs were infinite so I could not afford to store them explicitly! Specifically, I was studying the topology of amorphous materials represented as 3D tilings of unit cells (supercells).

For example, you can write a function to compute the nth-nearest neighbor shell of an origin vertex i like this:

nth i 0 = {i}
nth i 1 = neighbors i
nth i n = diff (diff (fold union empty (map neighbors (nth i (n-1)))) (nth i (n-1))) (nth i (n-2))

where neighbors is a function that returns the set of neighboring vertices to the given vertex.

For example, the 2D square lattice:

neighbors (x, y) = {(x-1, y), (x+1, y), (x, y-1), (x, y+1)}

Other interesting algorithms in this context include Franzblau's shortest path ring statistics.