Haskell: recursively convert hex string to integer?

Question

For my homework assignment, I need to convert a hexadecimal string to a base-10 integer using a recursive function (with as many helper methods as necessary).

This is what I've got so far:

-- Question 1, part (c):
hexChar :: Char -> Integer
hexChar ch
    | ch == '0' = 0
    | ch == '1' = 1
    | ch == '2' = 2
    | ch == '3' = 3
    | ch == '4' = 4
    | ch == '5' = 5
    | ch == '6' = 6
    | ch == '7' = 7
    | ch == '8' = 8
    | ch == '9' = 9
    | ch == 'A' = 10
    | ch == 'B' = 11
    | ch == 'C' = 12
    | ch == 'D' = 13
    | ch == 'E' = 14
    | ch == 'F' = 15
    | otherwise     = 0

parseHex :: String -> Integer
parseHex hxStr 
    | length hxStr /= 0 = (hexChar(last(hxStr)))+(10*parseHex(init(hxStr)))
    | otherwise         = 0  

However, this does not produce the correct results. Does anyone know of the correct way to do this?

Answer 1

You are really close. your error is on this line:

    | length hxStr /= 0 = (hexChar(last(hxStr)))+(10*parseHex(init(hxStr)))

Think about why you are multiplying by 10. Remember ... Hexadecimal is base 16.

Answer 2

Now that you got the right answer, you should consider the style. Using pattern matching, this looks clearer already:

parseHex :: String -> Integer
parseHex [] = 0
parseHex hxStr = (hexChar(last(hxStr)))+(16*parseHex(init(hxStr)))

And it's also more efficient, as you don't need to evalute length hxStr (which is O(N)) at each recursive call to decide which case applies. Total runtime goes from O(N**2) to O(N).

It looks even better when you drop some parentheses, as groovy suggested:

parseHex :: String -> Integer
parseHex [] = 0
parseHex hxStr = hexChar (last hxStr) + 16 * parseHex (init hxStr))

It's unfortunate that you can't pattern match on hStr right away because you need init and last instead of head and tail. But you can mitigate that using reverse and a helper:

parseHex :: String -> Integer
parseHex hxStr = go (reverse hxStr)
    where go []     = 0
          go (x:xs) = hexChar x + 16 * parseHex xs

That last one may be just a matter of taste though. hexChar also becomes shorter:

hexChar '0' = 0
hexChar '1' = 1
...                  -- other cases here
hexChar _ = 0        -- 'otherwise' case; maybe throw an error instead?