Have you ever needed a way to convert Roman numerals into Arabic numerals programmatically? One day in March 2015, I realized I did. I was writing a Schematron rule to check cross references like “see pp. 1–4” that take the form of a range of page numbers. The rule simply checked whether the pages in the range were ordered as expected. For example, a page range like “5–4” had to be flagged as an error, since 4 comes before 5. But to perform this check on cross references that used Roman numerals, such as “pp. i–v”, I needed to find a way to convert Roman numerals into their Arabic numeral counterparts. For expediency’s sake, I used automation guru Sal Mangano’s roman-to-number() function (XSLT Cookbook, 2nd Edition, pp. 70–72). Conveniently for my purposes, Sal used XSLT 2, which I was able to embed directly into my Schematron file. (If you’re interested, see the commit where I embedded Sal’s function and invoked it in my schematron. Sal’s function is an interesting read; it uses XML’s guarantee of document order and the XPath following-sibling:: axis to check if the next numeral is greater than the current numeral.)

Although Sal’s XSLT function fit my immediate need, I was more at home with XQuery, so I was curious to find out if anyone had written an XQuery function for performing the same conversion. It’s generally not difficult to port XSLT functions to XQuery (since both languages share the same XPath foundation), but sometimes XQuery lends itself to different approaches. Searching via Google, I found one promising XQuery function, written by Mattio Valentino in ~2011. (Thanks to Mattio for resurrecting it as I was writing this article!) I liked his version but noticed that it was written in XQuery 1.0—naturally, given the time period—and thought it might benefit from some features of XQuery 3.0, such as inline functions, the simple map operator, and the switch expression. These features of XQuery 3.0 (which was still in draft form but had already been adopted by eXist-db) allowed me to reduce the number of functions from three to just one without sacrificing clarity. Problem solved and curiousity satisfied, I posted my version as a Gist and moved on.

Last week, I learned about an implementation of a Roman-to-Arabic numeral function written in Clojure from a post by Thad Guidry on the OpenRefine mailing list, and I was amazed that it required only 6 lines! In comparison, Sal’s XSLT 2.0 function was 63 lines long, Mattio’s XQuery 1.0 function was 40 lines (a handful fewer if you omit the comments), and my XQuery 3.0 version was 24 lines. Brevity doesn’t equal superiority, but I wondered, did the Clojure version contain any insights that we could apply to simplify and streamline the earlier XQuery versions?

While I don’t know Clojure, I tried to pick apart the function’s logic:

