From: 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
Depending on the problem, you may be able to find a better data type than an array. Of course, since we're discussing generalities it's hard to make any specific recommendations.
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.
If I read it properly, this code won't either. The "words" function at the end of the pipeline will split tokens on any whitespace.
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
I often use this function as well. I think it's not in the libraries because it's so simple to define: groupN :: Int -> [a] -> [[a]] groupN n [] = [] groupN n xs = let (h,t) = splitAt n xs in h:groupN n t Or, for a nonrecursive version: groupN2 = fix g where g f n [] = [] g f n xs = let (h,t) = splitAt n xs in h: f n t but that's probably not what you had in mind. I've found that using unfoldr is simpler than fold if you wish to use HOFs to accomplish this, but neither is as simple as explicit recursion. John Lato