最近一边看「Haskell 函数式编程入门」一边自学 Haskell。函数式编程对笔者这种受OOP毒害颇深（虽然我完全不会 Java，但是经常会被别人来自 Java 背景的(:」∠)_）的菜鸟来说，还是很难适应的。想着目前主力语言是 C++，一种多范式编程语言，学习 Haskell 也算是自然而然吧。
学一门新语言还是很痛苦的，但是如果能做出什么的话还是很高兴的！废话就不多说了。
已知
罗马数字像是一种很有趣的五进制，说是五进制，但还不准确。在罗马数字中，i 为 1，v 为 5，x 为 10，l 为 50，c 为 100，但是 4、 9、40、90 分别用 iv、ix、xl、xc 来表示，将小一级的罗马数字放在左边表示减法。1∼10 罗马数字为:i、ii、iii、iv、v、vi、vii、viii、ix、x。
求解
在此笔者和「Haskell函数式编程入门」作者一样只考虑 5000 以内的罗马数字。首先将几个特殊的罗马数字和与之对应的十进制数放在一起：
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
为什么是倒序的，请看下面的代码：
subtrahend :: Int -> (Int, String)
subtrahend n = head (dropWhile (\(a, _) -> a > n) pair)
不难看出当给这个函数传入一个不大于 5000 的正整数时，它将从 pair 列表中取得第一个比这个正整数小的数字，通过 dropWhile 将 pair 中比给定正整数大的元组去掉，再取得列表第一个元素。有了这个元素，我们就能获取到这个正整数对应的罗马数字。那么剩下的就简单了，只需要先将传入的正整数减去这个元素对应的数字，然后再将差递归地转换成罗马数字即可。
> subtrahend 5
(5,"V")
> subtrahend 86
(50,"L")
下面定义函数 convert 来将十进制数转换为罗马数字，首先定义递归的基本条件。如果转换的数字是 0，那么返回空列表，因为罗马数字中没有表示 0 的符号，只需要返回 (0,"") 即可。 0 在数字中其实是一个非常抽象的概念。在当时，也许罗马人也不知道用什么来表示 0，这 里用的空字符串。下面再定义递归函数，使用 subtrahend 得到了减数，得到了对应的罗马数字 rome 与对应的数字 m，再递归地调用 convert 函数转换余下的十进制数，即 convert (n-m)，最后返回未转换的部分和两个罗马数字字符串连接：
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"
是不是很简单？😂几个小时前的笔者是跪了的╮(╯▽╰)╭，所以笔者决定贴心的用等式推导来演算一下 convert 17 的计算过程：
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"
聪明的各位应该已经看出来问题了，在计算的时候，要暂时存储中间的值。"X", "V", "I", "I" 这些中间的值在计算到达基本条件前没有任何的用处。显然，这样对于内存空间的使用效率是不高的。所以应该将 convert 改成尾递归的形式。不过笔者比较菜，聪明的你可以试试。
扩展
那么既然已经可以把十进制数字转成罗马数字了，理所当然也应该将一个 5000 以内的罗马数字转换为一个十进制数字。
思路也很简单，首先从大到小匹配罗马数字是否以 ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] 中的字符串开头，只需要找到第一个符合的字符串，就知道对应的十进制正整数，然后截断罗马数字，把剩下的罗马数字字符串递归执行同一函数，直到罗马数字全部处理完，此时所有十进制正整数相加即可。
所以我们只需要稍微修改一下 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
当然也可以改成尾递归，而且还应该有异常处理，但这里就不继续展开了。
后记
相信看到这里，大家也对 Haskell 这么语言有一定的了解了吧。在没学 Haskell 之前经常听说函数在 Haskell 中是一等公民，不是很理解，现在看何止是一等公民啊，是压根就一个公民(:」∠)_
而且在 Haskell 中也没有 for loop 这种迭代利器，所以很多时间逼着你考虑递归，但是野语有之曰：
"To iterate is human, to recur, divine." - L. Peter Deutsch
递归这种神迹对于笔者这样的菜鸡凡人还是很难的，所以要学好 Haskell 还是任重而道远啊。
网友评论