Inversions.elm

module Inversions (countInversions, mergeAndCount) where

import List.Extra exposing (splitAt)
import List exposing (length, sort, foldl, concat, head)
import Maybe.Extra exposing (isNothing, map2)


mergeAndCount : List Int -> List Int -> ( List Int, Int )
mergeAndCount left right =
    let
        ( _, lRest ) = splitAt 1 left

        ( _, rRest ) = splitAt 1 right

        dataForNextIteration lHead rHead =
            if lHead < rHead then
                let
                    ( merged, count ) = mergeAndCount lRest right
                in
                    ( concat [ [ lHead ], merged ], count )
            else
                let
                    ( merged, count ) = mergeAndCount left rRest
                in
                    ( concat [ [ rHead ], merged ], count + (length left) )

        maybeData = map2 dataForNextIteration (head left) (head right)
    in
        case maybeData of
            Just data ->
                data

            Nothing ->
                ( concat [ left, right ], 0 )



body : List Int -> (List Int, Int)
body nums =
    let
        (left, right) = splitAt ((length nums) //  2) nums
    in
        if (length nums) <= 1 then
            (nums, 0)
        else
            let
                (sortedLeft, leftInversions) = body left
                (sortedRight, rightInversions) = body right
                (merged, crossInversions) = mergeAndCount sortedLeft sortedRight
            in
                (merged, leftInversions + rightInversions + crossInversions)


countInversions : List Int -> Int
countInversions nums =
    snd (body nums)

Tests.elm

module Tests (..) where

import ElmTest exposing (..)
import Inversions exposing (countInversions, mergeAndCount)
import String


sortedListTest =
    test
        "Finds 0 inversions in a sorted list"
        (assertEqual 0 (countInversions [ 1, 2, 3, 4 ]))


singleInversionTest =
    test
        "Finds 1 inversion in a list"
        (assertEqual 1 (countInversions [ 2, 1, 3, 4 ]))


mergeAndCountTest =
    suite
        "Merge and count tests"
        [ test
            "Merges simple ordered lists"
            (assertEqual ([0, 1], 0) (mergeAndCount [0] [1]))
        , test
            "Handles empty left"
            (assertEqual ([1], 0) (mergeAndCount [] [1]))
        , test
            "Handles empty right"
            (assertEqual ([0], 0) (mergeAndCount [0] []))
        , test
            "Identifies an inversion"
            (assertEqual ([0, 1], 1) (mergeAndCount [1] [0]))
        , test
            "Identifies multiple inversions"
            (assertEqual ([0, 1, 2, 3], 2) (mergeAndCount [1, 2] [0, 3]))
        ]

all : Test
all =
    suite
        "The Inversion counter"
        [ sortedListTest
        , singleInversionTest
        , mergeAndCountTest
        ]