I recently taught myself Haskell while reading “Introduction to Haskell Functional Programming”. Functional programming is hard for a novice OOP addict like me (although I don’t know Java at all, I’m often exposed to other people from Java backgrounds). Given that the main language is C++, a multiparadigm programming language, learning Haskell is a natural progression. Learning a new language is still a pain, but it’s still fun if you can make something of it! Without further ado.

known

Roman numerals are kind of an interesting quintuple, but they’re not exactly quintuple. In Roman numerals, I is 1, V is 5, x is 10, L is 50, and C is 100, but 4, 9, 40, and 90 are represented by iv, ix, XL, and XC, respectively, with the lower Roman numerals placed to the left to indicate subtraction. Roman numerals from 1 to 10 are I, II, III, IV, V, VI, vii, VIII, ix, and X.

To solve the

Here, like the author of “Introduction to Haskell Functional Programming,” I only consider Roman numerals up to 5,000. First we put together a few special Roman numerals with their decimal counterparts:

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
Copy the code

Why is it in reverse order? Look at the following code:

subtrahend: :Int- > (Int.String)
subtrahend n = head (dropWhile (\(a, _) -> a > n) pair)
Copy the code

As you can see, when you pass this function a positive integer not greater than 5000, it retrieves the first number in the pair list that is less than the positive integer, uses dropWhile to remove any tuple in the pair that is greater than the given positive integer, and retrieves the first element in the list. With this element, we can get the Roman numeral corresponding to the positive integer. All that is left is to subtract the element’s number from the positive integer passed in, and then recursively convert the difference to Roman numerals.

> subtrahend 5
(5."V")
> subtrahend 86
(50."L")
Copy the code

Let’s define the function convert to convert decimal numbers to Roman numerals, first defining the basic conditions for recursion. If the converted number is 0, the empty list is returned, since there is no sign for 0 in Roman numerals, just return (0,””). 0 is actually a very abstract concept in numbers. At the time, maybe the Romans didn’t know what to use for zero either, so this is an empty string. Subtrahend is used to obtain the subtraction, and the corresponding Roman numeral Rome and the corresponding numeral M are obtained. The convert function is recursively called to convert the remaining decimal number, namely convert (n-m). Finally returns the unconverted portion and the concatenation of two Roman numeric strings:

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"
Copy the code

Isn’t that easy? 😂 a few hours ago, I was on my knees, and I decided to use the equations to calculate 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"
Copy the code

If you’re smart enough to see the problem, you have to temporarily store the intermediate value while you’re doing the calculation.” “X”, “V”, “I”, “I”, these intermediate values are of no use until the calculation reaches the basic condition. Obviously, this is not an efficient use of memory space. So convert should be changed to tail recursion. However, I compare dishes, smart you can try.

extension

Now that you can convert a decimal number to a Roman number, it makes sense to convert a Roman number up to 5000 to a decimal number. Thinking is also very simple, first of all, from big to small matching if Roman numerals to [” M “, “CM”, “D”, “CD” and “C”, “XC”, “L”, “XL”, “X”, “IX”, “V”, “IV”, “I”] string in the beginning, only need to find the first in line with the string, We know the corresponding positive decimal integer, and then truncate the Roman numeral, and recursively perform the same function for the rest of the Roman numeral string, until all the Roman numeral processing is complete, at which point all the positive decimal integer can be added. So we just need to modify subtrahend and convert slightly:

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
Copy the code

It could have been tail recursion, and there should have been exception handling, but I’m not going to expand here.

Afterword.

I believe that you have some understanding of Haskell language. In Haskell, there is no for loop iteration tool, so you have to spend a lot of time thinking about recursion. But there is something to be said:

“To iterate is human, to recur, divine.” – L. Peter Deutsch

The miracle of recursion is difficult for a mere mortal like me, so Haskell has a long way to go.