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
}
unfold(number)(next).mkString("")
}
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.
Monday, January 14, 2008
Roman numerals in Scala
Subscribe to:
Post Comments (Atom)
7 comments:
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..
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.
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
}
woo!
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!
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!
In the definition of "unfold"
"case Some(r, v)" should actually be
"case Some((r, v))" (extra parenthesis).
Post a Comment