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@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