Romanize a number

[sma]

Manchmal hat die Würze der Kürze einen unangenehmen Beigeschmack. Dieses Haskell-Programm sieht zwar elegant aus, aber ich finde es schwer verdaulich.

Code: Alles auswählen

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

Eine Zahl wird als "römische Zahl" dargestellt, indem man von der größten "Zahl" M bis zur kleinsten I schaut, wie oft die in der übergebenen Zahl steckt. Die Ergebnisliste wird schließlich zu einem String.

Code: Alles auswählen

def romanize(n):
  result = []
  for r, v in (('M', 1000), ...):
    while n >= v:
      n -= v
      result.append(r)
  return "".join(result)

Diese Lösung ist jedoch imperativ, nicht funktional, denn ich verändere Variablen. Das explizite Bauen der Ergebnisliste kann ich schon mal so vermeiden:

Code: Alles auswählen

def romanize(n):
  def next(n):
    for r, v in numerals:
      while n >= v:
        n -= v
        yield r
  return "".join(next(n))

Das Haskell-Beispiel iteriert AFAICT mehrfach über numerals. Das kann ich natürlich auch (statt einer Maybe-Monade benutze ich Generatoren):

Code: Alles auswählen

def ifold(f, x):
    while True:
      r, x = f(x).next()
      yield r

def romanize(n):
  def next(n):
    for r, v in numerals:
      if n >= v:
        yield r, n - v
  return "".join(ifold(next, n))

Obige Lösung ist zwar streng genommen noch imperativ, aber ifold könnte man auch rekursiv definieren, wenn Generatoren das nicht verhindern würden und Python generell Endrekursion optimieren würden. Ich folge aber dem Single-Assignment-Paradigma und das halte ich für das wesentliche Merkmal funktionaler Programmierung.

Würde itertools bereits ifold enthalten, wäre diese Lösung sogar recht kurz:

Code: Alles auswählen

def romanize(n):
  def next(n): return ((r, n - v) for r, v in numerals if n >= v)
  return "".join(ifold(next, n))

Tja, das wollte ich angeregt durch diesen Blogeintrag einfach mal loswerden :)

Stefan