Monday, January 14, 2008

Roman numerals in Scala

I just read about converting Ints to Romans numerals in Python and Haskell and thought... gee... I can do that in Scala:

def romanize(number: Int) = {
val numerals = List(("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(in: Int) = numerals.filter(_._2 <= in) match {
case (s, v) :: _ => Some((s, in - v))
case _ => None


def unfold[T, R](init: T)(f: T => Option[(R, T)]): List[R] = f(init) match {
case None => Nil
case Some(r, v) => r :: unfold(v)(f)

The 'unfold' function is not part of the standard Scala distribution, but looks to be darned useful. It takes an initial value and a function that returns the "next" thing and unrolls the initial value into a List. Nifty.

The actual "romanize" function contains a local definition of the roman numerals and the "next" function which finds the next match in the list of roman numerals. This function, along with the initial value are passed into unfold which returns a List of Roman numerals. mkString turns the list in a single String.

Short, sweet, and to my eye, the Scala and Haskell versions are very similar in complexity.


Maurice Codik said...

Cool stuff. In the definition of "next", could you explain how the '_._2 <= in' part works? It's the only part thats a little unclear to me..

Maurice Codik said...

Ah nm.. got it:

The first '_' is the normal scala shorthand for the first parameter of the anonymous function.

The second '_' is part of the '_2' val, that returns the second part of the tuple. The '_' in '_2' threw me off.

Daniel Green said...

def deromanize(roman : String) : int =
numerals.filter(roman startsWith _._1).sort(_._1.length > _._1.length) match {
case (s, v) :: _ => v + deromanize(roman.substring(s.length))
case Nil => 0


Germán said...

Interesting piece of code, I found it useful to get my head around it. And after taking a quick look at Daniel's deromanize function, I tried to make it myself without peeking. It took a few tries... and peeks... but well, that's how you learn! At some point I'll be able to write stuff like that more naturally.
My favorite parts from ScalaByExample were the exercises... can you guys come up with some in this blog?? That's valuable training!

Sarah A said...
This comment has been removed by the author.
Sarah A said...

Incidentally, there is a deep category-theoretical foundation to the unfold operation: it's formally known as a anamorphism (or sometimes the lens operator).

The classic paper Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire provides great insight into several standard recursive operators, and should be considered required reading for serious functional programmers.

I'm surprised to hear that Scala lacks unfold: I hope it will appear in a future release!

al said...

In the definition of "unfold"
"case Some(r, v)" should actually be
"case Some((r, v))" (extra parenthesis).

jimmy wilson said...

Great, it is not only interesting blog but informative too

Brad Pitt Jacket Fight Club

Harish Yes said...

I have enjoyed this great info so much. This was really very interesting and helpful to read. I can't wait to read more from this site. packers and movers bangalore packers and movers bangalore marathahalli packers and movers marathahalli packers and movers hsr layout packers and movers btm layout packers and movers bommanahalli packers and movers whitefield packers and movers koramangala packers and movers jp nagar

Greenwood Jonny said...

obat sipilis di bandung
jual obat sipilis bandung
antibiotik sifilis
obat antibiotik buat sipilis
obat tradisional buat sipilis
obat herbal buat sipilis
obat dokter buat sipilis
obat generik buat sipilis pada pria yang manjur
obat cina buat penyakit sipilis
obat sipilis yang bagus dan murah
obat sipilis di batam
nama obat buat sipilis yang manjur

Dedi Abdullah said...

kutil kelamin di liang vagina
Yang jual obat kutil kelamin di daerah bngkinang ada tidak?
jual obat untuk kutil kelamin di kota semarang
jual obat kutil penis daerah sorong
jual obat kutil kelamin di solo
penyakit memegang alat kelamin
kelamin wanita hamil
obat hpv 11 pada wanita
Tubuh wanita yang akan melakukan proses persalinan
obat kutil tradisional