Removing hackery from pair of radix functions

Question

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:

>>> 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])

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.

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

• Cris Stringfellow: A beautiful and symmetric radix! A great explanation as well. Thanks for teach me, and "us", something!
• Cris Stringfellow: (in spirit) +1 for deforest, that soo cool.
• Cris Stringfellow: @PetrPudlák so I understand, we are using our function (that would have been in unfold) on init, one time, then we are using our fold function on the yield value of that 'unfold' function, and accumulating that into init. And we are 're'-unfolding with the seed value. So we interleave folding into init, and unfolding out of seed. If we were to capture the sequences of seed and init, they would reproduce the lists being produced and consumed at each step of the deforest while loop. Does that sound right?
• Petr: @CrisStringfellow Yes, it's just like you say.
• Cris Stringfellow: @PetrPudlák good to know, thanks. Now I have learnt something else. :)

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)]