blob: 8f2a7c84fb39d009199ae88f7f415077bf5603fe (
plain)
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
|
module AufgabeFFP7
where
import Data.Char
import Data.List hiding ((\\))
import Test.QuickCheck
type Buffer = (Int, String)
-- the empty buffer
--TODO empty :: Buffer
-- insert character before cursor
--TODO insert :: Char -> Buffer -> Buffer
-- delete character before cursor
--TODO delete :: Buffer -> Buffer
-- move cursor left one character
--TODO left :: Buffer -> Buffer
-- move cursor right one character
--TODO right :: Buffer -> Buffer
-- is cursor at left end?
--TODO atLeft :: Buffer -> Bool
-- is cursor at right end?
--TODO atRight :: Buffer -> Bool
--------------------------------------------------------------------------------
type BufferI = (String, String)
-- the empty buffer
--TODO emptyI :: BufferI
-- insert character before cursor
--TODO insertI :: Char -> BufferI -> BufferI
-- delete character before cursor
--TODO deleteI :: BufferI -> BufferI
-- move cursor left one character
--TODO leftI :: BufferI -> BufferI
-- move cursor right one character
--TODO rightI :: BufferI -> BufferI
-- is cursor at left end?
--TODO atLeftI :: BufferI -> Bool
-- is cursor at right end?
--TODO atRightI :: BufferI -> Bool
--------------------------------------------------------------------------------
--TODO retrieve :: BufferI -> Buffer
--------------------------------------------------------------------------------
--TODO: quicheck stuff
--------------------------------------------------------------------------------
-- from slide 154
divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s
divideAndConquer indiv solve divide combine initPb = dAC initPb
where
dAC pb
| indiv pb = solve pb
| otherwise = combine pb (map dAC (divide pb))
-- from slide 156
quickSort :: Ord a => [a] -> [a]
quickSort lst = divideAndConquer indiv solve divide combine lst
where
indiv ls = length ls <= 1
solve = id
divide (l:ls) = [[ x | x <- ls, x <= l], [ x | x <- ls, x > l] ]
combine (l:_) [l1,l2] = l1 ++ [l] ++ l2
removeDuplicates :: [Int] -> [Int]
removeDuplicates xs = nub xs
-- from slide 245
ssfn :: [Int] -> Int
ssfn xs = sap 0 (removeDuplicates (quickSort xs))
sap :: Int -> [Int] -> Int
sap n [] = n
sap n (x:xs)
| n /= x = n
| otherwise = sap (n + 1) xs
-- from slide 247
(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ ys = filter (\x -> x `notElem` ys) xs
minfree :: [Int] -> Int
minfree xs = head ([0..] \\ xs)
--------------------------------------------------------------------------------
type Nat = [Int]
prop_ssfn_eq_minfree_a :: Nat -> Bool
prop_ssfn_eq_minfree_a xs = minfree pos == ssfn pos
where
pos = filter (>= 0) xs
prop_ssfn_eq_minfree_b :: Nat -> Property
prop_ssfn_eq_minfree_b xs = filter (< 0) xs == []
==> ssfn xs == minfree xs
|
