最近一邊看「Haskell 函數(shù)式編程入門(mén)」一邊自學(xué) Haskell。函數(shù)式編程對(duì)筆者這種受OOP毒害頗深（雖然我完全不會(huì) Java，但是經(jīng)常會(huì)被別人來(lái)自 Java 背景的(:」∠)_）的菜鳥(niǎo)來(lái)說(shuō)，還是很難適應(yīng)的钞速。想著目前主力語(yǔ)言是 C++，一種多范式編程語(yǔ)言，學(xué)習(xí) Haskell 也算是自然而然吧聋溜。
學(xué)一門(mén)新語(yǔ)言還是很痛苦的，但是如果能做出什么的話(huà)還是很高興的叭爱！廢話(huà)就不多說(shuō)了撮躁。
已知
羅馬數(shù)字像是一種很有趣的五進(jìn)制，說(shuō)是五進(jìn)制买雾，但還不準(zhǔn)確把曼。在羅馬數(shù)字中杨帽，i 為 1，v 為 5嗤军，x 為 10注盈，l 為 50，c 為 100叙赚，但是 4、 9震叮、40、90 分別用 iv朴则、ix、xl钓简、xc 來(lái)表示乌妒，將小一級(jí)的羅馬數(shù)字放在左邊表示減法。1～10 羅馬數(shù)字為:i撤蚊、ii损话、iii侦啸、iv、v丧枪、vi光涂、vii、viii忘闻、ix恋博、x。
求解
在此筆者和「Haskell函數(shù)式編程入門(mén)」作者一樣只考慮 5000 以?xún)?nèi)的羅馬數(shù)字债沮。首先將幾個(gè)特殊的羅馬數(shù)字和與之對(duì)應(yīng)的十進(jìn)制數(shù)放在一起：
romeNotation :: [String]
romeNotation =
["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
romeAmount :: [Int]
romeAmount = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
pair :: [(Int, String)]
pair = zip romeAmount romeNotation
為什么是倒序的，請(qǐng)看下面的代碼：
subtrahend :: Int -> (Int, String)
subtrahend n = head (dropWhile (\(a, _) -> a > n) pair)
不難看出當(dāng)給這個(gè)函數(shù)傳入一個(gè)不大于 5000 的正整數(shù)時(shí)硅蹦，它將從 pair 列表中取得第一個(gè)比這個(gè)正整數(shù)小的數(shù)字，通過(guò) dropWhile 將 pair 中比給定正整數(shù)大的元組去掉提针，再取得列表第一個(gè)元素。有了這個(gè)元素饲宛，我們就能獲取到這個(gè)正整數(shù)對(duì)應(yīng)的羅馬數(shù)字嗜价。那么剩下的就簡(jiǎn)單了，只需要先將傳入的正整數(shù)減去這個(gè)元素對(duì)應(yīng)的數(shù)字久锥，然后再將差遞歸地轉(zhuǎn)換成羅馬數(shù)字即可。
> subtrahend 5
(5,"V")
> subtrahend 86
(50,"L")
下面定義函數(shù) convert 來(lái)將十進(jìn)制數(shù)轉(zhuǎn)換為羅馬數(shù)字絮重，首先定義遞歸的基本條件歹苦。如果轉(zhuǎn)換的數(shù)字是 0，那么返回空列表殴瘦，因?yàn)榱_馬數(shù)字中沒(méi)有表示 0 的符號(hào)，只需要返回 (0,"") 即可蚪腋。 0 在數(shù)字中其實(shí)是一個(gè)非常抽象的概念。在當(dāng)時(shí)立帖，也許羅馬人也不知道用什么來(lái)表示 0悠砚，這 里用的空字符串。下面再定義遞歸函數(shù)哩簿，使用 subtrahend 得到了減數(shù)节榜，得到了對(duì)應(yīng)的羅馬數(shù)字 rome 與對(duì)應(yīng)的數(shù)字 m，再遞歸地調(diào)用 convert 函數(shù)轉(zhuǎn)換余下的十進(jìn)制數(shù)宗苍，即 convert (n-m)，最后返回未轉(zhuǎn)換的部分和兩個(gè)羅馬數(shù)字字符串連接：
convert :: Int -> String
convert 0 = ""
convert n = let (rome, m) = subtrahend n in m ++ convert (n - rome)
> convert 12
"XII"
> convert 109
"CIX"
> convert 1925
"MCMXXV"
> convert 4567
"MMMMDLXVII"
是不是很簡(jiǎn)單让歼？??幾個(gè)小時(shí)前的筆者是跪了的╮(╯▽╰)╭丽啡，所以筆者決定貼心的用等式推導(dǎo)來(lái)演算一下 convert 17 的計(jì)算過(guò)程：
convert 17
= "X" ++ convert (17 - 10)
= "X" ++ "V" ++ convert (7 - 5)
= "X" ++ "V" ++ "I" convert (2 - 1)
= "X" ++ "V" ++ "I" ++ "I" convert (1 - 1)
= "X" ++ "V" ++ "I" ++ "I" ++ ""
= "XVII"
聰明的各位應(yīng)該已經(jīng)看出來(lái)問(wèn)題了，在計(jì)算的時(shí)候改执，要暫時(shí)存儲(chǔ)中間的值坑雅。"X", "V", "I", "I" 這些中間的值在計(jì)算到達(dá)基本條件前沒(méi)有任何的用處。顯然裹粤，這樣對(duì)于內(nèi)存空間的使用效率是不高的。所以應(yīng)該將 convert 改成尾遞歸的形式拇泣。不過(guò)筆者比較菜突那，聰明的你可以試試。
擴(kuò)展
那么既然已經(jīng)可以把十進(jìn)制數(shù)字轉(zhuǎn)成羅馬數(shù)字了愕难，理所當(dāng)然也應(yīng)該將一個(gè) 5000 以?xún)?nèi)的羅馬數(shù)字轉(zhuǎn)換為一個(gè)十進(jìn)制數(shù)字。
思路也很簡(jiǎn)單葱弟，首先從大到小匹配羅馬數(shù)字是否以 ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] 中的字符串開(kāi)頭猜丹，只需要找到第一個(gè)符合的字符串，就知道對(duì)應(yīng)的十進(jìn)制正整數(shù)藏杖，然后截?cái)嗔_馬數(shù)字脉顿，把剩下的羅馬數(shù)字字符串遞歸執(zhí)行同一函數(shù)，直到羅馬數(shù)字全部處理完艾疟，此時(shí)所有十進(jìn)制正整數(shù)相加即可敢辩。
所以我們只需要稍微修改一下 subtrahend 和 convert 即可：
import Data.List
import Data.Maybe
subtrahend' :: String -> (Int, String)
subtrahend' n = head (dropWhile (\(_, a) -> not (a `isPrefixOf` n)) pair)
convert' :: String -> Int
convert' [] = 0
convert' n =
let (rome, m) = subtrahend' n
in rome + convert' (fromMaybe "" (stripPrefix m n))
> convert' "XII"
12
> convert' "CIX"
109
> convert' "MCMXXV"
1925
> convert' "MMMMDLXVII"
4567
當(dāng)然也可以改成尾遞歸弟疆，而且還應(yīng)該有異常處理，但這里就不繼續(xù)展開(kāi)了同廉。
后記
相信看到這里嘀略，大家也對(duì) Haskell 這么語(yǔ)言有一定的了解了吧。在沒(méi)學(xué) Haskell 之前經(jīng)常聽(tīng)說(shuō)函數(shù)在 Haskell 中是一等公民咒程，不是很理解讼育，現(xiàn)在看何止是一等公民啊，是壓根就一個(gè)公民(:」∠)_
而且在 Haskell 中也沒(méi)有 for loop 這種迭代利器奶段，所以很多時(shí)間逼著你考慮遞歸，但是野語(yǔ)有之曰：
"To iterate is human, to recur, divine." - L. Peter Deutsch
遞歸這種神跡對(duì)于筆者這樣的菜雞凡人還是很難的呢铆，所以要學(xué)好 Haskell 還是任重而道遠(yuǎn)啊蹲缠。
