Romanize a number
Verfasst: Mittwoch 16. Januar 2008, 19:10
Manchmal hat die Würze der Kürze einen unangenehmen Beigeschmack. Dieses Haskell-Programm sieht zwar elegant aus, aber ich finde es schwer verdaulich.
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.
Diese Lösung ist jedoch imperativ, nicht funktional, denn ich verändere Variablen. Das explizite Bauen der Ergebnisliste kann ich schon mal so vermeiden:
Das Haskell-Beispiel iteriert AFAICT mehrfach über numerals. Das kann ich natürlich auch (statt einer Maybe-Monade benutze ich Generatoren):
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:
Tja, das wollte ich angeregt durch diesen Blogeintrag einfach mal loswerden :)
Stefan
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)]
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)
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))
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))
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))
Stefan