-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathChapter9.hs
More file actions
180 lines (114 loc) · 4.16 KB
/
Copy pathChapter9.hs
File metadata and controls
180 lines (114 loc) · 4.16 KB
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
------------------------------------------------------------------------------
-- Haskell: The Craft of Functional Programming
-- Simon Thompson
-- (c) Addison-Wesley, 1999.
--
-- Chapter 9
------------------------------------------------------------------------------
-- Generalization: patterns of computation
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
module Chapter9 where
import Prelude hiding (map,filter,zipWith,foldr1,foldr,concat,and)
import Pictures hiding (flipV,sideBySide)
import qualified Chapter7
-- Higher-order functions: functions as arguments
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- Mapping a function along a list.
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
map,map' :: (a -> b) -> [a] -> [b]
map' f xs = [ f x | x <- xs ] -- (map.0)
map f [] = [] -- (map.1)
map f (x:xs) = f x : map f xs -- (map.2)
-- Examples using map.
-- Double all the elements of a list ...
doubleAll :: [Int] -> [Int]
doubleAll xs = map double xs
where
double x = 2*x
-- ... convert characters to their numeric codes ...
convertChrs :: [Char] -> [Int]
convertChrs xs = map ord xs
-- ... flip a Picture in a vertical mirror.
flipV :: Picture -> Picture
flipV xs = map reverse xs
-- Modelling properties as functions
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- Is an integer even?
isEven :: Int -> Bool
isEven n = (n `mod` 2 == 0)
-- Is a list sorted?
isSorted :: [Int] -> Bool
isSorted xs = (xs == iSort xs)
-- Filtering -- the filter function
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = [] -- (filter.1)
filter p (x:xs)
| p x = x : filter p xs -- (filter.2)
| otherwise = filter p xs -- (filter.3)
-- A list comprehension also serves to define filter,
filter' p xs = [ x | x <- xs , p x ] -- (filter.0)
-- Combining zip and map -- the zipWith function
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith f _ _ = []
sideBySide :: Picture -> Picture -> Picture
sideBySide pic1 pic2 = zipWith (++) pic1 pic2
-- Folding and primitive recursion
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- Folding an operation into a non-empty list
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f [x] = x -- (foldr1.1)
foldr1 f (x:xs) = f x (foldr1 f xs) -- (foldr1.2)
-- Examples using foldr1
foldEx1 = foldr1 (+) [3,98,1]
foldEx2 = foldr1 (||) [False,True,False]
foldEx3 = foldr1 (++) ["Freak ", "Out" , "", "!"]
foldEx4 = foldr1 min [6]
foldEx5 = foldr1 (*) [1 .. 6]
-- Folding into an arbitrary list: using a starting value on the empty list.
foldr f s [] = s -- (foldr.1)
foldr f s (x:xs) = f x (foldr f s xs) -- (foldr.2)
-- Concatenating a list using foldr.
concat :: [[a]] -> [a]
concat xs = foldr (++) [] xs
-- Conjoining a list of Bool using foldr.
and :: [Bool] -> Bool
and bs = foldr (&&) True bs
-- Can define foldr1 using foldr:
-- foldr1 f (x:xs) = foldr f x xs -- (foldr1.0)
-- Folding in general -- foldr again
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- The type of foldr is more general than you would initially expect...
foldr :: (a -> b -> b) -> b -> [a] -> b
rev :: [a] -> [a]
rev xs = foldr snoc [] xs
snoc :: a -> [a] -> [a]
snoc x xs = xs ++ [x]
-- Sorting a list using foldr
iSort :: [Int] -> [Int]
iSort xs = foldr Chapter7.ins [] xs
-- From the exercises: a mystery function ...
mystery xs = foldr (++) [] (map sing xs)
sing x = [x]
-- Generalizing: splitting up lists
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- Getting the first word from the front of a String ...
getWord :: String -> String
getWord [] = [] -- (getWord.1)
getWord (x:xs)
| elem x Chapter7.whitespace = [] -- (getWord.2)
| otherwise = x : getWord xs -- (getWord.3)
-- ... which generalizes to a function which gets items from the front of a list
-- until an item has the required property.
getUntil :: (a -> Bool) -> [a] -> [a]
getUntil p [] = []
getUntil p (x:xs)
| p x = []
| otherwise = x : getUntil p xs
-- The original getWord function defined from getUntil
-- getWord xs
-- = getUntil p xs
-- where
-- p x = elem x whitespace