5

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

例子：

  • "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
4

3 回答 3

9

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

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

fromData.Char可能很有用，它可以处理所有十六进制数字。但是，它不会返回所需的类型，因此您需要使用 afromIntegral或 atoInteger将其转换Int为Integer.

于 2013-02-17T22:52:03.377 回答
2

Here are two recursive functions, although it has been pointed out to me that they are not tail recursive. Maybe they can help you get there, though.

hexToInteger :: String -> Integer
hexToInteger [] = 0
hexToInteger str = 
  fromIntegral z + 16 * hexToInteger (init str)
    where z = let y = last str 
              in if y >= 'A' && y <= 'Z' 
                    then fromEnum y - 55 
                    else if y >= 'a' && y <= 'z'
                            then fromEnum y - 87
                            else fromEnum y - 48



hexToInteger :: String -> Integer
hexToInteger [] = 0
hexToInteger str = 
  z + 16 * hexToInteger (init str)
    where z = case last str of 
                '0' -> 0 
                '1' -> 1 
                '2' -> 2 
                '3' -> 3 
                '4' -> 4 
                '5' -> 5 
                '6' -> 6 
                '7' -> 7 
                '8' -> 8 
                '9' -> 9 
                'A' -> 10 
                'B' -> 11 
                'C' -> 12 
                'D' -> 13 
                'E' -> 14 
                'F' -> 15
                'a' -> 10 
                'b' -> 11 
                'c' -> 12 
                'd' -> 13 
                'e' -> 14 
                'f' -> 15
                otherwise -> 0
于 2013-02-17T23:46:01.970 回答
0

我们可以像在纸上转换十六进制字符串一样实现这一点：将输出初始化为 0，然后从左到右读取字符串，每次将结果乘以 16 并添加新数字。

创建并调用一个将累加器参数初始化为 0 的私有函数：

hex2int s = hex2int' s 0
    where

递归的基本情况采用空字符串并返回累加器：

        hex2int' "" n = n

递归情况采用字符串的第一个字符并相应地增加累加器。

        hex2int' (c:s) n = hex2int' s ((n * 16) + (hexDigit2int c))

hexDigit2int是一个简单的查找。

        hexDigit2int c
          | c == "0" = 0

         ...

          | c == "f" = 15
于 2019-03-07T15:04:10.323 回答