[Haskell-cafe] Higher-order algorithms

[Eugene Kirpichov]

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 and datastructures?
Is the field of higher-order algorithms indeed as unexplored as it seems?

I mean that not only higher-order facilities are used, but the essence
of the algorithm is some non-trivial higher-order manipulation.

For example, parser combinators are not so interesting: they are a
bunch of relatively orthogonal (by their purpose) combinators, each of
which is by itself quite trivial, plus not-quite-higher-order
backtracking at the core.

For example, for the Y combinator and difference lists are
interesting: the Y combinator builds a function from a function in a
highly non-trivial way; difference lists are a data structure built
entirely from functions and manipulated using higher-order mechanisms.


-- 
Eugene Kirpichov
Senior Software Engineer,
Grid Dynamics http://www.griddynamics.com/