Functional Roman Numerals in Python

Just as a quck note, I thought I'd post the cleanest python I could come up with to solve the roman numerals problem I discussed earlier. It tries to use a functional style while actually avoiding recursion. To do so, I wrote an iterative python unfold:

def unfold(f, x):
    res = []                       
    while 1:
        try:
            w, x = f(x)
            res.append(w)
        except TypeError:
            return res

And then the answer becomes:

numerals = [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
    ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
    ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
    ("I", 1)]

def next(x):
    for n in numerals:
        if n[1] <= x: return (n[0], x-n[1])

def romanize(n):
    return "".join(unfold(next, n))

Compare to the haskell I posted before:

romanize = concat . unfoldr next
    where next 0 = Nothing
          next x = Just $ second (x-) $ head $ filter ((<=x) . snd) numerals
          numerals = [("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
                      ("C", 100),  ("XC", 90),  ("L", 50),  ("XL", 40),
                      ("X", 10),   ("IX", 9),   ("V", 5),   ("IV", 4),
                      ("I", 1)]

The "where" idiom allows you to group helper functions and constants underneath the main function, and the unimportance of function order means you can highlight the high-level logic. The haskell code is much shorter and tighter than the python.

Having powerful iterative functions like unfoldr in the standard library is another clear win for Haskell; it took me more lines to define unfold than it did to define both next() and romanize(). (By the by, some googling failed to turn up a previous python implementation of unfold(); I think this code gets a lot uglier without it. I also don't see any obvious way to do it with itertools.)

On the other hand, I find the simplicity of the python next() appealing, with its constructive instead of declarative approach. It's a less generic solution that's intuitively simpler (for me, still an imperative thinker).

You could match the haskell more exactly:

from itertools import ifilter

def second(f, (a, b)): return (a, f(b))

def next(x):
    return second(lambda a: x-a, ifilter(lambda (y, z): z <= x, numerals).next()

but the result is pretty ugly. The inability to compose functions compactly results in a lot of boilerplate, and in having to pick a lot of meaningless variable names that obscure what's going on. We could move the lambdas out of the call and give them names:

def next(x):
    subx = lambda a: x-a
    ltx = lambda (y, z): z <= x

    return second(subx, ifilter(ltx, numerals).next())

And it's a little better, but I think we're now pretty far from idiomatic python.

Conclusion

The python translation of the haskell isn't bad, but I do think it loses something. The unfold() trick works really well, and translates easily into an imperative, pythonic implementation; I'll look for ways to use it in the future. And, finally, I'm pretty jealous of Haskell's function combination abilities.

Updates

In the comments at reddit, nostrademons posts a nicer unfold function:

def unfold(f, x):
    while True:
        w, x = f(x)
        yield w

And Kay Schluehr prefers the iterative solution:

 numerals = (("M", 1000), ("CM", 900), ("D", 500), ("CD", 400),
("C", 100),("XC", 90),("L", 50),("XL", 40), ("X", 10), ("IX", 9), ("V", 5), 
("IV", 4), ("I", 1))

def romanize(n):
    roman = []
    for ltr, num in numerals:
        (k,n) = divmod(n, num)
        roman.append(ltr*k)
    return "".join(roman)

David Pollak contributes a Scala unfold and romanize at his blog.