[Haskell-cafe] Reading integers
bertram.felgenhauer at googlemail.com
Wed Sep 6 17:35:10 EDT 2006
prompted by a discussion about http://www.spoj.pl/problems/MUL/ on
#haskell I implemented some faster routines for reading integers,
and managed to produce a program that passes this problem.
Currently I have a single module that provides reading operations
for Integers and Ints. I'm not quite sure what to do with it.
Ideally, read should use faster code for parsing numbers. This is hard
to do though, because read for numbers is specified in terms of lex,
which handles arbitrary tokens. One nasty side effect of this, besides
bad performance, is that for example
read ('"':reapeat 'a') :: Int
diverges, even though there's obviously no possible parse. Incorporating
faster integer reading code into read without breaking backward
compatibility is not trivial.
The next obvious place to put the functions is the Numeric module.
This sounds like a good idea until one realizes that readSigned (which
is the obvious thing to use for signed integers) again uses lex, with
all the complications above.
A third option is to put it all in a separate module. This would
probably be hard to find, so few people would use it.
I'm pondering breaking compatibility with Haskell 98 to some extent
and implementing read instances for Int and Integer that don't diverge
on weird inputs, but handle all valid numbers that Haskell 98 supports.
This still requires some work to support octal and hexadecimal numbers,
whitespace and parentheses.
What do you think?
The code (quite unpolished) is available with
darcs get http://int-e.home.tlink.de/haskell/readinteger
(browsing directly doesn't work)
It also includes a simple benchmark for comparing reads, Numeric.readDec
and my readInteger functions. Results for my computer are included as
More information about the Haskell-Cafe