{-# LANGUAGE ScopedTypeVariables, TemplateHaskell #-}

module Main where

--------------------------------------------------------------------------

-- imports

import Test.QuickCheck

import Data.List

  ( sort

  )

--------------------------------------------------------------------------

-- merge sort

msort :: Ord a => [a] -> [a]

msort xs = merging [ [x] | x <- xs ]

merging :: Ord a => [[a]] -> [a]

merging []   = []

merging [xs] = xs

merging xss  = merging (sweep xss)

sweep :: Ord a => [[a]] -> [[a]]

sweep []          = []

sweep [xs]        = [xs]

sweep (xs:ys:xss) = merge xs ys : sweep xss

merge :: Ord a => [a] -> [a] -> [a]

merge xs     []     = xs

merge []     ys     = ys

merge (x:xs) (y:ys)

  | x <= y          = x : merge xs (y:ys)

  | otherwise       = y : merge (x:xs) ys

--------------------------------------------------------------------------

-- example properties

ordered :: Ord a => [a] -> Bool

ordered []       = True

ordered [x]      = True

ordered (x:y:xs) = x <= y && ordered (y:xs)

prop_Merge xs (ys :: [Int]) =

  ordered xs && ordered ys ==>

    collect (length xs + length ys) $

    ordered (xs `merge` ys)

--  collect (sort [length xs, length ys]) $

--------------------------------------------------------------------------

-- quantificiation

--prop_Merge (Ordered xs) (Ordered (ys :: [Int])) =

--  ordered (xs `merge` ys)

--  classify (length xs `min` length ys >= 5) "not trivial" $

--  cover (length xs `min` length ys >= 5) 70 "not trivial" $

{-

  shrink (Ordered xs) =

    [ Ordered xs'

    | xs' <- shrink xs

    , ordered xs'

    ]

-}

--------------------------------------------------------------------------

-- merging

prop_Merging (xss :: [OrderedList Int]) =

  ordered (merging [ xs | Ordered xs <- xss ])

--  mapSize (`div` 2) $ \(xss :: [OrderedList Int]) ->

return []

main = $quickCheckAll

--------------------------------------------------------------------------

-- the end.