Clever Geek Handbook

Haskell: recursively convert hex string to integer?

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

This is what I have 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 give the correct results. Does anyone know how to do this correctly?

+3


source to share


3 answers


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 base is 16.

+4


source


Now that you've got the right answer, you must consider the style. Using pattern matching this looks clearer:

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

And it's also more efficient, since you don't have to check length hxStr

(which is O (N)) with every recursive call to decide which case. Total execution time from O (N ** 2) to O (N).

It looks even better when you strip away some of the 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 match up hStr

directly, because you need init

both last

instead of head

and tail

. But you can reduce this by using a reverse

helper as well:

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

However, the latter may only be a matter of taste. hexChar

also gets shorter:

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


source


After the problem is resolved, here's a shorter way to write this:

import Data.List
import Data.Maybe

hexChar ch = fromMaybe (error $ "illegal char " ++ [ch]) $ 
    elemIndex ch "0123456789ABCDEF"

parseHex hex = foldl' f 0 hex where
    f n c = 16*n + hexChar c
+4


source






More articles:


All Articles