[Haskell-cafe] (no subject)

[Thomas ten Cate]

On Sat, Aug 22, 2009 at 01:23, staafmeister<g.c.stavenga at uu.nl> wrote:
> 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