1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
{-# 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.
|
