-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathChapter7.hs
More file actions
251 lines (162 loc) · 5 KB
/
Copy pathChapter7.hs
File metadata and controls
251 lines (162 loc) · 5 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
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
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
-------------------------------------------------------------------------
-- Haskell: The Craft of Functional Programming
-- Simon Thompson
-- (c) Addison-Wesley, 1999.
--
-- Chapter 7
-------------------------------------------------------------------------
module Chapter7 where
-- Defining functions over lists
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- For pedagogical reasons, this chapter repeats many of the definitions in the
-- standard Prelude. They are repeated in this file, and so the original
-- definitions have to be hidden when the Prelude is imported:
import Prelude hiding (id,head,tail,null,sum,concat,(++),zip,take,getLine)
import Chapter5 hiding (mystery) -- for the digits function
-- Pattern matching revisited
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^
-- An example function using guards ...
mystery :: Int -> Int -> Int
mystery x y
| x==0 = y
| otherwise = x
-- ... or pattern matching
mystery' :: Int -> Int -> Int
mystery' 0 y = y
mystery' x _ = x
-- To join two strings
joinStrings :: (String,String) -> String
joinStrings (st1,st2) = st1 ++ "\t" ++ st2
-- Lists and list patterns
-- ^^^^^^^^^^^^^^^^^^^^^^^
-- From the Prelude ...
head :: [a] -> a
head (x:_) = x
tail :: [a] -> [a]
tail (_:xs) = xs
null :: [a] -> Bool
null [] = True
null (_:_) = False
-- The case construction
-- ^^^^^^^^^^^^^^^^^^^^^
-- Return the first digit in a string.
firstDigit :: String -> Char
firstDigit st
= case (digits st) of
[] -> '\0'
(x:_) -> x
-- Primitive recursion over lists
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- The sum of a list of Ints.
sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
-- Finding primitive recursive definitions
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- Concatenating a list of lists.
concat :: [[a]] -> [a]
concat [] = []
concat (x:xs) = x ++ concat xs
-- Joining two lists
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x:(xs++ys)
-- To double every element of an integer list
doubleAll :: [Int] -> [Int]
doubleAll xs = [ 2*x | x<-xs ]
doubleAll' [] = []
doubleAll' (x:xs) = 2*x : doubleAll' xs
-- To select the even elements from an integer list.
selectEven :: [Int] -> [Int]
selectEven xs = [ x | x<-xs , isEven x ]
selectEven' [] = []
selectEven' (x:xs)
| isEven x = x : selectEven' xs
| otherwise = selectEven' xs
-- To sort a list of numbers into ascending order.
iSort :: [Int] -> [Int]
iSort [] = []
iSort (x:xs) = ins x (iSort xs)
-- To insert an element at the right place into a sorted list.
ins :: Int -> [Int] -> [Int]
ins x [] = [x]
ins x (y:ys)
| x <= y = x:(y:ys)
| otherwise = y : ins x ys
-- General recursions over lists
-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- Zipping together two lists.
zip :: [a] -> [b] -> [(a,b)]
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip (x:xs) [] = []
zip [] zs = []
-- Taking a given number of elements from a list.
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs)
| n>0 = x : take (n-1) xs
take _ _ = error "PreludeList.take: negative argument"
-- Quicksort over lists.
qSort :: [Int] -> [Int]
qSort [] = []
qSort (x:xs)
= qSort [ y | y<-xs , y<=x] ++ [x] ++ qSort [ y | y<-xs , y>x]
-- Example: Text Processing
-- ^^^^^^^^^^^^^^^^^^^^^^^^
-- The `whitespace' characters.
whitespace :: String
whitespace = ['\n','\t',' ']
-- Get a word from the front of a string.
getWord :: String -> String
getWord [] = []
getWord (x:xs)
| elem x whitespace = []
| otherwise = x : getWord xs
-- In a similar way, the first word of a string can be dropped.
dropWord :: String -> String
dropWord [] = []
dropWord (x:xs)
| elem x whitespace = (x:xs)
| otherwise = dropWord xs
-- To remove the whitespace character(s) from the front of a string.
dropSpace :: String -> String
dropSpace [] = []
dropSpace (x:xs)
| elem x whitespace = dropSpace xs
| otherwise = (x:xs)
-- A word is a string.
type Word = String
-- Splitting a string into words.
splitWords :: String -> [Word]
splitWords st = split (dropSpace st)
split :: String -> [Word]
split [] = []
split st
= (getWord st) : split (dropSpace (dropWord st))
-- Splitting into lines of length at most lineLen
lineLen :: Int
lineLen = 80
-- A line is a list of words.
type Line = [Word]
-- Getting a line from a list of words.
getLine :: Int -> [Word] -> Line
getLine len [] = []
getLine len (w:ws)
| length w <= len = w : restOfLine
| otherwise = []
where
newlen = len - (length w + 1)
restOfLine = getLine newlen ws
-- Dropping the first line from a list of words.
dropLine :: Int -> [Word] -> Line
dropLine = dropLine -- DUMMY DEFINITION
-- Splitting into lines.
splitLines :: [Word] -> [Line]
splitLines [] = []
splitLines ws
= getLine lineLen ws
: splitLines (dropLine lineLen ws)
-- To fill a text string into lines, we write
fill :: String -> [Line]
fill = splitLines . splitWords