Things that make you go "Hmmm..."

OK. I rolled my own main, with serious help from "Haskell I/O for Imperative Programmers"--and I hasten to add that if you, like me, are learning Haskell, run, do not walk, to this page and read it.

Doing I/O, at least of the sort that programs like this do, in Haskell requires an attitude adjustment if you want to work with Haskell rather than against it. If you're a shell scripter, you already have the idea: you've worked with pipes. Pipes are like function composition; see
So, here's my main. I toyed with using interact, but having to skip the first line (the one that tells you how many lines are left) made it problematic, as well as the issue of adding a "case number" for getting the output in the form that the problem statement requires.

-- A new main, heavily inspired by "Haskell I/O for Imperative Programmers"
-- (What's with that tail, you ask? We're skipping that first line that says
-- how many more lines there are.
They could have been persnickety and padded
-- the file with additional lines to make sure you have to pay attention to
-- that first line, but they weren't.

main = do
    s <- getContents
    let r = map format $ zip [1..] (map process (tail $ lines s))
    putStr (unlines r)

process :: String -> Int

process line = let [m, n] = map read (words line)
               in  numXs m n

format :: (Int, Int) -> String

format (lineNum, result) = "Case #" ++ show lineNum ++ ": " ++ show result

So, it compiled, it ran, it gave the same results as before. What about the time and the cost centers? The time seems to be a little bit slower, though there's some overlap between it and the previous version. This version seems to take somewhere between 0.38 and 0.4 seconds. This despite the following profiler output:

COST CENTRE            MODULE                %time %alloc

process.(...)          Main                   35.9   41.7
nDigitYs               Main                   11.1    8.4
tenToThe               Main                    8.1    0.0
fromList.(...)         SemilatticeSearchTree   7.6    8.9
digitsIn.digitsIn'     Main                    5.5    3.9
justOnes.pair          Main                    5.1    3.0
main.r                 Main                    4.1    6.0
justOnes               Main                    3.9    6.2
main                   Main                    3.2    9.5
fromList               SemilatticeSearchTree   1.8    0.2
floorSqrt.floorSqrt'.y Main                    1.4    1.8
meet                   SemilatticeSearchTree   1.4    0.0
choose                 Main                    1.2    1.0
choices                Main                    1.2    2.8
mkBranch               SemilatticeSearchTree   0.7    1.0
yTree                  Main                    0.2    1.4
meet                   SemilatticeSearchTree   0.2    1.1

Note that process only chews up 35.9% of the time, 41.7% of the allocation, compared with 39.5% and 56.0% respectively for solve under the former regime. main and its immediate helpers are all that changed. How could execution time increase if the only part that changed decreased the percentage of execution time it took? It is, as someone once said, a puzzlement. I think I like this main, though, and will see if there's anything I can do to improve it.

UPDATE: Aha! Note that we've added a couple of cost centers: main.r and main. They collectively add up to 43.2% of time and 57.2% of allocation. That's how the result can take longer despite the distribution being flatter.


Popular posts from this blog

a longest path problem

No tutorial, I swear...

Bikeshedding leap years