-- This file demonstrates debugging in Haskell. It is an implementation of merge
-- sort
--
--   http://en.wikipedia.org/wiki/Merge_sort
--
-- but the code is currently wrong. Can you use QuickCheck to find the errors?
--
-- Also enable the trace line in mergeSort (before fixing the errors) to see why
-- it doesn't terminate.

import Data.List
import Test.QuickCheck as Test
import Debug.Trace



-- halve as splits as into two roughly equal parts
halve :: [a] -> ([a],[a])
halve as = go (l `div` 2) as
  where
    l = length as

    go 0 as     = ([],as)
    go n (a:as) = (a:bs,a:cs)
      where
        (bs,cs) = go (n-1) as

prop_halve as = as == bs++cs
  where
    _       = as :: [Int]
    (bs,cs) = halve as

-- merge as bs merges as and bs into a single sorted list, given that as and bs
-- are sorted
merge :: Ord a => [a] -> [a] -> [a]
merge as     []     = as
merge []     bs     = bs
merge (a:as) (b:bs)
    | a < b     = a : merge as bs
    | otherwise = b : merge as bs

-- isSorted as checks that as is sorted
isSorted :: Ord a => [a] -> Bool
isSorted as = and [a <= b | (a,b) <- zip as (tail as)]

prop_merge1 as bs = isSorted (merge (sort as) (sort bs))
  where
    _ = as :: [Int]

prop_merge2 as bs = merge (sort as) (sort bs) == sort (as++bs)
  where
    _ = as :: [Int]

-- mergeSort
mergeSort :: Ord a => [a] -> [a]
-- mergeSort as | trace (show (length as)) False = undefined
mergeSort []  = []
mergeSort [a] = [a]
mergeSort as  = merge (mergeSort bs) (mergeSort cs)
  where
    (bs,cs) = halve as

prop_mergeSort as = mergeSort as == sort as
  where
    _ = as :: [Int]



-- trace can be used to print intermediate values during evaluation
testTrace1 = 4 + (trace "Someone needs 5" 5) + (trace "Someone needs 6" 6)
  -- The printed trace reveals GHCs evaluation order for +; however, note that
  -- the Haskell language does not specify the order, so the compiler is free to
  -- use any order.

testTrace2
    | trace "Someone needs 1==2" (1==2) = trace "Someone needs 4" 4
    | otherwise                         = trace "Someone needs 5" 5
  -- Note that 4 is never needed