Talk:Higher-order function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
edit·history·watch·refresh Stock post message.svg To-do list for Higher-order function:
  • Make difference between anonymous functions, higher-order functions and closures superduper clear. An anonymous function is what you often pass as an argument to a higher-order function. Well actually, a closure is what you often pass to a higher-order functions. A closure relates to an (anonymous) function as an object to an (anonymous) class.

First-order function[edit]

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)


"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 ?[edit] —The preceding unsigned comment was added by (talk) 09:20, 15 May 2007 (UTC).

Curried functions higher order[edit]

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)

Higher order functions must return a function[edit]

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:

case f of:
 1:return f1(args);
 2:return f2(args);
 3:return f3(args);
map_array(pass_by_val: array,pass_by_val: 1, pass_by_ref: out_array)
  for i:=1 to lenght(array)
  next i;

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 (talk) 05:51, 11 March 2011 (UTC)

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

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

Link Broken[edit]

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 (talk) 11:13, 6 October 2013 (UTC)

Language comparison??[edit]

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. (talk) 00:59, 26 March 2014 (UTC)