Haskell: f :: hex String -> Ganzzahl mit Tail Rekursion

Question

Ich bin auf der Suche nach einer Möglichkeit, hex in eine ganze Zahl mit Tail-Rekursion zu ändern. Bis jetzt habe ich nur schreckliche Implementierungen der regulären primitiven Rekursion probiert, und ich bin nicht einmal nahe gekommen. Sehr frustriert. Selbst Beispiele für Tail Recursion werden helfen und sehr geschätzt werden. Ich verstehe es nicht gut genug für diese Implementierung.

Beispiel:

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

Beschränkungen: Kann nicht die Einfuhr verwenden oder wenn, dann, sonst etc, müssen mit Rekursion, wenn möglich oder Endrekursion erfolgen.

Mein Versuch der Rekursion.

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

Im Allgemeinen für tail-rekursive Funktionen, benötigen Sie einen Akkumulator Argument - mit Reinheit, könnte das Ergebnis sonst nur auf dem Basisfall erreicht abhängen. So würden Sie eine Hilfsfunktion benötigen auch einen Akkumulator Argument nehmen, und rufen, dass mit einem Anfangswert für den Akkumulator,

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

und Sie müssen

• was Sie Anfangswert herauszufinden, für den Pass sollte Akkumulator
• wie der Akkumulator in jedem Schritt aktualisiert werden muss.

Zum Beispiel kann ein tail-rekursive Implementierung von reverse ist

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

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

und einen Schwanz-rekursive faktorielles (den Fall eines negativen Argument fudging)

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 können Sie sehen, die allgemeine Struktur von hexToIntegerHelper,

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

und die Frage ist, wie der neue Akkumulator aus dem alten und der hexadezimalen Zahl berechnet werden soll (und was der anfängliche Akkumulator sein soll).

Für die Aktualisierung des Speichers könnte

digitToInt :: Char -> Int 

von Data.Char nützlich sein, dass kümmert sich um alle hexadezimalen Ziffern. Es wird jedoch nicht der gewünschte Typ zurückgegeben. Sie müssen also fromIntegral oder toInteger verwenden, um Int in Integer zu konvertieren.

Answer 2

Hier sind zwei rekursive Funktionen, obwohl darauf hingewiesen worden ist, dass sie nicht tail rekursiv sind. Vielleicht können sie dir aber helfen, dorthin zu gelangen.

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