Adding memoized functions

appengine/findit/libs/math/functions.py

Index: appengine/findit/libs/math/functions.py
diff --git a/appengine/findit/libs/math/functions.py b/appengine/findit/libs/math/functions.py
new file mode 100644
index 0000000000000000000000000000000000000000..18d15651dcd3cfe40e792e29ee58c6934f113627
--- /dev/null
+++ b/appengine/findit/libs/math/functions.py
@@ -0,0 +1,59 @@
+# Copyright 2016 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+

[Sharu Jiang, 2016/12/02 23:47:18]

nit: 2 empty lines.

[wrengr, 2016/12/05 18:50:45]

Done.

+class Function(object):
+  """Base class for mathematical functions.
+
+  The ``callable`` interface is sufficient for when you only ever need to
+  invoke a function. But many times we want to have more information about
+  the function, such as getting its domain or range or knowing whether
+  it's sparse. In addition, we often want to adjust the computational
+  representation of functions (e.g., adding memoization). So this class
+  provides a base class for functions supporting all these sorts of
+  operations in addition to being callable.
+  """
+  def __init__(self, f):
+    self._f = f
+
+  # TODO(wrengr): can we remove the extra indirection somehow?
+  def __call__(self, x):

[Sharu Jiang, 2016/12/02 23:47:18]

So we assume all the Funtions take only one parameter x? How about *args,
**kwargs?

[wrengr, 2016/12/05 18:50:45]

Yes, we assume a single argument for the sake of simplicity. I don't think the
added complexity is worth it to handle the more general case.

+    return self._f(x)
+
+  def map(self, g):
+    """Return a new function that applies ``g`` after ``self``.
+
+    Args:
+      g (callable): the function to post-compose.
+
+    Returns:
+      An object of the same type as ``self`` which computes ``lambda x:
+      g(self(x))``. N.B., although mathematically we have the equivalence:
+      ``SomeFunction(f).map(g) == SomeFunction(lambda x: g(f(x)))``;
+      operationally the left- and right-hand sides may differ. For
+      example, with the ``MemoizedFunction`` class, the left-hand side
+      will memoize the intermediate ``f(x)`` values whereas the right-hand
+      side will not. If that's not desired, be sure to call ``Unmemoize``
+      (or similar type coercions) before mapping.
+    """
+    return self.__class__(lambda x: g(self(x)))
+
+
+class MemoizedFunction(Function):
+  """A function which memoizes its value for all arguments."""
+  def __init__(self, f):
+    super(MemoizedFunction, self).__init__(f)
+    self._memos = {}
+
+  def _ClearMemos(self):
+    """Discard all memoized results of this function."""
+    self._memos = {}
+
+  # TODO(wrengr): can we remove the extra indirection somehow?

[Martin Barbella, 2016/12/02 23:50:21]

I'd be surprised, especially for this case. Probably best to omit these TODOs.

[inferno, 2016/12/05 00:02:10]

Are you planning to work on these TODOs  in next few weeks. I don't want these
to linger in code.
Also, rather than phrasing these as a question to yourself, put like
# TODO(wrengr): Find a way to remove the extra indirection step.

[wrengr, 2016/12/05 18:50:45]

Yes. Though I can file a bug instead if desired

+  def __call__(self, x):
+    try:

[inferno, 2016/12/05 00:02:10]

Docstring

[wrengr, 2016/12/05 18:50:45]

saying what? __call__ is a standard part of Python and has the standard meaning
here.

+      return self._memos[x]
+    except KeyError:
+      fx = self._f(x)
+      self._memos[x] = fx
+      return fx