Sunday, October 11, 2009

Extend functools.partial to nested function calls?

I am reading the 1977 ACM Turing Award Lecture "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs" by John Backus.

In section 5.1 he is contrasting a von Neumann program for inner product, which he gives as:
c := 0
for i := 1 step 1 until n do
c := c + c[i] x b[i]
The above converts quit nicely to the python equivalent:
>>> v1, v2 = [1,2,3], [6,5,4]
>>> def ip_von_neumann(a, b):
c = 0
for i in range(3):
c = c + a[i] * b[i]
return c

>>> ip_von_neumann(v1, v2)
28
Backus then goes on to contrast the von Neumann style with his functional program:
Def Innerproduct ≡ (Insert +)o(ApplyToAll x)oTranspose
Which I converted to the following functional style Python:
>>> from operator import add, mul
>>> from functools import reduce as insert
>>>
>>> def ip_functional(*x):
return insert(add, map(mul, *x))

>>> ip_functional(v1, v2)
28

Well, the Python works, but it still has this name x that I would like to eliminate.

I think I can go part of the way by using functools.partial. For example, for the single function call of map(mul, *x) I can do:
>>> from functools import partial
>>> p1 = partial(map, mul)
>>> assert p1(v1, v2) == map(mul, *(v1, v2))
>>> map(mul, *(v1, v2))
[6, 10, 12]
>>>
But I don't know how to go that extra step and remove x from the definition fully, ie end up with just some assignment like:
ip_purefunctional = {A pure function of functions without any argument placeholders}


All help would be appreciated, Thanks.

5 comments:

  1. The answer is mostly in the expression of the original solution you're trying to duplicate in Python. The compose operator is used twice here:

    Def Innerproduct ≡ (Insert +)o(ApplyToAll x)oTranspose

    So, define a compose function in Python and then use it to define the inner product function:

    >>> from operator import mul
    >>> from functools import partial
    >>> def compose(f, g):
    ... return lambda *args, **kwargs: f(g(*args, **kwargs))
    ...
    >>> ip = compose(sum, partial(map, mul))
    >>> ip([1, 2, 3], [6, 5, 4])
    28

    I used sum instead of reduce/add, but it's otherwise what you're looking for, I think.

    Also, unrelated to functional programming, your blog seems to have some unpleasant javascript injected into it which (at least in my case) popped up an audio-playing advertisement when I clicked on this text area to comment. :(

    ReplyDelete
  2. It's a bit easier to see what's going on if you do it in haskell, I think.

    In haskell, this is called pointfree style, and is made quite easy, especially by simpler function composition. These two definitions of "w" are equivalent:

    Prelude> let w x = map (+ 1) x
    Prelude> w [1,2,3]
    [2,3,4]
    Prelude> let w = map (+ 1)
    Prelude> w [1,2,3]
    [2,3,4]

    And the "." operator is just like Jean-Paul's compose function, so "x" and "x2" are equivalent in this code:

    Prelude> let x y = sum (map (+1) y)
    Prelude> let x2 = sum . (map (+1))

    Similarly, these two versions of "inner_product" are equivalent:

    Prelude> let ip = (foldr (+) 0 .) . zipWith (*)
    Prelude> let ip2 x y = foldr (+) 0 (zipWith (*) x y)
    Prelude> ip [1,2,3] [6,5,4]
    28
    Prelude> ip2 [1,2,3] [6,5,4]
    28

    An especially neat feature of haskell is that it's possible to automatically convert any function to or from pointfree style.

    ReplyDelete
  3. Thanks guys for the heads-up on compose. That is just what I am after.

    I wonder why there is no compose in functools?

    - Paddy.

    P.S. Anyone else have the popup problem mentioned by Jean-Paul?

    ReplyDelete
  4. I got the popup the first time I started to write a comment, but when I came back after editing it for a bit, it was gone. Weird, short-lived blogspot bug perhaps?

    Also, re compose function in functools: http://bugs.python.org/issue1506122

    It's still open from 2006, appears that nobody's done anything about it.

    ReplyDelete
  5. ooh but then it's been rejected apparently:

    http://mail.python.org/pipermail/python-dev/2009-August/091186.html

    which references this rejected patch

    http://bugs.python.org/issue1660179

    Basically, it got rejected for being out of line with python style generally. That seems silly to me, and that it would be simple and harmless to include in functools, but what are you going to do.

    ReplyDelete