Hi, I'm just started to learn Haskell. Coming from a programming contest background (where it is important to be able to solve problems in a small amount of code) I'm wondering what the best way is for simple IO. A typical input file (in a programming contest) is just a bunch of numbers which you want to read one by one (sometimes interspersed with strings). In C/C++ this is easily done with either scanf or cin which reads data separated by spaces. In Haskell I have not found an equally satisfactionary method. The methods I know of 1) Stay in the IO monad and write your own readInt readString functions. A lot of code for something easy. 2) Use interact together with words and put the list of lexemes in a State monad and define getInt where at least you can use read. 3) Use ByteString.Char8 which has readInt (but I couldn't find a readString). But one has to put it also in a State monad. I think that there must be standard function that can do this. What do experienced Haskellers use? Thanks in advance
G.C.Stavenga:
Hi, I'm just started to learn Haskell. Coming from a programming contest background (where it is important to be able to solve problems in a small amount of code) I'm wondering what the best way is for simple IO.
A typical input file (in a programming contest) is just a bunch of numbers which you want to read one by one (sometimes interspersed with strings). In C/C++ this is easily done with either scanf or cin which reads data separated by spaces. In Haskell I have not found an equally satisfactionary method. The methods I know of
1) Stay in the IO monad and write your own readInt readString functions. A lot of code for something easy.
2) Use interact together with words and put the list of lexemes in a State monad and define getInt where at least you can use read.
3) Use ByteString.Char8 which has readInt (but I couldn't find a readString). But one has to put it also in a State monad.
I think that there must be standard function that can do this. What do experienced Haskellers use?
map read . lines
Don Stewart-2 wrote:
G.C.Stavenga:
Hi, I'm just started to learn Haskell. Coming from a programming contest background (where it is important to be able to solve problems in a small amount of code) I'm wondering what the best way is for simple IO.
A typical input file (in a programming contest) is just a bunch of numbers which you want to read one by one (sometimes interspersed with strings). In C/C++ this is easily done with either scanf or cin which reads data separated by spaces. In Haskell I have not found an equally satisfactionary method. The methods I know of
1) Stay in the IO monad and write your own readInt readString functions. A lot of code for something easy.
2) Use interact together with words and put the list of lexemes in a State monad and define getInt where at least you can use read.
3) Use ByteString.Char8 which has readInt (but I couldn't find a readString). But one has to put it also in a State monad.
I think that there must be standard function that can do this. What do experienced Haskellers use?
map read . lines
Thank you for the reply. But this only works for if you read only integers all on different lines. But in general you have a structure like
first line -- integer specifying the number of testcases (n) Then for each testcase a line with an integer specifying the number of edges (e) a line with e pairs of string s and int p where p is the number asociated with string s, etc.
Such a structure cannot be parsed by map read.lines What I used is "words" to tokenize and put the list in a State monad with readInt, readString, etc. functions, to mimic C code. This seems to be a lot of overkill, so there must be an simpler way _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- View this message in context: http://www.nabble.com/%28no-subject%29-tp25088427p25088830.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Sat, Aug 22, 2009 at 01:23, staafmeister
But in general you have a structure like
first line -- integer specifying the number of testcases (n) Then for each testcase a line with an integer specifying the number of edges (e) a line with e pairs of string s and int p where p is the number asociated with string s, etc.
Such a structure cannot be parsed by map read.lines What I used is "words" to tokenize and put the list in a State monad with readInt, readString, etc. functions, to mimic C code. This seems to be a lot of overkill, so there must be an simpler way
Although you most certainly can use a State monad, in most problems this isn't necessary. Most algorithms that you need to solve programming contest problems can be written in a purely functional style, so you can limit monadic code to just a few helper functions. For example, this reads input in the style you mention (assuming the strings don't contain whitespace):
import Control.Monad
answer = id
parse [] = [] parse (s:p:r) = (s, (read p) :: Int) : parse r
run = getLine >> getLine >>= putStrLn . show . answer . parse . words
main = flip replicateM_ run =<< readLn
The answer function would be a pure function that computes the answer for a particular run. This main function is reusable for all problems with many runs. Observe that the number of edges (e), provided as a convenience for memory allocation in many other languages, is not even necessary in Haskell :) (If anyone knows a better way than explicit recursion to map over a list, two elements at a time, or zip its even elements with its odd elements, I'd love to hear! I can imagine a convoluted fold with a boolean in its state, but it's ugly.) Hope that helps, Thomas
Thank you for the reply. Thomas ten Cate wrote:
Although you most certainly can use a State monad, in most problems this isn't necessary. Most algorithms that you need to solve programming contest problems can be written in a purely functional style, so you can limit monadic code to just a few helper functions.
Yes I know but there are a lot of problems requiring O(1) array updates so then you are stuck with IO again Thomas ten Cate wrote:
For example, this reads input in the style you mention (assuming the strings don't contain whitespace):
import Control.Monad
answer = id
parse [] = [] parse (s:p:r) = (s, (read p) :: Int) : parse r
run = getLine >> getLine >>= putStrLn . show . answer . parse . words
main = flip replicateM_ run =<< readLn
The answer function would be a pure function that computes the answer for a particular run. This main function is reusable for all problems with many runs.
Observe that the number of edges (e), provided as a convenience for memory allocation in many other languages, is not even necessary in Haskell :)
Yes you're main is short. But how would you do it elegantly if instead of line breaks and spaces one would have only spaces. Every thing on one big line. My C code would not mind one bit. Thomas ten Cate wrote:
(If anyone knows a better way than explicit recursion to map over a list, two elements at a time, or zip its even elements with its odd elements, I'd love to hear! I can imagine a convoluted fold with a boolean in its state, but it's ugly.)
Yes I missed such a function in a couple of problems I wanted to solve. I would expect a generic function groupN::Int -> [a] -> [[a]] that groups a list into groups of N Best, Gerben -- View this message in context: http://www.nabble.com/%28no-subject%29-tp25088427p25094244.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Sat, Aug 22, 2009 at 3:20 PM, staafmeister
Thank you for the reply.
Thomas ten Cate wrote:
Although you most certainly can use a State monad, in most problems this isn't necessary. Most algorithms that you need to solve programming contest problems can be written in a purely functional style, so you can limit monadic code to just a few helper functions.
Yes I know but there are a lot of problems requiring O(1) array updates so then you are stuck with IO again
Not necessarily. The ST monad will usually do just as well. -- Sebastian Sylvan
staafmeister wrote:
Yes I know but there are a lot of problems requiring O(1) array updates so then you are stuck with IO again
Or use ST. Or use IntMap (which is O(log n), but n is going to max out on the integer size for your architecture, so it's really just O(32) or O(64), which is really just constant time). And, realistically, very few problems actually require indexed access on a large scale like this.
[parsing stuff]
As far as parsing is concerned, maybe you should look at Parsec. I know it sounds like overkill, but it's easy enough to use that it's quite lightweight in practice. Your example scenario: inputData :: Parser InputData inputData = many1 digit *> newline *> many (testCase <* newline) where testCase = many1 digit *> newline *> sepBy edge (char ' ') edge = liftA2 (,) (many nonspace <* char ' ') (read <$> digits) - Jake
Jake McArthur wrote:
staafmeister wrote:
Yes I know but there are a lot of problems requiring O(1) array updates so then you are stuck with IO again
Or use ST. Or use IntMap (which is O(log n), but n is going to max out on the integer size for your architecture, so it's really just O(32) or O(64), which is really just constant time).
Actually, IntMap is O(min(n,W)) where W is the number of bits in an Int. Yes, IntMaps are linear time in the worst case (until they become constant-time). In practice this is competitive with all those O(log n) structures though. Whereas Data.Map is O(log n) for the usual balanced tree approach. -- Live well, ~wren
There are also the judy arrays
http://hackage.haskell.org/package/HsJudy
http://hackage.haskell.org/package/judy
dons recently advertised the latter as being 2x faster than IntMap,
but I don't know in what respect these two packages differ and why Don
decided to create 'judy' despite the existence of HsJudy.
2009/10/15 wren ng thornton
Jake McArthur wrote:
staafmeister wrote:
Yes I know but there are a lot of problems requiring O(1) array updates so then you are stuck with IO again
Or use ST. Or use IntMap (which is O(log n), but n is going to max out on the integer size for your architecture, so it's really just O(32) or O(64), which is really just constant time).
Actually, IntMap is O(min(n,W)) where W is the number of bits in an Int. Yes, IntMaps are linear time in the worst case (until they become constant-time). In practice this is competitive with all those O(log n) structures though.
Whereas Data.Map is O(log n) for the usual balanced tree approach.
-- Live well, ~wren _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
-- Eugene Kirpichov Web IR developer, market.yandex.ru
At Thu, 15 Oct 2009 10:15:46 +0400, Eugene Kirpichov wrote:
but I don't know in what respect these two packages differ and why Don decided to create 'judy' despite the existence of HsJudy.
HsJudy doesn't compile against the latest judy library (as Don knew) - presumably he had a good reason to start a new package instead of patching the old one. There should be a way to mark packages as deprecated on hackage, and at the same time direct people to a more suitable alternative. Aside from uploading a dummy new version (ugh!), I don't see a way to do that currently. -- Robin
On Fri, Aug 21, 2009 at 11:42 PM, Stavenga, G.C.
Hi, I'm just started to learn Haskell. Coming from a programming contest background (where it is important to be able to solve problems in a small amount of code) I'm wondering what the best way is for simple IO.
A typical input file (in a programming contest) is just a bunch of numbers which you want to read one by one (sometimes interspersed with strings). In C/C++ this is easily done with either scanf or cin which reads data separated by spaces. In Haskell I have not found an equally satisfactionary method. The methods I know of
1) Stay in the IO monad and write your own readInt readString functions. A lot of code for something easy.
2) Use interact together with words and put the list of lexemes in a State monad and define getInt where at least you can use read.
3) Use ByteString.Char8 which has readInt (but I couldn't find a readString). But one has to put it also in a State monad.
I think that there must be standard function that can do this. What do experienced Haskellers use?
I usually just whip up a quick parser using Text.ParserCombinators.Parsechttp://www.haskell.org/ghc/docs/latest/html/libraries/parsec/Text-ParserComb... -- Sebastian Sylvan
On Fri, Aug 21, 2009 at 7:03 PM, Sebastian
Sylvan
I think that there must be standard function that can do this. What do experienced Haskellers use?
I usually just whip up a quick parser using Text.ParserCombinators.Parsec
I usually prefer ReadP for quick stuff, for an unknown reason. I guess it feels like there is less infrastructure to penetrate, it gives me the primitives and I structure the parser according to my needs. But yeah, I think parser combinators are the way to go. It's really not much work at all once you get the hang of it.
participants (10)
-
Don Stewart -
Eugene Kirpichov -
Jake McArthur -
Luke Palmer -
Robin Green -
Sebastian Sylvan -
staafmeister -
Stavenga, G.C.
-
Thomas ten Cate -
wren ng thornton