<p>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.  </p>

<p>Examples:</p>

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

<p>(2) Submodular function minimization (eg <a href="http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf">http://people.commerce.ubc.ca/faculty/mccormick/sfmchap8a.pdf</a> )</p>

<p>(3) The whole field of property testing is really of this form ( <a href="http://www.wisdom.weizmann.ac.il/~oded/test.html">http://www.wisdom.weizmann.ac.il/~oded/test.html</a> )</p>

<p>(4) Combinatorial auctions in the query model (eg  <a href="http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf">http://pluto.huji.ac.il/~blumrosen/papers/iter.pdf</a> )</p>

CC BY-SA 2.5
2010-08-23T11:43:05.350Z
2010-08-23T11:43:05.350Z
Noam
<p>There is another answer to this question: there aren't any.  More specifically, any such (implementable!) higher-order algorithm is <strong>mechanically</strong> equivalent to a first-order algorithm, using <a href="http://en.wikipedia.org/wiki/Defunctionalization">defunctionalization</a>.</p>

<p>Let me be more precise: while there are indeed actual higher-order algorithms, in practice it is always possible to rewrite each <em>instance</em> as a purely first-order program.  In other words, there are no <em>saturated</em> 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 <em>represent</em> functions, they are <strong>not</strong> functions].</p>

<p>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.</p>

CC BY-SA 2.5
2010-08-31T11:12:16.303Z
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
CC BY-SA 2.5
2010-08-31T12:40:58.707Z
@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']
Jacques Carette
CC BY-SA 2.5
2010-08-31T19:55:20.860Z
Ah, yes, "The Treachery of Eta Conversion". `(\\() -> "Ceci n'est pas une fonction") ()`
C. A. McCann
CC BY-SA 2.5
2010-09-01T04:29:39.297Z
I'm claiming that if two things are equivalent (by representing each other), you can't deny the existence of one of them :)
jkff
CC BY-SA 2.5
2010-09-01T13:00:53.533Z
@jkff: hard to disagree with that!
Jacques Carette
CC BY-SA 2.5
2010-08-31T00:05:24.210Z
2010-08-31T00:05:24.210Z
Jacques Carette
<p>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.</p>

<p>Klaus Weihrach has talked of this as the <em>Type Two Hierarchy of Effectivity</em> of computable topology.  For more about this, look at Weihrach &amp; Grubba, 2009, <a href="http://www.jucs.org/jucs_15_6/elementary_computable_topology/jucs_15_06_1381_1422_weihrauch.pdf" rel="nofollow noreferrer">Elementary Computable Topology</a>, and at John Tucker's research page, <a href="http://www-compsci.swan.ac.uk/~csjvt/JVTResearch/ComputationTopologicalData.html" rel="nofollow noreferrer">Computation with Topological Data</a>.  I mention Tucker's page in my question, <a href="https://cstheory.stackexchange.com/questions/408/applications-of-cantor-space">Applications of Cantor Space</a>.</p>

CC BY-SA 3.0
2012-06-12T20:00:43.680Z
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.
ex0du5
CC BY-SA 2.5
2010-08-23T09:24:33.597Z
2010-08-23T09:24:33.597Z
2017-04-13T12:32:28.080Z
Charles Stewart
<p>A <em>modulus of continuity</em> functional is a map <code>m</code> which accepts a (continuous) functional <code>F : (nat -&gt; nat) -&gt; nat</code> and outputs a number <code>k</code> such that <code>F f = F g</code> whenever <code>f i = g i</code> for all <code>i &lt; k</code>. There are algorithms for computing the <em>modulus of continuity</em> (not very efficient ones), so that makes it an instance of a 3rd order algorithm.</p>

CC BY-SA 2.5
2010-08-31T05:20:52.580Z
2010-08-31T05:20:52.580Z
Andrej Bauer
<p>In parser combinator libraries the order of the function is generally fairly high. Check out <a href="http://www.eecs.usma.edu/webs/people/okasaki/jfp98.ps"><strong>Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function?</strong></a> by Chris Okasaki. <em>Journal of Functional Programming</em>, 8(2):195-199, March 1998.</p>

CC BY-SA 2.5
2010-08-22T20:50:56.947Z
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
CC BY-SA 2.5
2010-08-22T08:34:31.203Z
2010-08-22T08:34:31.203Z
Dave Clarke
<p>To complement <a href="https://cstheory.stackexchange.com/questions/384/higher-order-algorithms/411#411">Noam's answer</a>, there are also several situations where it's important to have the <em>output</em> be (an explicit representation of) a function.  </p>

<p>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:</p>

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

<p>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. </p>

CC BY-SA 2.5
2010-08-23T21:13:09.650Z
2010-08-24T02:18:52.670Z
2017-04-13T12:32:28.167Z
arnab
<p>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.</p>

<p>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).</p>

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

<pre><code>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))
</code></pre>

<p>where <code>neighbors</code> is a function that returns the set of neighboring vertices to the given vertex.</p>

<p>For example, the 2D square lattice:</p>

<pre><code>neighbors (x, y) = {(x-1, y), (x+1, y), (x, y-1), (x, y+1)}
</code></pre>

