read-Int implementation

Serge D. Mechveliani mechvel at botik.ru
Sun Feb 12 13:50:12 CET 2012


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



More information about the Glasgow-haskell-users mailing list