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 monoidsSplitting a fingertree on a monotonous predicatePrefix 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 combinatorDifference listsDo there exist other nontrivial higher-order algorithms?In attempt to clarify my question, under nontrivial higher-order I mean using higher-order facilities of the computational formalism in a critical way in the algorithm's interface and/or implementation
Higher-order algorithms
ds.algorithms;functional programming;ds.data structures;pl.programming languages
There are a lot of higher order functions on http://math.andrej.com/, for example in the post about double exponentials, the following Haskell type appears (with the type synonyms expanded):shift :: Bool -> ((Int -> Bool) -> Bool) -> ((Int -> Bool) -> Bool)You can also have a lot of fun with the post A Haskell Monad for Infinite Search in Finite Time - for example:newtype S a = S ((a -> Bool) -> a)bigUnion :: S (S a) -> S aI guess the type of bigUnion is 4th or 5th order!