Counting inversions Haskell.

inversions.hs

import Control.Monad

inversions :: [Int] -> Int
inversions = snd . countInversions

countInversions :: [Int] -> ([Int], Int)
countInversions []  = ([] , 0)
countInversions [x] = ([x], 0)
countInversions arr = let mid   = (length arr) `div` 2
                          left  = take mid arr
                          right = drop mid arr
                          (left'  , l) = countInversions $! left
                          (right' , r) = countInversions $! right
                          (whole  , w) = id $! countSplit left' right'
                      in (whole, l + r + w)

countSplit :: [Int] -> [Int] -> ([Int], Int)
countSplit [] y = (y, 0)
countSplit x [] = (x, 0)
countSplit (x:xs) (y:ys)
        | x <= y    = ((x: left ), 0 + l)
        | otherwise = ((y: right), 0 + r)
            where leftSplit  = countSplit xs (y:ys)
                  rightSplit = countSplit (x:xs) ys
                  left  = fst leftSplit
                  right = fst rightSplit
                  l     = snd leftSplit
                  r     = (snd rightSplit) + length((x: xs))

main = do
    nums <- liftM (map (read :: String -> Int) . lines) getContents
    print $ inversions nums

left  = take mid arr
right = drop mid arr

can be done in half the time with Data.List.splitAt. But it can be done in O(1) with Data.Vector.Generic.splitAt if you use Vector instead of [].

Curiosity: why 0 + ...?

I was being sloppy. Let me add the formatted code.