Integer array indexing (numpy.take) as function composition

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Integer array indexing (numpy.take) as function composition

Jim Pivarski
Hi,

I'm a long-time user of Numpy; I had a question and I didn't know where else to ask. (It's not a bug—otherwise I would have posted it at https://github.com/numpy/numpy/issues).

Has anyone noticed that indexing an array with integer arrays (i.e. numpy.take) is a function composition? For example, suppose you have any two non-negative functions of integers:

def f(x):
    return x**2 - 5*x + 10
def g(y):
    return max(0, 2*y - 10) + 3

and you sample them as arrays, as well as their composition g(f(•)):

F   = numpy.array([f(i) for i in range(10)])     # F is f at 10 elements
G   = numpy.array([g(i) for i in range(100)])    # G is g at enough elements to include max(f)
GoF = numpy.array([g(f(i)) for i in range(10)])  # GoF is g∘f at 10 elements

Indexing G by F (G[F]) returns the same result as the sampled composition (GoF):

print("G\u2218F =", G[F])   # integer indexing
print("g\u2218f =", GoF)    # array of the composed functions
G∘F = [13  5  3  3  5 13 25 41 61 85]
g∘f = [13  5  3  3  5 13 25 41 61 85]

This isn't a proof, but I think it's easy to see that it would be true for any non-negative functions (negative index handling spoils this property). 

It might sound like a purely academic point, but I've noticed that I've been able to optimize and simplify some code by taking advantage of the associative property of function composition, repeatedly applying numpy.take on arrays of integers before applying the fully composed index to my data. As an example of an optimization, if I have to do the same thing to N data arrays, it helps to prepare a single integer index and apply it to the N data arrays instead of modifying all N data arrays in multiple steps. As an example of a simplification, if I need to modify arrays in recursion, it's easier to reason about the recursion if only the terminal case applies an index to data, with the non-terminal steps applying indexes to indexes.

This is such a basic property that I bet it has a name, and there's probably some literature on it, like what you could find if you were interested in monads in Haskell. But I haven't been able to find the right search strings—what would you call this property? Is there a literature on it and its uses?

Thanks!
-- Jim




_______________________________________________
NumPy-Discussion mailing list
[hidden email]
https://mail.python.org/mailman/listinfo/numpy-discussion