I recently decided to learn Haskell by solving Code Chef problems. Unfortunately, the problem TSORT is proving to be quite a challenge (it should not, I think). As can be seen from the list of submissions, no one solved this problem with Haskell so far: Link This particular submission can sort a list of 10^6 integers randomly generated in 0.5seconds on my machine, but still failing the 5 seconds time limit on CodeChef. Any suggestions to solve this problem with Haskell? Thank you... asked 07 Feb '14, 05:22

Hello, First of all, I must say that you must be a really, really very versatile coder... Understanding I/O in Haskell, which implies understanding Monads (at least, the IO Monad) is actually one of the major difficulties I've came across while learning Haskell and it is, imho, one of the biggest challenges a programmer can face on a more theoretical vs. practical level... It is also the reason why I haven't used Haskell to solve codechef problems... (I'm also learning Haskell and am still a newbie) With that being said, have you read stuff about Haskell's FFI? It might be your best shot here... if you can plug it in your code: Haskell's FFI and other I/O tricks More specifically, read point 8 on the link :) Best, Bruno EDIT: Can't you process input data in a way that you read it to a list and then output the whole sorted list at once? If you import Data.List and manage to process input into a list, say L, then it's simply a matter of doing: sort L and then to output something like: putStr (show (sort L)) or something alike... answered 07 Feb '14, 05:34
1
Thank you for the link. Lot's of things to learn there. I didn't worry much about IO because I managed to pass the INTEST problem with Haskell.
(07 Feb '14, 06:08)
Maybe we can learn Haskell together? :) Yes, Haskell wiki is a great place :D And I still need to attempt INTEST myself :D
(07 Feb '14, 06:25)
@kuruma Haskell is very fun to learn, unfortunately I don't think it is suited for CodeChef :( Not until I find an elegant solution for this problem, something that don't force me to use C inside Haskell.
(07 Feb '14, 23:00)

This is a great example of how to code and what to optimize. There are many programmers here better than me, but I’ve figured out some tips and tricks about optimizing Haskell for the problems in the past month, and my solutions are pretty consistently twice as fast as the other Haskell submissions. This isn’t how you do that; it’s a simplified example. But I’ll be getting to it. I won’t need to bring up monads again (although there’s no need to be afraid of them). There’s a really handy function that pretty much solves the problem of console I/O for you. It’s called Here’s a really idealized walkthrough of how you might solve the problem naïvely. Haskell has the really useful feature that, if you write Let’s start with a basic skeleton. We want to read in a list of numbers as
If we try to compile this in ghc, we get three error messages, one per hole, about how the compiler
The first thing we need to do is split the input into lines and ignore the first line. (One thing you’ll often find yourself doing for contests that’s a bad habit in the real world is skipping input validation.) So we want to look for a function of type
Now we get some useful error messages:
GHC tells us what the type signature of the function we need is. It even gives us a list of the relevant local variables. That doesn’t help us at the moment, but it is usually the list of building blocks we have to fill a typed hole with. So we need a function of type
Now GHC tells us that the first hole has type
Now we just need a function to sort a list of type
You’ll want to have at least two testcases for every problem saved as text files, one that’s short and simple, and one that’s the maximum size, contains every boundary case, and as hard as possible. However, this will be much too slow to be accepted. Better solutions to come. answered 14 Nov, 22:43

@hase @kuruma...are u sure u need to sort the numbers in TSORT??? cant u try using this algo...http://www.codechef.com/viewsolution/2541169 answered 18 Mar '14, 07:50

Hi, I am new to Haskell as well and I am stock in this problem as well :) here is my solution, which runs in like 1 sec which is obviously way under 5 sec but I get a TLE.
I will keep trying some other things but I don't know what is the bottle neck here. So is going to be difficult. answered 20 Mar '14, 10:42

Since these replies are listed as answers, not in the order they were posted, this is a followup to my previous answer. Haskell is a fast language. I’ve gotten performance not far behind C or C++ when running the same algorithms on the same data structures. In every case I’ve found where an optimized Haskell solution wasn’t fast enough, the problem was with the algorithm or data structure I was using, and if you’re more than slightly behind, there’s a better approach that will get you the answer with a lower order of time complexity. In the most pathological case, a mutable The lesson there, for me, was not to prematurly optimize so much. I spent a lot of time getting the mutable arrays in the ST monad right, and I learned something from it, but the real solution was to use a different data structure, segment trees. You will, however, have to start with one optimization: fast I/O. The first snag you’re going to run into, on every single problem, is that the standard Haskell I/O library is extremely slow. Why is that? Remember, I said Haskell is fast when using the same data structures as other languages. The I/O library in The efficient data structure for output is arrays of characters, and ASCII is enough for (nearly?) any problem on this site. An even better one for this purpose is a list of buffers, dynamically allocated as needed. That exists in Haskell, as An equivalent skeleton with fast I/O might be:
And it says a lot about Haskell that the operations to combine the optimized, lowlevel data structures from I/O are found in the typeclasses It turns out that Both updating an array and iterating through an array in Haskell are concepts from imperative languages, and we’ll use library functions to get out of having to do them. If you check the documentation for
The first hole is now a function from
For the first remaining hole, each time we encounter an
I submitted a few different variants of it, for benchmarking. Subtle differences can have a big impact on performance, and since Haskell is such a highlevel language, it’s often opaque which ones. (It took me a while to figure out that You’ll notice that it’s possible to pass flags to GHC inside the source code. I haven’t found that answered 15 Nov, 01:11
