Difference between revisions of "Higher-order function"

From CS 61A Wiki
Jump to: navigation, search
[unchecked revision][checked revision]
(created)
 
(Added Basics sidebar and some cleanup)
 
(14 intermediate revisions by 4 users not shown)
Line 1: Line 1:
A '''higher-order function''' (HOF) is a function that is specialized by another function or that produces another function (i.e. it accepts a function as an argument and/or returns a function). All other functions are ''lower-order functions''.
+
{{Sufficient-class}}
 +
[[File:Higherorderfunctions.JPG|thumb|500px|A simple diagram of a higher-order function. It either takes in a function, returns a function, or does both.]]
 +
{{Basics sidebar}}
 +
A '''higher-order function''' (HOF) is a [[function]] that is specialized by another function or that produces another function (i.e. it accepts a function as an [[Expression#Call expressions|argument]] and/or [[Statement#return|returns]] a function).
  
== Use ==
+
== Background ==
A function is data, so we can treat it like any other object (e.g., a number or a string) and use it as an argument or as a return value.
+
Functions are data, so we can treat them like all other objects (e.g. [[number]]s, [[string]]s, [[boolean]]s, etc.) and use them as arguments or return values.
  
 
HOFs allow us to build [[abstraction]]s by passing actions (functions) around. For example, a recurring pattern is applying a specific function to all the elements of a list. <code>[[map]]</code> abstracts away the details of this behavior, allowing us to apply any function that is passed in.
 
HOFs allow us to build [[abstraction]]s by passing actions (functions) around. For example, a recurring pattern is applying a specific function to all the elements of a list. <code>[[map]]</code> abstracts away the details of this behavior, allowing us to apply any function that is passed in.
Line 8: Line 11:
 
== Examples ==
 
== Examples ==
 
=== Functions as arguments ===
 
=== Functions as arguments ===
 +
* <code>[[map]]</code>, <code>[[filter]]</code>, and <code>[[reduce]]</code>
 +
 +
* [[Iterative improvement]]:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
def map(f, iterable):
+
def iter_solve(guess, done, update):
     return (f(x) for x in iterable)
+
     while not done(guess):
 +
        guess = update(guess)
 +
    return guess
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
=== Functions as return values ===
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
def filter(f, iterable):
+
def make_adder(n):
    return (x for x in iterable if f(x))
+
  def adder(x):
 +
    return x + n
 +
  return adder
 
</syntaxhighlight>
 
</syntaxhighlight>
  
=== Functions as return values ===
 
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
def countdown(n):
 
def countdown(n):
Line 30: Line 40:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
def rational(x, y):
 
def rational(x, y):
     def dispatch(field)
+
     def dispatch(field):
 
         if field == 'numer':
 
         if field == 'numer':
 
             return x
 
             return x
Line 41: Line 51:
  
 
=== Both ===
 
=== Both ===
 +
<syntaxhighlight lang="python">
 +
def make_doubler(f):
 +
  def doubler(*args)
 +
    f(f(*args))
 +
  return doubler
 +
</syntaxhighlight>
 +
 +
* [[Currying]]: Reducing evaluation of a function of multiple arguments to evaluating successive one-argument functions
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 
curry = lambda f: lambda x: lambda y: f(x, y)
 
curry = lambda f: lambda x: lambda y: f(x, y)

Latest revision as of 11:00, 9 July 2014

A simple diagram of a higher-order function. It either takes in a function, returns a function, or does both.

A higher-order function (HOF) is a function that is specialized by another function or that produces another function (i.e. it accepts a function as an argument and/or returns a function).

Background

Functions are data, so we can treat them like all other objects (e.g. numbers, strings, booleans, etc.) and use them as arguments or return values.

HOFs allow us to build abstractions by passing actions (functions) around. For example, a recurring pattern is applying a specific function to all the elements of a list. map abstracts away the details of this behavior, allowing us to apply any function that is passed in.

Examples

Functions as arguments

def iter_solve(guess, done, update):
    while not done(guess):
        guess = update(guess)
    return guess

Functions as return values

def make_adder(n):
  def adder(x):
    return x + n
  return adder
def countdown(n):
    def tick():
        nonlocal n
        n -= 1
        return n
    return tick
def rational(x, y):
    def dispatch(field):
        if field == 'numer':
            return x
        elif field == 'denom':
            return y
        else:
            return 'invalid field'
    return dispatch

Both

def make_doubler(f):
  def doubler(*args)
    f(f(*args))
  return doubler
  • Currying: Reducing evaluation of a function of multiple arguments to evaluating successive one-argument functions
curry = lambda f: lambda x: lambda y: f(x, y)

Sources