f# - 进一步优化 F# 中的 Number to Roman Numeral 函数

Question

我是 F# 的新手，我很好奇这是否还能进一步优化。我不确定我是否也正确地做到了这一点。我特别好奇最后一行，因为它看起来真的很长而且很丑陋。

我在谷歌上搜索过，但只显示罗马数字到数字的解决方案，所以我很难比较。

type RomanDigit = I | IV | V | IX
let rec romanNumeral number =
    let values = [ 9; 5; 4; 1 ]
    let capture number values =
            values
            |> Seq.find ( fun x -> number >= x )
    let toRomanDigit x =
        match x with
        | 9 -> IX
        | 5 -> V
        | 4 -> IV
        | 1 -> I
    match number with
    | 0 -> []
    | int -> Seq.toList ( Seq.concat [ [ toRomanDigit ( capture number values ) ]; romanNumeral ( number - ( capture number values ) ) ] )

感谢任何可以帮助解决此问题的人。

Answer 1

递归查找可以从值中减去的最大数字表示的稍短的方法（使用 List.find）：

let units =
    [1000, "M"
     900, "CM"
     500, "D"
     400, "CD"
     100, "C"
     90, "XC"
     50, "L"
     40, "XL"
     10, "X"
     9, "IX"
     5, "V"
     4, "IV"
     1, "I"]

let rec toRomanNumeral = function
    | 0 -> ""
    | n ->
        let x, s = units |> List.find (fun (x,s) -> x <= n)
        s + toRomanNumeral (n-x)

Answer 2

如果我必须使用有区别的联合来表示罗马字母，我不会包括 IV 和 IX。

type RomanDigit = I|V|X

let numberToRoman n =       
   let (r, diff) =
        if   n > 8 then [X], n - 10
        elif n > 3 then [V], n -  5
        else [], n
   if diff < 0 then I::r
   else r @ (List.replicate diff I)

然后，基于此解决方案，您可以更进一步并将其扩展到所有数字。

这是我的第一次尝试，使用折叠和部分应用程序：

type RomanDigit = I|V|X|L|C|D|M

let numberToRoman n i v x = 
    let (r, diff) =
        if   n > 8 then [x], n - 10
        elif n > 3 then [v], n -  5
        else [], n
    if diff < 0 then i::r
    else r @ (List.replicate diff i)

let allDigits (n:int) =
    let (_, f) = 
        [(I,V); (X,L); (C,D)] 
        |> List.fold (fun (n, f) (i, v) -> 
            (n / 10, fun x -> (numberToRoman (n % 10) i v x) @ f i)) (n, (fun _ -> []))
    f M

Answer 3

这是@Philip Trelford 答案的尾递归版本：

let toRomanNumeral n =
    let rec iter acc n =
        match n with
        | 0 -> acc
        | n ->
            let x, s = units |> List.find (fun (x, _) -> x <= n)
            iter (acc + s) (n-x)

    iter "" n