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 <[email protected]>wrote: > 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
