Haskell: f :: hex String - Integer using tail recursion

Question

I'm looking for a way to change hex to an integer using tail recursion. So far I've only tried terrible implementations of regular primitive recursion and I haven't even gotten close. Very frustrated. Even examples of tail recursion will help and be greatly appreciated. I don't quite understand it well enough for this implementation. Example: - `"005" -> 5` - `"1E" -> 30` Restrictions: Cannot use imports or if, then, else etc, must be done with recursion if possible or tail recursion. My attempt at recursion. ``` hexToInteger :: String -> Integer |(x:xs) = [] = [] |x == 0 = hexToInteger xs |otherwise = addition x + hexToInteger xs addition :: String -> Integer addition x |--something to check what position we're dealing with and what hex value. |--Return the Integer value ```

Accepted Answer

Generally, for tail-recursive functions, you need an accumulator argument -- with purity, the result could otherwise only depend on the base case reached. So you would need a helper function taking also an accumulator argument, and call that with an initial value for the accumulator,

```
hexToInteger :: String -> Integer
hexToInteger string = hexToIntegerHelper initialAccumulator string
```

and you must find out

- what initial value you should pass for the accumulator

- how the accumulator has to be updated in each step.

For example, a tail-recursive implementation of `reverse` is

```
reverse :: [a] -> [a]
reverse xs = reverseHelper [] xs

reverseHelper :: [a] -> [a] -> [a]
reverseHelper accumulator [] = accumulator
reverseHelper accumulator (x:xs) = reverseHelper (x:accumulator) xs
```

and a tail-recursive factorial (fudging the case of a negative argument)

```
factorial :: Integer -> Integer
factorial n = factorialHelper 1 n

factorialHelper :: Integer -> Integer -> Integer
factorialHelper accumulator n
    | n < 2     = accumulator
    | otherwise = factorialHelper (n*accumulator) (n-1)
```

So you can see the general structure of `hexToIntegerHelper`,

```
hexToIntegerHelper :: Integer -> String -> Integer
hexToIntegerHelper accumulator "" = accumulator
hexToIntegerHelper accumulator (d:ds) = hexToIntegerHelper (newAccumulatorFrom accumulator d) ds
```

and the question is how the new accumulator is to be computed from the old one and the hexadecimal digit (and what the initial accumulator should be).

For the updating of the accumulator,

```
digitToInt :: Char -> Int
```

from `Data.Char` could be useful, that handles all hexadecimal digits. But, it doesn't return the desired type, so you'd need to use a `fromIntegral` or a `toInteger` to convert the `Int` to `Integer`.

Haskell: f :: hex String -> Integer using tail recursion

Solution

Problem