Haskell:f::hex String -> 使用尾递归的整数

Question

我正在寻找一种使用尾递归将十六进制更改为整数的方法。到目前为止，我只尝试过常规原始递归的糟糕实现，但我什至还没有接近。非常沮丧。即使是尾递归的例子也会有所帮助并且受到高度赞赏。我不太理解这个实现。

示例:

• “005”-> 5
• "1E"-> 30

限制:不能使用导入或 if、then、else 等，如果可能的话必须使用递归或尾递归。

我对递归的尝试。

    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

Answer 1

通常，对于尾递归函数，您需要一个累加器参数 - 具有纯度，否则结果可能仅取决于达到的基本情况。因此，您需要一个辅助函数，它还带有累加器参数，并使用累加器的初始值来调用它，

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

你必须找出来

• 您应该为累加器传递什么初始值
• 如何在每一步中更新累加器。

例如，reverse 的尾递归实现是

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

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

和尾递归阶乘(捏造负参数的情况)

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

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

这样就可以看到hexToIntegerHelper的大致结构了，

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

问题是如何根据旧累加器和十六进制数字计算新累加器(以及初始累加器应该是什么)。

对于累加器的更新，

digitToInt :: Char -> Int

来自 Data.Char 可能很有用，它可以处理所有十六进制数字。但是，它不会返回所需的类型，因此您需要使用 fromIntegral 或 toInteger 将 Int 转换为 整数。