-
Notifications
You must be signed in to change notification settings - Fork 0
/
Set12.hs
228 lines (193 loc) · 7.39 KB
/
Set12.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
module Set12 where
import Data.Functor
import Data.Foldable
import Data.List
import Data.Monoid
import Mooc.Todo
------------------------------------------------------------------------------
-- Ex 1: Implement the function incrementAll that takes a functor
-- value containing numbers and increments each number inside by one.
--
-- Examples:
-- incrementAll [1,2,3] ==> [2,3,4]
-- incrementAll (Just 3.0) ==> Just 4.0
incrementAll :: (Functor f, Num n) => f n -> f n
incrementAll x = fmap (+1) x
------------------------------------------------------------------------------
-- Ex 2: Sometimes one wants to fmap multiple levels deep. Implement
-- the functions fmap2 and fmap3 that map over nested functors.
--
-- Examples:
-- fmap2 on [[Int]]:
-- fmap2 negate [[1,2],[3]]
-- ==> [[-1,-2],[-3]]
-- fmap2 on [Maybe String]:
-- fmap2 head [Just "abcd",Nothing,Just "efgh"]
-- ==> [Just 'a',Nothing,Just 'e']
-- fmap3 on [[[Int]]]:
-- fmap3 negate [[[1,2],[3]],[[4],[5,6]]]
-- ==> [[[-1,-2],[-3]],[[-4],[-5,-6]]]
-- fmap3 on Maybe [Maybe Bool]
-- fmap3 not (Just [Just False, Nothing])
-- ==> Just [Just True,Nothing]
fmap2 :: (Functor f, Functor g) => (a -> b) -> f (g a) -> f (g b)
fmap2 func = fmap $ fmap func
fmap3 :: (Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))
fmap3 func = fmap $ fmap $ fmap func
------------------------------------------------------------------------------
-- Ex 3: below you'll find a type Result that works a bit like Maybe,
-- but there are two different types of "Nothings": one with and one
-- without an error description.
--
-- Implement the instance Functor Result
data Result a = MkResult a | NoResult | Failure String
deriving Show
instance Functor Result where
fmap f (MkResult a) = MkResult (f a)
fmap _ NoResult = NoResult
fmap _ (Failure str) = Failure str
------------------------------------------------------------------------------
-- Ex 4: Here's a reimplementation of the Haskell list type. You might
-- remember it from Set6. Implement the instance Functor List.
--
-- Example:
-- fmap (+2) (LNode 0 (LNode 1 (LNode 2 Empty)))
-- ==> LNode 2 (LNode 3 (LNode 4 Empty))
data List a = Empty | LNode a (List a)
deriving Show
instance Functor List where
fmap _ Empty = Empty
fmap f (LNode a rest) = LNode (f a) (fmap f rest)
------------------------------------------------------------------------------
-- Ex 5: Here's another list type. This type every node contains two
-- values, so it's a type for a list of pairs. Implement the instance
-- Functor TwoList.
--
-- Example:
-- fmap (+2) (TwoNode 0 1 (TwoNode 2 3 TwoEmpty))
-- ==> TwoNode 2 3 (TwoNode 4 5 TwoEmpty)
data TwoList a = TwoEmpty | TwoNode a a (TwoList a)
deriving Show
instance Functor TwoList where
fmap _ TwoEmpty = TwoEmpty
fmap f (TwoNode a1 a2 rest) = TwoNode (f a1) (f a2) (fmap f rest)
------------------------------------------------------------------------------
-- Ex 6: Count all occurrences of a given element inside a Foldable.
--
-- Hint: you might find some useful functions from Data.Foldable.
-- Check the docs! Or then you can just implement count directly.
--
-- Examples:
-- count True [True,False,True] ==> 2
-- count 'c' (Just 'c') ==> 1
count :: (Eq a, Foldable f) => a -> f a -> Int
count x = getSum . foldMap (\y -> if y == x then Sum 1 else Sum 0)
------------------------------------------------------------------------------
-- Ex 7: Return all elements that are in two Foldables, as a list.
--
-- Examples:
-- inBoth "abcd" "fobar" ==> "ab"
-- inBoth [1,2] (Just 2) ==> [2]
-- inBoth Nothing [3] ==> []
inBoth :: (Foldable f, Foldable g, Eq a) => f a -> g a -> [a]
inBoth xs ys = [x | x <- toList xs, x `elem` toList ys]
where
toList :: Foldable t => t a -> [a]
toList = foldr (:) []
------------------------------------------------------------------------------
-- Ex 8: Implement the instance Foldable List.
--
-- Remember what the minimal complete definitions for Foldable were:
-- you should only need to implement one function.
--
-- After defining the instance, you'll be able to compute:
-- sum (LNode 1 (LNode 2 (LNode 3 Empty))) ==> 6
-- length (LNode 1 (LNode 2 (LNode 3 Empty))) ==> 3
instance Foldable List where
foldMap _ Empty = mempty
foldMap f (LNode x xs) = f x `mappend` foldMap f xs
------------------------------------------------------------------------------
-- Ex 9: Implement the instance Foldable TwoList.
--
-- After defining the instance, you'll be able to compute:
-- sum (TwoNode 0 1 (TwoNode 2 3 TwoEmpty)) ==> 6
-- length (TwoNode 0 1 (TwoNode 2 3 TwoEmpty)) ==> 4
instance Foldable TwoList where
foldMap _ TwoEmpty = mempty
foldMap f (TwoNode x1 x2 xs) = f x1 `mappend` f x2 `mappend` foldMap f xs
------------------------------------------------------------------------------
-- Ex 10: (Tricky!) Fun a is a type that wraps a function Int -> a.
-- Implement a Functor instance for it.
--
-- Figuring out what the Functor instance should do is most of the
-- puzzle.
data Fun a = Fun (Int -> a)
runFun :: Fun a -> Int -> a
runFun (Fun f) x = f x
instance Functor Fun where
fmap g (Fun f) = Fun (\x -> g (f x))
------------------------------------------------------------------------------
-- Ex 11: (Tricky!) You'll find the binary tree type from Set 5b
-- below. We'll implement a `Foldable` instance for it!
--
-- Implementing `foldr` directly for the Tree type is complicated.
-- However, there is another method in Foldable we can define instead:
--
-- foldMap :: Monoid m => (a -> m) -> Tree a -> m
--
-- There's a default implementation for `foldr` in Foldable that uses
-- `foldMap`.
--
-- Instead of implementing `foldMap` directly, we can build it with
-- these functions:
--
-- fmap :: (a -> m) -> Tree a -> Tree m
-- sumTree :: Monoid m => Tree m -> m
--
-- So your task is to define a `Functor` instance and the `sumTree`
-- function.
--
-- Examples:
-- using the [] Monoid with the (++) operation:
-- sumTree Leaf :: [a]
-- ==> []
-- sumTree (Node [3,4,5] (Node [1,2] Leaf Leaf) (Node [6] Leaf Leaf))
-- ==> [1,2,3,4,5,6]
-- using the Sum Monoid
-- sumTree Leaf :: Sum Int
-- ==> Sum 0
-- sumTree (Node (Sum 3) (Node (Sum 2) Leaf Leaf) (Node (Sum 1) Leaf Leaf))
-- ==> Sum 6
--
-- Once you're done, foldr should operate like this:
-- foldr (:) [] Leaf ==> []
-- foldr (:) [] (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)) ==> [1,2,3]
--
-- foldr (:) [] (Node 4 (Node 2 (Node 1 Leaf Leaf)
-- (Node 3 Leaf Leaf))
-- (Node 5 Leaf
-- (Node 6 Leaf Leaf)))
-- ==> [1,2,3,4,5,6]
--
-- The last example more visually:
--
-- .4.
-- / \
-- 2 5 ====> 1 2 3 4 5 6
-- / \ \
-- 1 3 6
data Tree a = Leaf | Node a (Tree a) (Tree a)
deriving Show
instance Functor Tree where
fmap _ Leaf = Leaf
fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)
sumTree :: Monoid m => Tree m -> m
sumTree Leaf = mempty
sumTree (Node x l r) = sumTree l `mappend` x `mappend` sumTree r
instance Foldable Tree where
foldMap f t = sumTree (fmap f t)
------------------------------------------------------------------------------
-- Bonus! If you enjoyed the two last exercises (not everybody will),
-- you'll like the `loeb` function:
--
-- https://github.com/quchen/articles/blob/master/loeb-moeb.md