[Haskell-cafe] Higher-order algorithms

[Vinod Grover]

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 <ekirpichov at gmail.com>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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100830/e2cb0de9/attachment.html