content: {-# LANGUAGE DeriveDataTypeable,TemplateHaskell #-}
  module MergeSort where
  
  import Prelude(Bool(..),undefined,return,Eq,Ord)
  import HipSpec.Prelude
  import Definitions
  import Test.QuickSpec.Signature
  import Test.QuickCheck.All
  
  -- Koen Style:
  {-# NOINLINE whenSorted #-}
  whenSorted :: NList -> NList
  whenSorted xs = if sorted xs then xs else NNil
  
  merge :: NList -> NList -> NList
  merge (NCons x xs)    (NCons y ys)   =
      if x <= y
          then NCons x (merge xs (NCons y ys))
          else NCons y (merge (NCons x xs) ys)
  merge xs@(NCons _ _)  NNil           = xs
  merge NNil            ys@(NCons _ _) = ys
  merge NNil            NNil           = NNil
  
  data Pair = Pair !NList !NList deriving (Eq,Typeable,Ord)
  
  instance Arbitrary Pair where
      arbitrary = do
          a <- arbitrary
          b <- arbitrary
          return (Pair a b)
  
  evens :: NList -> NList
  evens NNil = NNil
  evens (NCons x NNil) = NNil
  evens (NCons x (NCons y zs)) = NCons x (evens zs)
  
  odds :: NList -> NList
  odds NNil = NNil
  odds (NCons x NNil) = NCons x NNil
  odds (NCons x (NCons y zs)) = NCons y (odds zs)
  
  interleave :: NList -> NList -> NList
  interleave NNil         ys = ys
  interleave (NCons x xs) ys = NCons x (interleave ys xs)
  
  prop_interleave xs = interleave (evens xs) (odds xs) =:= xs
  
  msort :: NList -> NList
  msort NNil = NNil
  msort (NCons x NNil) = NCons x NNil
  msort xs@(NCons _ (NCons _ _)) = merge (msort (evens xs)) (msort (odds xs))
  
  prop_msort xs = whenSorted (msort xs) =:= msort xs
  prop_sorted xs = sorted (msort xs) =:= True
  
  prop_merge xs ys = sorted (merge (whenSorted xs) (whenSorted ys)) =:= True
  
  {-
  prop_elem_msort x xs = elem x xs =:= elem x (msort xs)
  prop_count_msort x xs = count x xs =:= count x (msort xs)
  -}
  
  main = $(quickCheckAll)
  
  