I have the following code:
inversions :: (Ord a) => [a] -> Int
inversions xs = snd $ countInv' (xs, length xs)
countInv' :: (Ord a) => ([a], Int) -> ([a], Int)
countInv' ([], _) = ([], 0)
countInv' ([x], _) = ([x], 0)
countInv' (xs, n) = (sorted, leftInv + splitInv + rightInv)
where
leftLen = n `div` 2
rightLen = n - leftLen
(left, right) = splitAt leftLen xs
(sortedLeft, leftInv) = countInv' (left, leftLen)
(sortedRight, rightInv) = countInv' (right, rightLen)
(sorted, splitInv) = countSplitInv' (sortedLeft, leftLen) (sortedRight, rightLen)
countSplitInv' :: (Ord a) => ([a], Int) -> ([a], Int) -> ([a], Int)
countSplitInv' ([], _) ([], _) = ([], 0)
countSplitInv' (xs, _) ([], _) = (xs, 0)
countSplitInv' ([], _) (xs, _) = (xs, 0)
countSplitInv' (x : xs, nx) (y : ys, ny)
| x > y = (y : sortedY, nx + splitInvY)
| otherwise = (x : sortedX, splitInvX)
where
(sortedX, splitInvX) = countSplitInv' (xs, pred nx) (y : ys, ny)
(sortedY, splitInvY) = countSplitInv' (x : xs, nx) (ys, pred ny)
main :: IO ()
main = do
contents <- getContents
print $ inversions (map read (lines contents) :: [Int])
How could I write this code in a way that is more idiomatic, reduces the amount of repetition, and reduces the amount of data being copied?
As a Haskell beginner, I would appreciate it if you give an indepth explanation of the code you write and try to keep your code as simple as possible.
