Algorithms: design and analysis I, exercise1 (week1)

exercise01.hs

{-# LANGUAGE UnicodeSyntax #-}
import Control.Applicative ((<$>))

import Inversions

inputFile ∷ FilePath
inputFile = "IntegerArray.txt"

main ∷ IO ()
main = print =<< inversions <$> map (read ∷ String → Int) <$> lines <$> readFile inputFile

Inversions.hs

{-# LANGUAGE UnicodeSyntax #-}
module Inversions (inversions) where

inversions ∷ Ord α ⇒ [α] → Int
inversions = fst . inversions'
  where
    inversions' list@(_:_:_) = (leftInvs + rightInvs + splitInvs, sortedList)
      where (leftInvs, leftSortedList) = inversions' leftList
            (rightInvs, rightSortedList) = inversions' rightList
            (splitInvs, sortedList) = mergeInvs leftSortedList rightSortedList
            (leftList,rightList) = splitAt ((`div` 2) $ length list) list
    inversions' list = (0, list)

mergeInvs ∷ Ord α ⇒ [α] → [α] → (Int,[α])
mergeInvs = mergeInvs' 0
  where mergeInvs' i a [] = (i, a)
        mergeInvs' i [] a = (i, a)
        mergeInvs' i (x:xs) ylist@(y:_) | x < y = (i + invs, x : invList)
          where (invs, invList) = mergeInvs' 0 xs ylist
        mergeInvs' i xlist (y:ys) = (i + invs + length xlist, y : invList)
          where (invs, invList) = mergeInvs' 0 xlist ys