(defn ro2ar [r]
  (->> (reverse (.toUpperCase r))
       (map {\M 1000 \D 500 \C 100 \L 50 \X 10 \V 5 \I 1})
       (partition-by identity)
       (map (partial apply +))
       (reduce #(if (< %1 %2) (+ %1 %2) (- %1 %2)))))

I found it somewhat terse, but I deduced that it achieves most of its compactness through Clojure’s syntax for performing the fold function—a functional programming method for recursively processing a sequence of items and recombining the results to build up a return value. XQuery 3.0 had added a pair of functions for performing folds—fold-left() and fold-right()1—but I hadn’t taken advantage of them in my earlier adaptation of the Roman numeral function, because I didn’t really understand them at the time. It wasn’t until I worked on XQuery for Humanists that I took a serious look at the fold functions.2 Folds are really powerful and worth learning—as you’ll see below when we apply them to Roman numerals.

Besides folds, several other recent features of XQuery can simplify our function for Roman numeral processing. A large portion of the earlier XQuery functions were dedicated to spelling out how to convert individual Roman numeral symbols into integers: Sal used an XML lookup structure, Mattio used a conditional chain, and I had used a switch expression. The Clojure version used a map for this purpose, so I tried XQuery’s map facility and found this nicely simplified the lookup operation. I also found that XQuery’s array facility was a nice way to store and look up the tuple values for the fold function’s accumulator, i.e., [0, 0] as the starting values and [$running-total, $previous-number] for ongoing values. Also, to achieve a similarly clean, linear flow as the Clojure version, I applied XQuery’s arrow operator (=>), which allows us to elegantly pass values through a chain of functions. I also used XQuery’s for-each() function to help when I applied inline functions in arrow operator chains. Lastly, while XQuery doesn’t yet have a built-in function for splitting strings into characters, I was able to simplify the task of selecting each Roman numeral’s individual characters by applying XQuery’s powerful analyze-string() function.

Applying these techniques—folds, maps, the arrow operator, and the for-each() and analyze-string() functions—the new XQuery version weighs in at 24 lines, including liberal use of whitespace. It doesn’t sacrifice clarity, assuming you understand how folding works. (Don’t worry if you don’t; I’ll explain it below.) Here’s the XQuery:

xquery version "3.1";

module namespace r = "http://joewiz.org/ns/xquery/roman-numerals";

declare function r:decode-roman-numeral($roman-numeral as xs:string) as xs:integer {
    $roman-numeral
    => upper-case()
    => for-each( 
        function($roman-numeral-uppercase) { 
            analyze-string($roman-numeral-uppercase, ".")/fn:match/string()
        } 
    )
    => for-each( 
        map { "M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1 }
    )
    => fold-right( [0, 0], 
        function($number as xs:integer, $accumulator as array(*)) { 
            let $running-total := $accumulator?1
            let $previous-number := $accumulator?2
            return
                if ($number lt $previous-number) then
                    [ $running-total - $number, $number ]
                else
                    [ $running-total + $number, $number ]
        }
    )
    => array:head()
};

This updated XQuery 3.1 function takes a string containing a Roman numeral and performs the following operations:

  1. The Roman numeral is converted to uppercase.
  2. The uppercase Roman numeral is split into individual symbols.
  3. Each symbol is converted to its corresponding integer value.
  4. Moving through these integers from right to left, it compares each number to the previous value it had examined. (Upon first run, the starting “previous number” is simply 0.) If the current number is less than the previous number, the current number is subtracted from the running total, but otherwise, it is added to the running total. (Since the running total starts at 0, the first number is always added to 0, but any subsequent numbers will be added or subtracted accordingly.)
  5. Once all numerals have been exhausted, the final total is returned.

For example, given the Roman numeral “vi”, or 6:

  1. The string is converted to the uppercase “VI”.
  2. The uppercase Roman numeral split into individual symbols: V and I.
  3. These symbols are converted into two integers: 5 and 1.
  4. Proceeding from right to left, the first number checked is 1. Since 1 is greater than the default “previous number” (0), 1 is added to the default “running total” (0), yielding a value of 1.
  5. Continuing from right to left, the next number checked is 5. Since 5 is greater than the previous number (1), 5 is added to the “running total” (1), yielding a value of 6.
  6. With all numerals exhausted, the function returns the final “running total”: 6.

The fold-right() function is responsible for the logic starting with step 4. Starting with a default “running total” of 0 and a default “previous number” of 0 (these two default values comprise the function’s [0, 0] array), it begins running through each of the integers from right to left, one at a time. After each comparison, it updates the $accumulator variable with the new pair of values for the “running total” and “previous number.” Once it’s finished, we can access the final total by looking up the first value in the array returned by the fold-right() function.

A more complex example is “xliv”, or 44:

  1. The string is converted to the uppercase “XLIV”.
  2. The uppercase Roman numeral is split into individual symbols: X, L, I, and V.
  3. These symbols are converted into a sequence of 4 integers: 10, 50, 1, and 5.
  4. Proceeding from right to left, the first number checked is 5. Since 5 is greater than the default “previous number” (0), 5 is added to the default “running total” (0), yielding a value of 5.
  5. Continuing from right to left, the next number checked is 1. Since 1 is less than the “previous number” (5), 1 is subtracted from the “running total” (5), yielding a value of 4.
  6. The next number checked is 50. Since 50 is greater than the “previous number” (1), 50 is added to the “running total” (4), yielding a value of 54.
  7. The final number checked is 10. Since 10 is less than the “previous number” (50), 10 is subtracted from the “running total” (54), yielding a value of 44.
  8. With all numerals exhausted, the function returns the final “running total”: 44.

(Whereas my earlier XQuery 3.0 version raised an error when an invalid Roman numeral was included in the input string, this one just assigns any invalid symbols the value of 0.)

Looking ahead to XPath and XQuery 4.0, a community effort being actively discussed in the XML Community Slack (which just turned 1!), we’ll be able to streamline our code even more with these features:

  1. The new characters() function will let us jettison the inline function calling analyze-string()
  2. The new, short form of the inline function expression will let us jettison the verbose function expressions.
  3. Update (Oct 14, 2022): The lookup operator (“?”) for maps and arrays can now accept variable references without requiring them to be wrapped in parentheses.

Based on the draft spec, the XQuery 4.0 version will weigh in at 17 lines, using the same liberal whitespace:

declare function r:decode-roman-numeral($roman-numeral as xs:string) as xs:integer {
    $roman-numeral
    => upper-case()
    => characters()
    => for-each(
        map { "M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1 }
    )
    => fold-right( [0, 0], 
        ->($number, $accumulator) { 
            let $running-total := $accumulator?1
            let $previous-number := $accumulator?2
            return
                if ($number lt $previous-number) then
                    [ $running-total - $number, $number ]
                else
                    [ $running-total + $number, $number ]
        }
    )
    => array:head()
};

Applying a reasonably compact, still readable whitespace policy, we’ll be able to not just meet the Clojure version but beat it, with this 5 line equivalent:

declare function r:decode-roman-numeral($roman-numeral as xs:string) as xs:integer { 
    $roman-numeral => upper-case() => characters() 
    => for-each(map { "M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1 })
    => fold-right([0,0], ->($number, $accumulator) { if ($number lt $accumulator?2) then [ $accumulator?1 - $number, $number ] else [ $accumulator?1 + $number, $number ] } ) 
    => array:head() };

The purpose of such exercises, of course, is not to achieve the most compact or “best” implementation of this simple algorithm, but rather to illustrate how a simple challenge like converting Roman into Arabic numerals can be a gateway to powerful features built into XQuery, or your language of choice.3 The arrow operator, inline functions, and folds—all insights from functional programming—can both simplify and supercharge your XQuery. But, more generally, finding examples of how others have approached a challenge that you find interesting is a great way to learn, get things done, and—perhaps, before long—contribute your own take.

  1. XQuery 3.1 added a second pair of functions for performing folds with arrays instead of sequences: array:fold-left() and array:fold-right(). ↩

  2. In particular, see Chapter 8, “Thinking Functionally.” If you don’t have the book, we posted a code sample from our discussion of fold-left(). ↩

  3. Rosetta Code, a “programming chrestomathy,” offers a compilation of many languages’ approaches to Roman numeral conversion. The same site provides a list of similar sites. For a fun look at how to accomplish one feat in many languages, see 99 Bottles of Beer, with over 1,500 languages and variations (including two in XQuery). ↩