# Higher-order algorithms

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"

• I asked something similar once. A few answers here: caml.inria.fr/pub/ml-archives/caml-list/2004/09/… Aug 22 '10 at 15:05
• Are you guys talking about algorithms that take algorithms and/or returns algorithms? Sep 1 '10 at 6:15

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!

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 )

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.

• I agree that any higher-order algorithm is equivalent to some first-order algorithm with the same external specification, but this shouldn't preclude us from arguing about their internal properties. There's no difference between representing something and being something.
– jkff
Aug 31 '10 at 11:12
• @jkff: I agree with your first point - we most definitely should discuss these internal properties. I emphatically disagree with the second point: you are somehow claiming that extensions and intensions are 'the same', which is just patently false. [Reminds me of the Matisse painting 'this is not a pipe'] Aug 31 '10 at 12:40
• Ah, yes, "The Treachery of Eta Conversion". (\\() -> "Ceci n'est pas une fonction") () Aug 31 '10 at 19:55
• I'm claiming that if two things are equivalent (by representing each other), you can't deny the existence of one of them :)
– jkff
Sep 1 '10 at 4:29
• @jkff: hard to disagree with that! Sep 1 '10 at 13:00

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.

• This is a great paper, but not quite the thing that I am looking for. Although the combinators are higher-order, they are very simple and independent, and any single of them would hardly count as a non-trivial algorithm/datastructure (however, perhaps combinator parsers themselves would). On the contrary, the Y combinator is a highly nontrivial algorithm to find a fixed point, and difference lists are a clever datastructure built entirely from higher-order functions. (I'm not undermining your answer, just trying to clarify my question)
– jkff
Aug 22 '10 at 20:50

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.

• And this extends quite naturally to computable mathematical objects in general: other computable numbers (not necessarily real), computable elements of infinite groups (rings, algebras, ...), computable points in spaces, etc. In all such cases, the algorithmic theory concerns extracting information from the functional representation (of how to compute the mathematical object), and not from the object itself. Jun 12 '12 at 20:00

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.

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.

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.

• This brings me to a question I had once. If there are programmatic ways of defining graphs this way, is there a way to define a self-referential paradoxical graph ? Jun 12 '12 at 15:32
• @Suresh: it is possible to replicate Russell's paradox in a functional language; evaluating $\{x: x \notin x\} \in \{x: x \notin x\}$ will get stuck in an infinite loop. See, for example, blog.sigfpe.com/2008/01/type-that-should-not-be.html Jul 25 '12 at 22:19
• Sure. But is that a self-referential graph ? Jul 25 '12 at 22:45
• @Suresh: It is a graph defined in a functional language in the sense that there is a type U of vertices and a function U -> U -> Bool of edges. Jul 29 '12 at 18:22