read-Int implementation

[Bertram Felgenhauer]

Serge D. Mechveliani wrote:
> 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?

I believe your numbers simply were not large enough. I changed
strs n  to be

       strs n =  if n == 0 then [""]
                 else
                 [d : ds | ds <- strs (pred n), d <- digits]

(which changes the answer but avoids holding on to tons of memory)
and ran the program for m = powers of 2 up to 128:

  1 real    0m0.392s
  2 real    0m0.447s
  4 real    0m0.575s
  8 real    0m0.995s
 16 real    0m1.885s
 32 real    0m3.695s
 64 real    0m7.826s
128 real    0m17.344s

(best run out of 9 each time)

This looks super-linear already; in the end it should be quadratic.

Bertram