Search code examples
language-agnosticprogramming-languagesautomatic-differentiation

Derivative of a Higher-Order Function


This is in the context of Automatic Differentiation - what would such a system do with a function like map, or filter - or even one of the SKI Combinators?

Example: I have the following function:

def func(x):
    return sum(map(lambda a: a**x, range(20)))

What would its derivative be? What will an AD system yield as a result? (This function is well-defined on real-number inputs).


Solution

  • Higher-order functions are discrete. They don't have the Cartesian quality of having arguments that have well-defined mappings to points in some n-dimensional space.

    However, with your clarification on the answer, there are several things that can be said. Symbolically differentiating some higher-order functions would be possible, but only for certain calling patterns that resolve to well-known functions.

    Probably, numerical differentiation would be more fruitful, as it can estimate the derivative by repeatedly evaluating the given function.

    Also, functions that are totally general - and your example is heading that way, with use of relatively arbitrary functions - eventually you'll hit Turing completeness, which will mean that no amount of cleverness on the part of a symbolic differentiator will be able to automatically differentiate the function.