<p>Other interesting algorithms in this context include Franzblau's shortest path ring statistics.</p>

CC BY-SA 3.0
2012-06-12T15:32:05.697Z
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 ?
Suresh Venkat
CC BY-SA 3.0
2012-07-25T22:19:03.057Z
@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, http://blog.sigfpe.com/2008/01/type-that-should-not-be.html
sdcvvc
CC BY-SA 3.0
2012-07-25T22:45:42.073Z
Sure. But is that a self-referential *graph* ?
Suresh Venkat
CC BY-SA 3.0
2012-07-29T18:22:25.213Z
@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.
sdcvvc
CC BY-SA 3.0
2012-06-12T12:32:30.690Z
2012-06-12T12:32:30.690Z
J D
<p>There are a lot of higher order functions on <a href="http://math.andrej.com/">http://math.andrej.com/</a>, for example in the post about <a href="http://math.andrej.com/2009/10/12/constructive-gem-double-exponentials/#more-338">double exponentials</a>, the following Haskell type appears (with the type synonyms expanded):</p>

<pre><code>shift :: Bool -&gt; ((Int -&gt; Bool) -&gt; Bool) -&gt; ((Int -&gt; Bool) -&gt; Bool)
</code></pre>

<p>You can also have a lot of fun with the post <a href="http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/#more-122">A Haskell Monad for Infinite Search in Finite Time</a> - for example:</p>

<pre><code>newtype S a = S ((a -&gt; Bool) -&gt; a)
bigUnion :: S (S a) -&gt; S a
</code></pre>

<p>I guess the type of bigUnion is 4th or 5th order!</p>

CC BY-SA 2.5
2010-08-31T15:50:23.207Z
2010-08-31T15:50:23.207Z
yatima2975
<p>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.</p>

<p>Some are also second-order but somewhat more interesting:</p>

<ul>
<li>Fingertrees parameterized by monoids</li>
<li>Splitting a fingertree on a monotonous predicate</li>
<li>Prefix sum algorithms, again usually parameterized by a monoid or a predicate etc.</li>
</ul>

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

<ul>
<li>The Y combinator</li>
<li>Difference lists</li>
</ul>

<p>Do there exist other nontrivial higher-order algorithms?</p>

<p>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"</p>

CC BY-SA 2.5
2010-08-22T15:05:40.237Z
I asked something similar once. A few answers here: http://caml.inria.fr/pub/ml-archives/caml-list/2004/09/483078164a7970c153cae42ab59c1c22.en.html
Radu GRIGore
CC BY-SA 2.5
2010-09-01T06:15:22.997Z
Are you guys talking about algorithms that take algorithms and/or returns algorithms?
Pratik Deoghare
<ds.algorithms><functional-programming><ds.data-structures><pl.programming-languages>
Higher-order algorithms
jkff
# Higher-order algorithms

(Asked by: username_0 on 2010-08-22)

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"

**Tags:** ds.algorithms, functional-programming, ds.data-structures, pl.programming-languages
> **Comments:**
> **username_1**: I asked something similar once. A few answers here: http://caml.inria.fr/pub/ml-archives/caml-list/2004/09/483078164a7970c153cae42ab59c1c22.en.html  
> **username_2**: Are you guys talking about algorithms that take algorithms and/or returns algorithms?  

---

## 8 answers

### Answer by username_14 on 2010-08-31. Score: 14 | Accepted answer

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 by username_3 on 2010-08-23. Score: 22

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 by username_4 on 2010-08-31. Score: 16

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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: @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']  
> **username_5**: Ah, yes, "The Treachery of Eta Conversion". `(\\() -> "Ceci n'est pas une fonction") ()`  
> **username_0**: I'm claiming that if two things are equivalent (by representing each other), you can't deny the existence of one of them :)  
> **username_4**: @jkff: hard to disagree with that!  

---

### Answer by username_6 on 2010-08-23. Score: 13

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](http://www.jucs.org/jucs_15_6/elementary_computable_topology/jucs_15_06_1381_1422_weihrauch.pdf), and at John Tucker's research page, [Computation with Topological Data](http://www-compsci.swan.ac.uk/~csjvt/JVTResearch/ComputationTopologicalData.html). I mention Tucker's page in my question, [Applications of Cantor Space](https://cstheory.stackexchange.com/questions/408/applications-of-cantor-space).

> **Comments:**
> **username_7**: 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.  

---

### Answer by username_8 on 2010-08-31. Score: 13

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 by username_9 on 2010-08-22. Score: 13

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?**](http://www.eecs.usma.edu/webs/people/okasaki/jfp98.ps) by Chris Okasaki. *Journal of Functional Programming*, 8(2):195-199, March 1998.

> **Comments:**
> **username_0**: 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)  

---

### Answer by username_10 on 2010-08-23. Score: 9

To complement [Noam's answer](https://cstheory.stackexchange.com/questions/384/higher-order-algorithms/411#411), 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 by username_11 on 2012-06-12. Score: 5

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.

> **Comments:**
> **username_12**: 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 ?  
> **username_13**: @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, http://blog.sigfpe.com/2008/01/type-that-should-not-be.html  
> **username_12**: Sure. But is that a self-referential *graph* ?  
> **username_13**: @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.  

---

