read-Int implementation

Niklas Larsson metaniklas at gmail.com
Sun Feb 12 14:35:44 CET 2012


You can see the source code for Read and its basic instances at
http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Read.html#Read

Search for readNumber to find the instances that parses numbers.
Nothing very much magical happens, lexP reads in a token (using
Text.Parsercombinators.readP_to_S and the small lexer in
Text.Read.Lex(http://hackage.haskell.org/packages/archive/base/latest/doc/html/Text-Read-Lex.html,
click on the source link to see source)). If that token is a number of
the kind we were looking for (convertInt accepts only integers,
convertFrac can handle fractional and integer), return it, otherwise
fail.

Hoogle is a great resource for exploring the libraries . It's at
http://www.haskell.org/hoogle/ . That and the source links in the
documentation makes it easy to follow what happens all the way down.

-- Niklas

Den 12 februari 2012 13:50 skrev Serge D. Mechveliani <mechvel at botik.ru>:
> Who can tell, please, how     read string :: Integer
> is implemented in ghc-7.4.1 ?
> Is it linked from the GMP (Gnu Multi-Precision) library?
>
> It is suspiciosely fast :-)
> In my test on 10^5 strings of length  l = 5, 20  it shows the cost order
> in  l  less than  1,  as if it was   O(log(l)), or O(squareRoot(l).
>
> This is even despite that the very forming of the string list by  concat
> and by   take l0Exp (strs l)  seems to have large overhead.
>
> The impression is that I am missing something.
>
> Regards,
>
> ------
> Sergei
> mechvel at botik.ru
>
>
>
> -------------------------------------------------------------------------
> main = putStr (shows resSum "\n")
>       where
>       m = 1  :: Int     -- edit this multiplicity:  1, 4 ...
>
>       digits = (if m == 1 then  id  else  reverse)
>                                                 ['0' .. '9']  :: [Char]
>       l0    = 5  :: Int       -- first length
>       l0Exp = (10 :: Int)^l0
>       l     = l0 * m          -- second length
>
>       strs :: Int -> [String]          -- all digit strings of length n
>       strs n =  if n == 0 then [""]
>                 else
>                 concat [map (d :) (strs (pred n)) | d <- digits]
>
>       strings = strs l
>       segm    = if m == 1 then  strings
>                 else            take l0Exp strings
>                                         -- length segm  is always 10^l0
>
>       resSum = sum [read str :: Integer | str <- segm]
>
>       -- testPairs = [(str, read str :: Int) | str <- strings]
>       -- correctness testing
> ------------------------------------------------------------------------
>
>  > ghc -O2 --make Main
>  > time ./Main
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users



More information about the Glasgow-haskell-users mailing list