Difference between revisions of "Higher-order function"

From CS 61A Wiki
Jump to: navigation, search
[checked revision][checked revision]
m
(copyedit; add)
Line 1: Line 1:
 
{{Sufficient-class}}
 
{{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.]]
+
[[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.]]
 
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 [[return value|returns]] a function).
 
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 [[return value|returns]] a function).
  
Line 7: Line 7:
  
 
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.
 
 
  
 
== Examples ==
 
== Examples ==
 
=== Functions as arguments ===
 
=== Functions as arguments ===
<syntaxhighlight lang="python">
+
<code>[[map]]</code>, <code>[[filter]]</code>, and <code>[[reduce]]</code>
def map(f, iterable):
+
    return (f(x) for x in iterable)
+
</syntaxhighlight>
+
 
+
<syntaxhighlight lang="python">
+
def filter(f, iterable):
+
    return (x for x in iterable if f(x))
+
</syntaxhighlight>
+
  
 
[[iterative improvement]]:
 
[[iterative improvement]]:
Line 66: Line 56:
 
   return doubler
 
   return doubler
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 
[[currying]]:
 
[[currying]]:
 
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">

Revision as of 14:38, 4 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

map, filter, and reduce

iterative improvement:

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:

curry = lambda f: lambda x: lambda y: f(x, y)

Sources