Talk:Higher-order function

First-order function

Functions that are not higher-functions are (I believe) first-order functions. It would be nice if someone could find a citation of this (I couldn't) any integrate it into the article. Oligomous (talk) 22:24, 27 December 2009 (UTC)

Would be nice if this definition were expanded. I landed on this page looking for information on first-order functions (Map Reduce), but saying that they are those which are not higher-functions isn't particularly descriptive without the set of possibilites being known or stated. If higher-functions take a function as parameter and return a function, then "everything else" are those functions that don't take functions as parameters and don't return a function; that can range from taking no parameters to taking any parameters which are not functions, and the same for the return type. I'm none the wiser. — Preceding unsigned comment added by 130.149.246.89 (talk) 10:37, 14 July 2016 (UTC)

Power

"Macros can also be used to achieve some of the effects of higher order functions. These do not have the efficiency problems of run-time evaluation, but are more limited in what they can achieve. These also tend to not be strongly typed."

I thought macros (as in, Lisp macros, not simple textual search-and-replace) could do everything first-order functions could do? Am I missing something? --Maru (talk) Contribs 20:51, 29 November 2005 (UTC)

It depends exactly what you mean by "macro". In general, macros don't do capture-avoiding substitution, and macros can almost never be recursive -- higher-order functions do both. --bmills 16:37, 30 November 2005 (UTC)

Well, what about hygienic macros? I had understood they allowed arbitary transformations, which to my mind implies allowing recursion. --Maru (talk) Contribs 00:22, 1 December 2005 (UTC)

Proper hygienic macros do fix the problem of variable capture. The exact power of macros depends on the macro system, but if they can do "arbitrary transformations" that seems to imply turing-completeness, which in turn means that macro-expansion may not terminate -- that is, programs may be infinite. Usually we want to restrict ourselves to only finite programs, which puts some serious limits on what we can actually do with macros. Moreover, if the number of times a function recurses isn't known until run-time, there's no way we could write a macro that captures it. (The problem is mostly one of phase distinction or phase separation.) --bmills 23:28, 4 December 2005 (UTC)

This needs to be updated. As an example, Higher-ordered functions can be implemented in C# 2.0 as anonymous delegates (and they are statically typed). Java, Ruby, and a host of other languages also support these. Google for "closures."

other high-order functions ?

http://en.wikipedia.org/wiki/Talk:Fold_%28higher-order_function%29#other_high-order_functions_.3F —The preceding unsigned comment was added by 212.176.32.19 (talk) 09:20, 15 May 2007 (UTC).

Curried functions higher order

The article reiterates the common confusion that a function which returns a function is higher order. According to this (+) : Int -> (Int -> Int) is higher order? The type is isomorphic to Int x Int -> Int which is not higher order. Moreover the standard definition of order of a function is maximum of order of domain+1 and order of codomain. According to this the type of (+) is first order as one would expect and not higher order. --Thorsten (talk) 12:54, 2 March 2010 (UTC)

are they really isomorphic? Int -> (Int -> Int) demands its arguments one at a time; (Int,Int) -> Int demands both its arguments at the same time, it seems. Note the forbidden t-word. I guess notions of functions and notions of computations get conflated here ... and BTW or course (+) is higher-order in e.g. Haskell, where it has the first type. Its domain is numbers, codomain - incrementing functions. Currying (i.e. partial specification) in such languages is just partial application. WillNess (talk) 09:58, 1 July 2011 (UTC)

The initial comment indicates a common confusion that derives from the curried style of function definition and the behaviour of functions and operators such as (+) that are strict in all their arguments. If an operator such as (+) is strict in all its arguments then no useful work can be done until the values of both arguments are available and so why would we not give it the uncurried and first-order type (Int, Int) -> Int? This would match with the emotional expectation that addition is so basic, so straightforward, that it should not be considered "higher order". By contrast, the curried definition of (+) has type Int -> Int -> Int which is a completely different type to (Int, Int) -> Int. As noted by WillNess above, the two types are not isomorphic. The curried version is neither simple nor straightforward; it is higher-order, taking one argument of type Int and returning an anonymous function (of first-order type (Int -> Int)). Why would we introduce such complexity for such a basic operation? Because currying permits partial application; for example I can give a name to the anonymous intermediary function by defining inc = (+ 1) — Preceding unsigned comment added by 10-clarity-01 (talk • contribs) 14:06, 8 July 2016 (UTC)

There's no confusion. In some languages (+) is indeed higher order because you'll be able to do :t (+2) -- Num a => a -> a. In others it is not. Where it returns a function as is the case in Haskell, it is a higher-order function. Per this, I am taking the dispute template off. Bluedeck 21:39, 19 April 2018 (UTC)

Higher order functions must return a function

The main point about higher order functions is that they return a function. It does not matter if it is curried or uncurried.

A function just accepting one or more functions is not high order.

Passing pointers to functions is more or less similar to pass any id to select a function.

see for example this pseudo-code:

pseudo_high_order_funs(f,args)
case f of:
 1:return f1(args);
 2:return f2(args);
 3:return f3(args);
esac

map_array(pass_by_val: array,pass_by_val: 1, pass_by_ref: out_array)
  for i:=1 to lenght(array)
    out_array[i]:=pseudo_high_order_funs(1,array[1]);
  next i;
end;

Languages implemented as interpreters of text code can simulate high order functions.

The trick is to write a function on a file at execution time, then call it. because it is interpreted from text code, it works. I saw this trick in an old hp basic manual. about 1976.

In principle, this trick may be implemented in compiled languages, by writing the source code, compiling it at run time, then dynamic linking it. I never did this trick, but this should work.

If anyone of you are skilled enough to write some examples in this sense in some unix (linux) and windows (I am some outdated in this issues), those tricks may be included in the article. —Preceding unsigned comment added by 189.217.253.136 (talk) 05:51, 11 March 2011 (UTC)

I'm confused - The article defines a higher order function as one that returns a function, but then states a prime example of such a thing is map(), which in most cases doesn't return a function (just a list). Is this because map could in theory return a list of functions, or because the criteria to return a function is wrong? — Preceding unsigned comment added by Hfrancis (talk • contribs) 12:54, 19 May 2016 (UTC)

A Higher Order Function either takes a function as its argument or returns a function as its result, or both. This can be done in different ways in different languages, but the terminology remains the same. You should inspect the type expression for the function: if it has more than one function arrow then this indicates that the function is Higher Order (either taking a function argument, (a -> b) -> c, or returning a function as its result, a -> (b -> c), and noting that a -> b -> c must be disambiguated by reference to the type associativity rule for the language which most often is right-associative giving a -> (b -> c)). — Preceding unsigned comment added by 10-clarity-01 (talk • contribs) 19:55, 25 July 2016 (UTC)

Untyped lambda calculus and higher order functions

Does the adjective "Higher Order" only apply to typed functions? or does it equally apply to untyped functions? does Barendregt have anything to say on this?

In the untyped lambda calculus there are no types. There are functions (lambda abstractions) but they are not typed. The syntax permits any expression to be applied to any other expression, and if the expression on the left (being applied) is a lambda abstraction then it will match the left hand side of the beta reduction rule, thereby triggering a beta reduction. The type of the argument is never checked because there is no type system. Similarly the type of the result is never checked because there is no type system. It therefore may appear strange to read that "in the untyped lambda calculus all functions are Higher Order". In the untyped lambda calculus (without constants) a lambda abstraction can be thought of as an untyped function of one argument, and such a function both takes and returns either a variable name or a function or the result of applying a function to an argument. In essence, when variable names are replaced by their bound values, and when applications are replaced by their results, everything is represented as a function (a lambda abstraction) and therefore in this sense every function takes a function as an argument and returns a function as its result. — Preceding unsigned comment added by 10-clarity-01 (talk • contribs) 20:22, 25 July 2016 (UTC)

Example sections seems to be all wrong. Might need review from someone who really knows FP

Example sections seems to be all wrong. Might need review from someone who really knows FP. — Preceding unsigned comment added by 117.207.1.89 (talk) 10:35, 1 June 2012 (UTC)

I have to agree. I'm looking at the definition of, 'takes a function and returns a function', and the examples don't do that (at least the ones I looked at). They take a function as parameter, but then return a value after applying the parameterized function a couple of times. This contradicts the definition. On my understanding the examples are wrong and the definition correct. If these examples are valid then the definition provided is lacking. 76.103.48.252 (talk) 15:22, 8 September 2015 (UTC)

I removed some of the "wrong" examples. There is little need to give examples in so many languages in any case. —Ruud 19:44, 8 September 2015 (UTC)

Link Broken

The first of the external links (Higher-order functions and variational calculus) is no longer valid. Maybe someone can replace it with another equivalent source? — Preceding unsigned comment added by 77.21.86.100 (talk) 11:13, 6 October 2013 (UTC)

Language comparison??

Despite the warning that the Examples section is not intended to compare and contrast languages, there are three examples that are equivalents. Perhaps either the warning could be removed or the two superfluous examples. Alternately, they could reasonably be converted to examples of other higher-order functions.

24.102.110.195 (talk) 00:59, 26 March 2014 (UTC)

Is "higher-order function" synonymous with "functor"?

On Wikipedia, the Functor article refers to a concept in category theory, but the higher-order function article also mentions "functor" as a synonym for "higher-order function". Are these concepts really the same? Jarble (talk) 17:56, 10 November 2014 (UTC)

In general no, because the word functor is used in different ways in different fields. See Functor (disambiguation). Some of those uses have little to do with higher order functions. Even in the computer science context, this isn't true. In Haskell, for instance, a Functor is a typeclass, whereas a higher order function is simply a function that consumes or produces functions. --Mark viking (talk) 21:42, 10 November 2014 (UTC)

Haskel example

The haskel example does not implement the same functionality as the other code examples. F(7) = 1 vs f(7) = 13. 91.158.251.58 (talk) 01:59, 26 September 2016 (UTC)

Was Perl intentionally left out for some reason?

Perl clearly supports (and has always supported) Higher Order Functions and Currying. Mark Jason Dominus demonstrated this and more about Perl in the Book "HIGHER-ORDER PERL, Transforming Programs with Programs" published in 2005 ISBN: 1-55860-701-3 — Preceding unsigned comment added by Aimass (talk • contribs) 20:04, 4 May 2020 (UTC)