Number of possible numbers in roman number string

Question

I just started learning programming a few months ago, and I'm intrigued by Haskell. To learn a bit I tried to adapt some code I have in Java so I can see what are equivalent solutions in Haskell.

The problem I had was to see how many different numbers can be "represented" by a string of roman numbers (0, .., 9, where X is equivalent to zero).

For example "I" means just one possible number (1), but "II" could be two possibilities: 11 (two "I") or 2 (one "II"). This is from some competitive programming website. Similar "XX" should give 1, since it represents 00 only. A bit bigger example: "IVII" should give 6, because there are 6 possibilities:

• "I" + "V" + "I" + "I" = 1511
• "I" + "V" + "II" = 152
• "I" + "VI" + "I" = 161
• "IV" + "I" + "I" = 411
• "I" + "VII" = 17
• "IV" + "II" = 42

Ok, that said, this is my Haskell code (first thing I write so far).

romanCombinations :: String -> Int
romanCombinations [] = 1
romanCombinations str = if length str == 1 then 1
 else foldr (+) 0 [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]
 where
 sep = map (divide str) $ take (length str) [1..4]
 divide str n = (take n str, drop n str)
 possibles = ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

What would you change in this Haskell code? I've never written anything before. Anything is welcome since I will probably learn from every comment. (I'm not asking about algorithms, but anything is welcome too)

• Zeta: Welcome to Code Review. If you never written anything in Haskell before, you might want to add the beginner tag to your question.

Answer 1

Use pattern matching to check for single-element lists

Let's start with romamCombination's second pattern:

romanCombinations str = if length str == 1 then 1

Compared to Java, length isn't a constant time operation in Haskell. It will traverse the whole list. If we only want to know if a list consists of a single element, we should pattern match to get a constant time behaviour:

romanCombinations [_] = 1

Use named variants of folds where applicable

Next, we will sum all elements in some list:

 -- we have to change the else due to the new pattern, but more on that later
 else foldr (+) 0 [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]

However, foldr (+) 0 is a common operation and therefore has a name in the Prelude: sum. We should use the named variant to convey our intend:

 else sum [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]

Similarly, divide is already in the Prelude, it's called splitAt, although the arguments are flipped:

 where
 divide str n = splitAt n str

Use Hoogle to find functions

But how would we find those functions? With Hoogle. If we search for Num a => \[a\] -> a, we will come across sum very soon, and if we search for [a] -> Int -> ([a], [a]), Hoogle will also find splitAt, even though the arguments are flipped.

Note that you sometimes need to use more general type signatures to find something with Hoogle.

All together so far

If we apply all those recommendations, we end up with

romanCombinations :: String -> Int
romanCombinations [] = 1
romanCombinations [_] = 1
romanCombinations str = sum [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]
 where
 sep = map (`splitAt` str) $ take (length str) [1..4]
 possibles = ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

Adjusting the length of a list by another list

We're already at the end. However, there is one last step we should take: get rid of the other length. That can be done with zip and map:

limit :: [a] -> [b] -> [b]
limit xs = map snd . zip xs

In case you're not familiar with pointfree-code, it's the same as

limit :: [a] -> [b] -> [b]
limit xs ys = map snd (zip xs ys)

As zip will end whenever the shorter list is exhausted, this will limit str to at most 4 elements in [1..4] and of course limit [1..4] to at most length str.

We end up with

romanCombinations :: String -> Int
romanCombinations [] = 1
romanCombinations [_] = 1
romanCombinations str = sum [ romanCombinations xs | (x, xs) <- sep , elem x possibles ]
 where
 sep = map (`splitAt` str) $ limit str [1..4]
 possibles = ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
limit :: [a] -> [b] -> [b]
limit xs = map snd . zip xs

Bottom line

All in all, your original code was already easy to read, had type signatures and uses simple splitting algorithm one can easily infer from your code. That being said, I haven't checked your algorithm or thought about improvements but only checked the code.

I recommend you to check the Prelude, as splitAt and sum are already available for your use without any import. Also, try to avoid length. Either work with the list immediately (e.g. map, fold, sum, ...) or pattern match.

Answer 2

Data.List saves us the number manipulation. The length-1 case reduces to the length-0 case.

romanCombinations :: String -> Int
romanCombinations [] = 1
romanCombinations str =
 sum $ map romanCombinations $ mapMaybe (`splitPrefix` str) 
 ["X", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]