Ruby and Python

[Alex Martelli]

"Johann Hibschman" <johann at physics.berkeley.edu> wrote in message
news:mt66lnhi43.fsf at astron.berkeley.edu...
    [snip]
> While playing around with Ruby, I came up with the following simple
> class to learn iterators
>
> # set of Die's
> class Dice
>   def initialize(*dice)
>     @dice = dice
>   end
>
>   def dice_combs(dice)
>     if dice.length == 1
>       1.upto(dice[0]) {|n| yield([n])}
>     else
>       1.upto(dice[0]) {|n|
>         dice_combs(dice[1...dice.length]) {|ns|
>           yield([n]+ns)
>         }
>       }
>     end
>   end
>   private :dice_combs
>
>   # run through all permutations
>   def each
>     dice_combs(@dice) {|v| yield(v)}
>   end
>
>   attr :dice
> end
>
> which lets you iterate over all possible combinations via
>
> ds = Dice.new 2, 2, 2
> ds.each {|a, b, c| print a, " ", b, " ", c, "\n"}
> 1 1 1
> 1 1 2
> 1 2 1
> 1 2 2
> 2 1 1
> 2 1 2
> 2 2 1
> 2 2 2
>
> I thought that was pretty neat.  It's not all that far from Stackless
> to good python iterators, although the lack of a corresponding block
> structure in Python makes it hard.

Generators (and perhaps, more generally, coroutines) are indeed a
great thing, and I can't wait for Python to get them!-), but this
specific task easily admits of a differently-structured solution
(thanks to the fact that you may see "the N-th combination" as
a sequence of based-digits, with each digit-position having a
distinct base -- the bases are just the 'self.dice' or @dice...).

E.g.:
class Dice:
    def __init__(self, *dice):
        self.dice = list(dice)
        self.dice.reverse()
    def __getitem__(self, n):
        result = []
        for die in self.dice:
            n,this = divmod(n,die)
            result.append(1+this)
        if n: raise IndexError
        result.reverse()
        return result

(I don't know how to express the for...append loop as a
Python 2 list-comprehension -- funny, maybe I'm just having
a brainstorm -- I usually find list comprehensions neater
and handier than such for...append loops, but here I just
cant' seem to do it...?)

Anyway, even without the list-comprehension this seems to
me to be more concise and transparent than the Ruby version.
The 'iterator' just becomes 'give me the n-th item in the
sequence, please raise IndexError if there IS no n-th item'.

Not *every* generator maps to this Python idiom, but lots
do -- and even many more, with a simple mixin such as:

class IteratorOnly:
    def __init__(self, next, rewind):
        self.__next=next
        self.__rewind=rewind
        self.__nextindex=None
    def __getitem__(self, n):
        if n==0:
            self.__rewind()
            self.__nextindex=0
        if n!=self.__nextindex:
            raise ValueError, "Only for-loop supported"
        self.__nextindex += 1
        return self.__next()

This lets any class follow the iterator-protocol needed
by the for-loop if: it doesn't know how to compute its
"n-th item", but does have methods for "next-item" and
"rewind", with 'next-item' returning IndexError if
there IS no next-item.

If I didn't know about base-digits, for example, I
might implement Dice this way...:

class Dice(IteratorOnly):
    def __init__(self, *dice):
        self.dice = list(dice)
        IteratorOnly.__init__(self, self._next, self._rewind)
    def _rewind(self):
        self.state = [1] * len(self.dice)
        self.state[-1] = 0
    def _next(self):
        for i in range(len(self.dice)):
            j = -i-1
            self.state[j] += 1
            if self.state[j] <= self.dice[j]:
                return self.state
            else: self.state[j] = 1
        else: raise IndexError

Not quite as concise and transparent as the special
solution above, but still pretty workable, and based
on the simple and often-applicable paradigm of "get
next state if any given current one / reset state at
sequence-start" (the mixin-class is written once,
then forgotten, of course...:-).

Sometimes you get intrinsically-recursive problems
for which no such linearized iteration paradigm is
a good, simple fit (e.g., 'fringe of a tree' -- you
need to either use recursion or simulate it with
your own stack for that...) -- and these are the
cases where one really hungers for generators.  But
in my experience they don't tend to be all that
many as one might think.


So, anyway, however you implement class Dice (say
in module dice), the client-code is always:

>>> ds = dice.Dice(2,2,2)
>>> for a,b,c in ds:
 print a,b,c

and, I may be biased, of course, but it does seem to
me to be quite simpler and clearer than the given
Ruby equivalent, i.e.:

ds = Dice.new 2, 2, 2
ds.each {|a, b, c| print a, " ", b, " ", c, "\n"}


If/when Python DOES finally get generators, I hope
they'll be made accessible through the simple "for-
loop protocol" (perhaps needing a simple mixin for
wrapping them to the suitable form... that would
not be a big problem!).


And, one more thing... suppose than, rather than
REALLY needing to enumerate all items of an object,
what we really want to know is whether this sequence
contains a certain 'target', e.g.:

    for combo in ds:
        if combo==mycombo:
            print "yes!"
            break
    else:
        print "no..."

(Presumably there is some way to code the equivalent
in Ruby, passing to ds.each a block which does a test
and breaks the iteration if the test succeeds...?)

Well, Python *wraps this very common idiom for us*!
Since ds satisfies the 'for-loop protocol', then
the existence of a given 'target' in the sequence
of its sub-items can ALSO be tested by coding:

    if mycombo in ds: print "yes!"
    else: print "no..."

which internally, by default, expands to the same
thing as the above-exemplified loop.  *Further*,
if we decide this is a frequent operation and want
to optimize it, *with no change in client-code*,
we just need to add to class Dice one method...:

    def __contains__(self, item):
        if type(item) != type([]): return 0
        if len(item)!=len(self.dice): return 0
        for i in range(len(item)):
            if item[i]<=0 or item[i]>self.dice[-i-1]:
                return 0
        return 1

in the former version, where self.dice is kept
in reversed form for convenience in iteration;
in the latter version, e.g., the niftier:

    def __contains__(self, item):
        if type(item) != type([]): return 0
        if len(item)!=len(self.dice): return 0
        for this, die in zip(item,self.dice):
            if not 0<this<=die: return 0
        return 1

thus turning the containment-test (again, with
NO change to client-code!) from O(N!) down to
O(N)... dunno 'bout YOU, but good old me IS
impressed by this kind of little speedups!-)


Alex