How to make this python function and its inverse more beautiful and symmetric?

Question

I like the radix function and found a really neat way to compute it's inverse in python with a lambda and reduce (so I really feel like I'm learning my cool functional programming stuff) :

def unradix(source,radix):
        # such beauty
        return reduce(lambda (x,y),s: (x*radix,y+s*x), source, (1,0))

Where :

>>> unradix([1,0,1,0,1,0,1],2)
(128,85)

But its dizygotic twin is unable to use the same pattern without an ugly hack :

def radix(source,radix):
        import math
        hack = 1+int(math.floor(math.log(source)/math.log(radix)))
        # ^^^^ ... _nearly_ , such beauty
        return reduce(lambda (x,y),s: (x/radix,y+[x%radix]), xrange(hack), (source,[]))

Where :

>>> radix(85,2)
(0, [1, 0, 1, 0, 1, 0, 1])

My question is emphatically how can I remove the hack from this pattern? or failing that, how can I rewrite this pair of function and inverse so they use the same pattern, and only differ in "mirror-symmetries" as much as possibly.

By mirror symmetry I mean something like the way increment and decrement are mirror images, or like the juxtaposition of x*radix versus x/radix in the same code location as above.

Answer 1

The reverse operation to folding is unfolding. To be honest, I'm not very fluent in python and I couldn't find if python has an unfolding function. (In Haskell we have foldr and its complement unfoldr.)

Nevertheless, we can easily construct one:

"""
f accepts a value and returns None or a pair.
The first element of the pair is the next seed,
the second element is the value to yield.
"""
def unfold(f, r):
    while True:
        t = f(r);
        if t:
            yield t[1];
            r = t[0];
        else: 
            break;

It iterates a given function on a seed until it returns None, yielding intermediate results. It's dual to reduce, which takes a function and an iterable and produces a value. On the other hand, unfold takes a value and a generating function, and produces a generator. For example, to create a list of numbers from 0 to 10 we could write:

print list(unfold(lambda n: (n+1, n) if n <= 10 else None, 0));

(we call list to convert a generator into a list).

Now we can implement radix quite nicely:

def radix(source, radix):
    return unfold(lambda n: divmod(n, radix) if n != 0 else None, source);

print list(radix(12, 2));

prints [0, 0, 1, 1].

---

Edit: Folding (reduce) captures the pattern of consuming lists. Any function that sequentially consumes a list can be eventually written using reduce. The first argument to reduce represents the core computation and the third argument, the accumulator, the state of the loop. Similarly, unfolding (my unfold) represents the pattern of producing lists. Again, any function that sequentially produces a list can be eventually rewritten using unfold.

Note that there are functions that can be expressed using either of them, as we can look at them as functions that produce or consume lists. For example, we can implement map (disregarding any efficiency issues) as

def map1(f, xs):
    return reduce(lambda rs, x: rs + [f(x)], xs, [])

def map2(f, xs):
    return unfold(lambda xs: (xs[1:], f(xs[0])) if xs else None, xs)

---

The duality of reduce and unfold is nicely manifested in a technique called deforestation. If you know that you create a list using unfold only to consume it immediately with reduce, you can combine these two operations into a single, higher-order function that doesn't build the intermediate list:

def deforest(foldf, init, unfoldf, seed):
    while True:
        t = unfoldf(seed);
        if t:
            init = foldf(t[1], init);
            seed = t[0];
        else:
            return init;

For example, if we wanted to compute the sum of digits of 127 in base 2, we could call

print deforest(lambda x,y: x + y, 0,  # folding part
               lambda n: divmod(n, 2) if n != 0 else None, # unfolding
               127); # the seed

Answer 2

I modified the answer by Petr Pudlák slightly, changing the unfold function to yield the last seed before exhaustion as it ends.

def unfold(f, r):
    while True:
        t = f(r)
        if t:
            yield t[1]
            r = t[0]
        else: 
            yield r  #<< added
            break

This enables some kind of accumulated value to be kept, like in the original unradix we can keep the highest power of the base greater than the source number.

Using the modified unfold function we can keep it here, too. To do so I modified the radix like so:

def radix(source,radix):
        return unfold(lambda (n,maxpow): ((n/radix, maxpow*radix), n%radix) if n !=0 else None, (source,1))

I prefer my version better, since it keeps the first seed tuple (source,1) which is similar to the one for unradix , (1,0) each containing the appropriate identity for multiplicative or additive accumulation. And it outputs the radix as well as the highest power.

>>> list(totesweird.radix(121,3))
[1, 1, 1, 1, 1, (0, 243)]