使用 haskell 将十进制数字转成罗马数字

https://0x11901.github.io/

最近一边看「Haskell 函数式编程入门」一边自学 Haskell。函数式编程对笔者这种受OOP毒害颇深（虽然我完全不会 Java，但是经常会被别人来自 Java 背景的_(:」∠)）的菜鸟来说，还是很难适应的。想着目前主力语言是 C++，一种多范式编程语言，学习 Haskell 也算是自然而然吧。
学一门新语言还是很痛苦的，但是如果能做出什么的话还是很高兴的！废话就不多说了。

已知

求解

在此笔者和「Haskell函数式编程入门」作者一样只考虑 5000 以内的罗马数字。首先将几个特殊的罗马数字和与之对应的十进制数放在一起：

1
2
3
4
5
6
7
8
9

 :: [String]
 =
    ["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

为什么是倒序的，请看下面的代码：

1
2

subtrahend :: Int -> (Int, String)
subtrahend n = head (dropWhile ((a, _) -> a > n) pair)

不难看出当给这个函数传入一个不大于 5000 的正整数时，它将从 pair 列表中取得第一个比这个正整数小的数字，通过 dropWhile 将 pair 中比给定正整数大的元组去掉，再取得列表第一个元素。有了这个元素，我们就能获取到这个正整数对应的罗马数字。那么剩下的就简单了，只需要先将传入的正整数减去这个元素对应的数字，然后再将差递归地转换成罗马数字即可。

1
2
3
4

> subtrahend 5
(5,"V")
> subtrahend 86
(50,"L")

下面定义函数 convert 来将十进制数转换为罗马数字，首先定义递归的基本条件。如果转换的数字是 0，那么返回空列表，因为罗马数字中没有表示 0 的符号，只需要返回 (0,””) 即可。 0 在数字中其实是一个非常抽象的概念。在当时，也许罗马人也不知道用什么来表示 0，这 里用的空字符串。下面再定义递归函数，使用 subtrahend 得到了减数，得到了对应的罗马数字 rome 与对应的数字 m，再递归地调用 convert 函数转换余下的十进制数，即 convert (n-m)，最后返回未转换的部分和两个罗马数字字符串连接：

1
2
3
4
5
6
7
8
9
10
11
12

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 的计算过程：

1
2
3
4
5
6
7

  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 改成尾递归的形式。不过笔者比较菜，聪明的你可以试试。

扩展

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

后记