[Edu-sig] Reversing dictionaries, closures, permutations etc.

[Kirby Urner]

How to reverse a dictionary?  The dict class has no .reverse() method, which
makes sense, as keys must be immutable so there's no guarantee the reverse
is even valid (throwing an exception would be the way to go in this case).

Anyway, a straightforward way to do it in code would be:

 >>> phonebook = {'John Smith':'223-2312', 'Beverly Stein':'610-231-2222'}

 >>> def reverse(d):
	   newdict = {}
	   for k in d:
	       newdict[d[k]] = k
	   return newdict

 >>> reverse(phonebook)
 {'223-2312': 'John Smith', '610-231-2222': 'Beverly Stein'}

Note that we no longer have to write 'for k in d.keys()' as 'for k in d' is
now defined to iterate over d's keys.

Here's another way, which I also like:

 >>> def reverse2(d):
         return dict([(val, key) for key, val in d.items()])

 >>> reverse2(phonebook)
 {'223-2312': 'John Smith', '610-231-2222': 'Beverly Stein'}

So what's a "closure"?  The Camel Book (a holy book in Perldom) talks about
closures in terms of manufacturing subroutines with some of the guts
defined, but with other guts to be passed as arguments when the subroutine
is actually used.  The pre-defined guts bind some of the variables, while
leaving others for later definition.

Here's the Perl example (pg. 253):

======

  sub newprint {
     my $x = shift;
     return sub {my $y = shift; print "$x, $y!\n; };
  }

  $h = newprint("Howdy");
  $g = newprint("Greetings");

  # Time passes...

  &$h("world");
  &$g("earthlings");

This prints:

   Howdy, world!
   Greetings, earthlings!

======

Here's the same example in Python, in shell mode:

 >>> def newprint(x):
         def anon(y):
	        print "%s, %s!" % (x,y)
	   return anon

 >>> h = newprint("Howdy")
 >>> g = newprint("Greetings")

 >>> # Time passes...

 >>> h("world")
 Howdy, world!

 >>> g("earthlings")
 Greetings, earthlings!

=======

I use 'anon' for anonymous function, but that's sort of an oxymoron, as
'anon' is the function's name, insofar as functions have a name.  If you ask
for string representations of these references, you get:

  >>> g
  <function anon at 0x0089A030>
  >>> h
  <function anon at 0x00ACEC70>

If you want to make it clear in a different way, that these functions are
anonymous, you could use lambda like this:

 >>> def newprint(x):
	   def anon(y):
		  print "%s, %s!" % (x,y)
	   return lambda y: anon(y)

 >>> h = newprint("Howdy")
 >>> g = newprint("Greetings")
 >>> h
 <function <lambda> at 0x00ACEB70>
 >>> g
 <function <lambda> at 0x00ACEE30>

I guess I have no strong preference for either format.  However, this does
show it's easy for lambda to represent functions of any length, with print
statements included.

* * * *

Tying these two threads together, I might define a "closure" that takes a
specific dictionary as a given.  When invoked as a function, it simply does
a lookup:

 >>> def makefunc(d):
	  def anon(y):
		return d[y]
	  return lambda y: anon(y)


 >>> f1 = makefunc(phonebook)
 >>> f2 = makefunc(reverse2(phonebook))
 
 >>> f1('John Smith')
 '223-2312'
 >>> f2('223-2312')
 'John Smith'

Where I'm going with this is now I might use a "wrapper class" to make f1
and f2 usable with operator overloading.  f1 * f2 would return a new object
representing f1(f2(x)) for any x.  E.g.:

 >>> class P:

	 def __init__(self,f):
		self.f = f

	 def __mul__(self,other):
		return P(self._compose(self.f, other.f))

	 def _compose(klass,f,g):
		return lambda x:  f(g(x))

	 def __call__(self,x):
		return self.f(x)
		
	 _compose = classmethod(_compose)


 >>> p1 = P(f1)
 >>> p2 = P(f2)
 >>> p3 = p1 * p2	

 >>> p1('John Smith')
 '223-2312'
 >>> p2('223-2312')
 'John Smith'

 >> p3('223-2312')
 '223-2312'

If we know in advance that our class P is supposed to work exclusively with
"dictionary functions" of the type returned by makefunc (above), then an
__invert__ method could be defined which automatically creates an "inverse
P" from P, e.g. pinv = ~p1, such that pinv * p1 is the identity permutation
(P is for permutation).

I'll save that for later.

Kirby