One very nice example of a &quot;higher-order&quot; algorithm is the notion of region (i.e. Point -&gt; Bool) defined in Hudak&#39;s paper, that is using functions as data structures... <div><br></div><div><a href="http://delivery.acm.org/10.1145/250000/242477/a196-hudak.html?key1=242477&amp;key2=4611513821&amp;coll=GUIDE&amp;dl=GUIDE&amp;CFID=99830619&amp;CFTOKEN=16057768">http://delivery.acm.org/10.1145/250000/242477/a196-hudak.html?key1=242477&amp;key2=4611513821&amp;coll=GUIDE&amp;dl=GUIDE&amp;CFID=99830619&amp;CFTOKEN=16057768</a><br>
<div><br><div class="gmail_quote">On Mon, Aug 23, 2010 at 6:03 AM, Eugene Kirpichov <span dir="ltr">&lt;<a href="mailto:ekirpichov@gmail.com">ekirpichov@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Most of the well-known algorithms are first-order, in the sense that<br>
their input and output are &quot;plain&quot; data.<br>
Some are second-order in a trivial way, for example sorting,<br>
hashtables or the map and fold functions: they are parameterized by a<br>
function, but they don&#39;t really do anything interesting with it except<br>
invoke it on pieces of other input data.<br>
<br>
Some are also second-order but somewhat more interesting:<br>
* Fingertrees parameterized by monoids<br>
* Splitting a fingertree on a monotonous predicate<br>
* Prefix sum algorithms, again usually parameterized by a monoid or a<br>
predicate etc.<br>
<br>
Finally, some are &quot;truly&quot; higher-order in the sense that is most<br>
interesting to me:<br>
* The Y combinator<br>
* Difference lists<br>
<br>
Do there exist other nontrivial higher-order algorithms and datastructures?<br>
Is the field of higher-order algorithms indeed as unexplored as it seems?<br>
<br>
I mean that not only higher-order facilities are used, but the essence<br>
of the algorithm is some non-trivial higher-order manipulation.<br>
<br>
For example, parser combinators are not so interesting: they are a<br>
bunch of relatively orthogonal (by their purpose) combinators, each of<br>
which is by itself quite trivial, plus not-quite-higher-order<br>
backtracking at the core.<br>
<br>
For example, for the Y combinator and difference lists are<br>
interesting: the Y combinator builds a function from a function in a<br>
highly non-trivial way; difference lists are a data structure built<br>
entirely from functions and manipulated using higher-order mechanisms.<br>
<font color="#888888"><br>
<br>
--<br>
Eugene Kirpichov<br>
Senior Software Engineer,<br>
Grid Dynamics <a href="http://www.griddynamics.com/" target="_blank">http://www.griddynamics.com/</a><br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</font></blockquote></div><br></div></div>