Higher-order function

From CS 61A Wiki
Revision as of 16:13, 25 May 2014 by Axis (Talk | contribs)


Jump to: navigation, search

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.

Use

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.

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 map(f, iterable):
    return (f(x) for x in iterable)
def filter(f, iterable):
    return (x for x in iterable if f(x))

iterative improvement:

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

Functions as return values

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

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

Sources