Umwandlung von Integer in die Liste stellen, ohne 'mod' und 'div'

Momentan habe ich die Haskell-Funktion wandelt eine ganze Zahl in eine Liste von Ziffern genommen von der ursprünglichen ganzen Zahl. Meine Frage ist also: gibt es eine Möglichkeit, dies zu tun, ohne mit mod und div? Zum Beispiel, wenn ich wollte, das gleiche zu tun, nur mit einem string könnte ich eine Funktion erstellen, die Nutzung anderer Funktionen, wie Kopf und Schwanz usw.

Ich kämpfte mit diesem problem für eine Weile, bevor Sie schließlich kommen, um SO und finden die Antwort in einem anderen post. Was hat mich diese Frage ist die Tatsache, dass ich hätte nie daran gedacht, mit mod und div mich!

toDigits :: Integer -> [Integer]
toDigits n 
 | n < 1 = []
 | otherwise = toDigits (n `div` 10) ++ [n `mod` 10]
InformationsquelleAutor Dave0504 | 2014-06-21
  1. 8

    Sie erwähnt, dass Sie das gleiche tun könnte auf strings mit einer Liste von Operationen. In der Tat, das wäre eine andere Art und Weise. Sie könnte konvertieren von integer in string umwandeln und dann jedes Zeichen in eine Ganzzahl:

    import Data.Char (digitToInt)

toDigits :: Int -> [Int]
toDigits = map digitToInt . show

    Hier habe ich Int eher als Integer, aber Sie können Integer wenn Sie wirklich wollen, mit ein wenig mehr Mühe:

    toDigits :: Integer -> [Integer]
toDigits = map (fromIntegral . digitToInt) . show
    InformationsquelleAutor icktoofay
  2. 2

    @icktoofay Antwort verwendet show, eine generische Art und Weise zu konvertieren einen Wert zu einem String (in anderen Worten, seine string-Darstellung). Ein Wert sollte von einem Typ, der eine Instanz einer typeclass Show. Zum Beispiel Int ist eine Instanz von Show (geben Sie :i Int im ghci und suchen nach einer Zeichenfolge instance Show Int -- Defined in `GHC.Show'). Aber eine Funktion ist nicht eine Instanz von Show, so let f n = n in f wirft einen Fehler, denn wie würde Sie konvertieren eine Funktion, um einen string? (Siehe auch: Wenn Funktionen als Instanzen der Show typeclass). Wie auch immer, mit show Funktion ist idiomatischer, so können Sie sich auch daran halten.

    Es ist jedoch ein Verfahren zum extrahieren einer Ziffer aus einer Zahl mithilfe von Logarithmen, Potenzen und integer-Divisionen. Denken Sie daran, dass Sie können entfernen Sie die Ziffern aus der linken von der Suche nach einem Rest, und entfernen Sie die Ziffern von rechts durch integer-division. In beiden Fällen, der Rechte operand ist einige Kraft der 10. Zum Beispiel:

    *Main> 123 `mod` 10
3
*Main> 123 `div` 100
1

    Aber wie wollen Sie wissen, welche Potenz von 10, die Sie verwenden sollten, durch die geteilt werden? Von der Suche nach einem Logarithmus zur Basis 10: #Ziffern von N = log10N + 1, z.B. log1012345 = 4. Leider können Sie nicht verwenden,logBase, weil es verwendet floating-point-Arithmetik, die ungenau. Zum Beispiel:

    *Main> logBase 10 1000
2.9999999999999996

    Können Sie benutzerdefinierte Funktion iLogBase für Ganzzahlen kopieren Sie den code aus dem link in Ihren Quellcode. Auf diese Weise finden Sie eine erste Ziffer einer Zahl, die ich den folgenden code verwenden:

    firstDigit :: (Integral a) => a -> a
firstDigit n = n `div` (10^log)
  where log = fst $ iLogBase 10 n

    Erstellen eine mehr Allgemeine Funktion bei der Suche nach einer beliebigen Ziffer der einen Zahl und der Umwandlung einer Zahl in eine Liste von Ziffern ist Links, um Sie als übung :).

    Darüber hinaus ist der code in deiner Frage ist ineffizient. Liste Verkettung (++) operation hat die Komplexität der O(n), das heißt, jedes mal, wenn Sie wollen, um ein element anzuhängen und am Ende der Liste, es hat der linken Liste in die Rechte Liste, bis Sie die resultierende Liste. Überprüfen Sie heraus die Quelle für (++) im Grunde [1,2,3] ++ [4] wird 1 : 2 : 3 : [4], das ist furchtbar ineffizient, da dauert es 3 Nachteile (:) Operationen zum hinzufügen einer Liste. Und als Sie Anhängen von zahlen an das Ende mehrmals, es zu wiederholen Sie den gleichen Vorgang jedes mal, also insgesamt die Komplexität der Funktion ist O(n^2).

    Auf der anderen Seite (:) ist instant, das heißt, hat die Komplexität der O(1). Egal wie lange ist Ihre Liste voranstellen eines Elements am Anfang ist Billig. Also anstatt das hinzufügen eines Elements zu Ende ist, würde ich empfehlen, indem es um den Anfang und das Ende einfach nur die Umkehrung der Liste wieder (für Informationen, die Lisp-Leute nennen diese push/nreverse idiom):

    reverse $ (n `mod` 10) : toDigits (n `div` 10)
    InformationsquelleAutor Mirzhan Irkegulov
Schreibe einen Kommentar