My Name Rhymes

Functional Roman Numerals in Python

2008-01-12T17:52:00Z

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.

Beautiful Code

2008-01-12T03:32:00Z

This bit of code for converting numbers into their Roman numeral equivalents was posted by geezusfreeek on reddit, and I found it so alarmingly pretty that I'm going to spend some time to break it down. This exercise is largely for my own edification, but perhaps somebody else will learn a bit along the way. Here's the code:

import List
import Control.Arrow

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

Starting from the inside out is usually the easiest method of understanding blocks like this, so we'll look first at the "numerals" list. It is, simply, a list of tuples matching Roman numerals to their value. Importantly, it's ordered from largest to smallest; we'll see why shortly.

The meat of this snippet comes in the "next" function:

next 0 = Nothing
next x = Just $ second (x-) $ head $ filter ((<=x) . snd) numerals

This function is going to return either Nothing (in the base case) or Just a tuple of type (String, Integer), where the string is the largest roman numeral that's smaller than x and the int is the difference between x and the value of that roman numeral.

The first thing we do is filter out the numerals larger than x; we can run some quick tests at the interactive console to see how this works:

Prelude> let numerals = [("M", 1000), ("CM", 900), ("D", 500)]
Prelude> filter ((<=900) . snd) numerals
[("CM",900),("D",500)]

We use head to grab the largest numeral we can squeeze into the current value:

Prelude> head $ filter ((<=900) . snd) numerals 
("CM",900)

Then we subtract the value of the roman numeral from the current value of x, in order to return the remainder to be operated on next:

Prelude> :m Control.Arrow
Prelude Control.Arrow> second (900-) $ head $ filter ((<=900) . snd) numerals
("CM",0)
Prelude Control.Arrow> second (915-) $ head $ filter ((<=915) . snd) numerals
("CM",15)

And, finally, we wrap it up in a Maybe monad, so that the main function can handle the base case transparently:

Prelude Control.Arrow> Just $ second (915-)  $ head $ 
    filter ((<=915) .  snd) numerals
Just ("CM",15)

And now we're getting pretty close! What we have is a function that returns either Nothing or a tuple containing a letter to add to our roman numeral and the next value to operate on. All we have left is the code to drive the operation:

romanize = concat . unfoldr next

The use of unfoldr helps explain why we've wrapped next up in Maybe; here's its type:

Prelude Control.Arrow> :m List
Prelude List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

So we'll take a function from b -> Maybe (a, b), a value of type b, and return a list of [a]. In our case, a = String and b = Integer.

All unfoldr does is call the function it's given as a first argument, which returns a tuple or Nothing. If it's a tuple, it appends its first element to a list and calls the same function with the second element. If it's Nothing, it returns the list it's built up to this point.

As we can see, that matches up perfectly with the "next" function we've already defined, and the unfoldr will build up a list of roman numeral strings:

Prelude> :m Control.Arrow List
Prelude Control.Arrow List> let numerals = [("X", 10), ("IX", 9), ("V", 5), 
("IV", 4), ("I", 1)]
Prelude Control.Arrow List> let next x = if x==0 then Nothing               
    else Just $ second (x-) $ head $ filter ((<=x) . snd) numerals
Prelude Control.Arrow List> unfoldr next 9
["IX"]
Prelude Control.Arrow List> unfoldr next 8
["V","I","I","I"]

(We had to mangle the definition of next a bit to fit into the interactive interpreter, but we haven't changed anything fundamental about it.)

Finally, all we have to do is concatenate the strings into our final result:

Prelude Control.Arrow List> (concat . unfoldr next) 8
"VIII"

Conclusion

Phew - that's an awful lot of information stuffed into a few pretty lines! I still have a hell of a time geting the types to match up so that I can write stuff like this, but that doesn't mean that I can't appreciate the beauty of how it all fits together. The original function presented here is tight in the very best sense of the word.