Removing hackery from pair of radix functions I like the radix function and found a really neat way to compute its 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:

&gt;&gt;&gt; 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:

&gt;&gt;&gt; radix(85,2)
(0, [1, 0, 1, 0, 1, 0, 1])


How can I remove the hack from this pattern?  Or failing that, how can I rewrite this pair of functions 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.
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 &lt;= 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