One very nice example of a "higher-order" algorithm is the notion of region
(i.e. Point -> Bool) defined in Hudak's paper, that is using functions as
data structures...
http://delivery.acm.org/10.1145/250000/242477/a196-hudak.html?key1=242477&key2=4611513821&coll=GUIDE&dl=GUIDE&CFID=99830619&CFTOKEN=16057768
On Mon, Aug 23, 2010 at 6:03 AM, 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/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe