forked from NigelNewby/cis5520-classes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
MonoidFoldable.hs
230 lines (177 loc) · 6.32 KB
/
MonoidFoldable.hs
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
{-
---
fulltitle: "In class exercise: Semigroup, Monoid and Foldable"
date:
---
-}
module MonoidFoldable where
import qualified Data.List as List
import Test.HUnit
import Prelude hiding (all, and, any, or)
{-
Monoids
-------
First, make sure that you have read the 'Semigroups and Monoids' section of HW 02's
[SortedList](../../../hw/hw02/SortedList.html) module.
Note that this section defines the following function that tailors a fold
operation to a specific instance of the `Monoid` class.
-}
foldList :: Monoid b => [b] -> b
foldList = List.foldr (<>) mempty
{-
For example, because the `String` type is an instance of this class
(using `++` for `mappend`) we can `foldList` a list of `String`s to
a single string.
-}
tm0 :: Test
tm0 = foldList ["C", "I", "S", "5", "5", "2"] ~?= "CIS552"
{-
The assignment shows you that numbers can instantiate this class in multiple
ways. Like numbers, `Booleans` can be made an instance of the `Monoid` class
in two different ways.
-}
newtype And = And {getAnd :: Bool} deriving (Eq, Show)
newtype Or = Or {getOr :: Bool} deriving (Eq, Show)
{-
Make sure that you understand these type definitions. We are defining a type
`And` with single data constructor (also called `And`). The argument of this
data constructor is a record with a single field, called `getAnd`. What this
means is that `And` and `getAnd` allow us to convert `Bool`s to `And` and
back.
λ> :t And
And :: Bool -> And
λ> :t getAnd
getAnd :: And -> Bool
Above, `newtype` is like data, but is restricted to a single variant. It is
typically used to create a new name for an existing type. This new name allows
us to have multiple instances for the same type (as below) or to provide type
abstraction (like `SortedList` in the HW).
Your job is to complete these instances that can tell us whether any of the
booleans in a list are true, or whether all of the booleans in a list are
true. (See two test cases below for an example of the behavior.)
-}
anyT1 :: Test
anyT1 = getOr (foldList (fmap Or [True, False, True])) ~?= True
allT2 :: Test
allT2 = getAnd (foldList (fmap And [True, False, True])) ~?= False
instance Semigroup And where
(<>) = undefined
instance Monoid And where
mempty = undefined
instance Semigroup Or where
(<>) = undefined
instance Monoid Or where
mempty = undefined
{-
Because `And` and `Or` wrap boolean values, we can be sure that our instances
have the right properties by testing the truth tables. (There are more
concise to write these tests, but we haven't covered them yet.)
-}
monoidAnd :: Test
monoidAnd =
TestList
[ And False <> (And False <> And False) ~?= (And False <> And False) <> And False,
And False <> (And False <> And True) ~?= (And False <> And False) <> And True,
And False <> (And True <> And False) ~?= (And False <> And True) <> And False,
And False <> (And True <> And True) ~?= (And False <> And True) <> And True,
And True <> (And False <> And False) ~?= (And True <> And False) <> And False,
And True <> (And False <> And True) ~?= (And True <> And False) <> And True,
And True <> (And True <> And False) ~?= (And True <> And True) <> And False,
And True <> (And True <> And True) ~?= (And True <> And True) <> And True,
And True <> mempty ~?= And True,
And False <> mempty ~?= And False,
mempty <> And True ~?= And True,
mempty <> And False ~?= And False
]
monoidOr :: Test
monoidOr =
TestList
[ Or False <> (Or False <> Or False) ~?= (Or False <> Or False) <> Or False,
Or False <> (Or False <> Or True) ~?= (Or False <> Or False) <> Or True,
Or False <> (Or True <> Or False) ~?= (Or False <> Or True) <> Or False,
Or False <> (Or True <> Or True) ~?= (Or False <> Or True) <> Or True,
Or True <> (Or False <> Or False) ~?= (Or True <> Or False) <> Or False,
Or True <> (Or False <> Or True) ~?= (Or True <> Or False) <> Or True,
Or True <> (Or True <> Or False) ~?= (Or True <> Or True) <> Or False,
Or True <> (Or True <> Or True) ~?= (Or True <> Or True) <> Or True,
Or True <> mempty ~?= Or True,
Or False <> mempty ~?= Or False,
mempty <> Or True ~?= Or True,
mempty <> Or False ~?= Or False
]
{-
Foldable
--------
Now, make sure that you have read the section marked `The Foldable Typeclass` in the
[MergeSort](../../../hw/hw02/MergeSort.html) module.
We can use your Monoid instances for `Or` and `And` to generalize
operations to any data structure.
For example, we can generalize the `and` operation to any Foldable data
structure using `foldMap`.
-}
and :: Foldable t => t Bool -> Bool
and = getAnd . foldMap And
{-
Your job is to define these three related operations
-}
or :: Foldable t => t Bool -> Bool
or = undefined
all :: Foldable t => (a -> Bool) -> t a -> Bool
all f = undefined
any :: Foldable t => (a -> Bool) -> t a -> Bool
any f = undefined
{-
so that the following tests pass
-}
tf0 :: Test
tf0 = or [True, False, False, True] ~?= True
tf1 :: Test
tf1 = all (> 0) [1 :: Int, 2, 4, 18] ~?= True
tf2 :: Test
tf2 = all (> 0) [1 :: Int, -2, 4, 18] ~?= False
tf3 :: Test
tf3 = any (> 0) [1 :: Int, 2, 4, 18] ~?= True
tf4 :: Test
tf4 = any (> 0) [-1 :: Int, -2, -4, -18] ~?= False
{-
Application
-----------
Recall our familiar `Tree` type. Haskell can derive the `Functor` instance for this type so we ask it to do so.
-}
data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Eq, Functor)
{-
And here is an example `Tree`.
-}
t1 :: Tree String
t1 = Branch "d" (Branch "b" (l "a") (l "c")) (Branch "f" (l "e") (l "g"))
where
l x = Branch x Empty Empty
{-
We *could* make this type an instance of `Foldable` using the definition of
`foldrTree` from the TreeFolds module.
But, for practice, complete the instance using `foldMap`.
-}
instance Foldable Tree where
foldMap = undefined
{-
With this instance, we can for example, verify that all of the sample strings
above have length 1.
-}
tt1 :: Test
tt1 = all ((== 1) . length) t1 ~?= True
{-
Finally, look at the documentation for the
[Foldable](https://hackage.haskell.org/package/base-4.15.1.0/docs/Data-Foldable.html)
class and find some other tree operations that we get automatically for
free.
-}
tt2 :: Test
tt2 = undefined
{-
Oblig-main
----------
-}
main :: IO ()
main = do
_ <- runTestTT $ TestList [tm0, anyT1, allT2, monoidAnd, monoidOr, tf0, tf1, tf2, tf3, tf4, tt1]
return ()