-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathChapter9.lhs
More file actions
179 lines (111 loc) · 4 KB
/
Copy pathChapter9.lhs
File metadata and controls
179 lines (111 loc) · 4 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
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 \texttt{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