[Haskell-cafe] Higher-order algorithms

[Dan Piponi]

Automatic differentiation can also bee seen this way. In a sense it
transforms a function to compute f(x) into a function to compute
f'(x), where f' is the derivative of f.
--
Dan

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
>