Haskell: f :: hex String -> Intero che utilizza la ricorsione della coda

Question

Sto cercando un modo per cambiare hex in un intero utilizzando la ricorsione della coda. Fino ad ora ho provato solo implementazioni terribili della normale ricorsione primitiva e non mi sono nemmeno avvicinato. Molto frustrato. Anche gli esempi di ricorsione della coda aiuteranno e saranno molto apprezzati. Non lo capisco abbastanza bene per questa implementazione.

Esempio:

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

Limitazioni: Non può utilizzare l'importazione o se, poi, il resto ecc, deve essere fatto con la ricorsione, se possibile, o la coda ricorsione.

Il mio tentativo di ricorsione.

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

Generalmente, per funzioni ricorsiva in coda, è necessario un argomento accumulatore - con purezza, il risultato potrebbe altrimenti dipendere solo il caso base raggiunto. Così si avrebbe bisogno di una funzione di supporto tenendo anche un argomento di accumulo, e chiamare che, con un valore iniziale per l'accumulatore,

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

e si deve scoprire

• che valore iniziale si dovrebbe passare per la accumulatore
• come l'accumulatore deve essere aggiornato in ogni passaggio.

Ad esempio, un'implementazione ricorsiva in coda di reverse è

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

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

e fattoriale ricorsiva in coda (fudging caso di un argomento negativo)

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

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

Così si può vedere la struttura generale di hexToIntegerHelper,

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

e la domanda è come deve essere calcolato il nuovo accumulatore da quello vecchio e la cifra esadecimale (e quale dovrebbe essere l'accumulatore iniziale).

Per l'aggiornamento dell'accumulatore,

digitToInt :: Char -> Int 

da Data.Char potrebbe essere utile, che gestisce tutte le cifre esadecimali. Tuttavia, non restituisce il tipo desiderato, pertanto è necessario utilizzare uno fromIntegral o uno toInteger per convertire lo Int in Integer.

Answer 2

Qui ci sono due funzioni ricorsive, anche se mi è stato fatto notare che non sono ricorsive in coda. Forse possono aiutarti ad arrivare lì, però.

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