Thinking Functionally with Haskell (55 page)

Jones, M.,
144
,
275

Just
,
244

Knuth, D.E.,
21
,
62
,
167

KRC,
x

Lapalme, G.,
180

last
,
68

Launchbury, J.,
275

laws

arithmetic,
17

bifunctor,
302

commutative,
186

distributive,
186

equational,
ix

functor,
71
,
81
,
303
,
330

fusion,
120
,
131
,
176

homomorphisms,
185
,
186

idempotence,
204

identities,
ix
,
110

involutions,
96
,
113

leapfrog,
247
,
265

left-distributive,
293

left-zero,
293

monad laws,
246
,
279

naturality,
72
,
87
,
97

point-free,
110

right-zero,
293

trigonometric,
ix

tupling,
152
,
165

layout description language,
182

lazy evaluation,
see
evaluation

least fixed points,
220

least upper bounds,
218

left-recursion problem,
287

Leibniz, G.,
243

length
,
69
,
79
,
160

let
,
see
expressions

lexicographic order,
76
,
189
,
217

liftM
,
264

lines
,
188
,
200

Linux,
12

list

adjacency,
261

comprehensions,
66
,
92
,
156
,
244
,
245
,
248

concatenation,
see
(++)

cyclic,
210

doubly-linked,
228

finite,
64

identity function,
118

indexing,
see
(!!)

infinite,
53
,
64
,
75
,
108
,
210

notation,
3

partial,
64
,
115
,
211

listArray
,
260

lists

adjacency,
261

literate programming,
8

local definitions,
11
,
149
,
256

log
,
141

logarithmic factors,
159

logarithmic time,
56

logBase
,
2
,
141

lookup
,
244
,
319

loop invariants,
255
,
263

lower bounds,
157

lowercase,
5

Loyd, S.,
267

Mac,
12

main
,
34
,
227

map
,
5
,
23
,
31
,
38
,
67
,
70
,
80
,
91
,
119
,
299

mapM
,
265

mapM_
,
265

Marlow, S.,
20

Maslanka, C.,
48

mathematical operators,
217

matrices,
90
,
94
,
234

matrix

addition,
105

multiplication,
105

transpose,
94
,
106

maximum
,
122

Maybe
,
39
,
244

McIlory, D.,
21

mean
,
151

Meijer, E.,
209
,
297

merge
,
76
,
211
,
231

mergesort,
see
sorting

minimum
,
104
,
107
,
122
,
157
,
211

Miranda,
x

mkStdGen
,
223

ML,
29
,
48

mod
,
9

modules,
13
,
25
,
35
,
309

export declarations,
35
,
199

hierarchical names,
21

import declarations,
13
,
35

Monad
,
243
,
264

monadic programming,
239

MonadPlus
,
292

monads,
243

commutative,
264

monoids,
247

mplus
,
292

mutable structures,
248

mzero
,
292

Nat
,
56
,
110
,
132

natural transformations,
87

negate
,
50

newline character,
see
\
n

newSTRef
,
251

Newton’s method,
60

newtype
declarations,
278

non-decreasing order,
74

none
,
134

normal form,
146

not
,
30

notElem
,
98

Nothing
,
244

nub
,
106
,
108

null
,
39
,
68

null tuple,
see
()

Num
,
23
,
31
,
49
,
56

Number Theory,
219

numbers

complex,
see
Complex

floating point,
see
Float
,
Double

floating-point,
60

integer,
see
Int
,
Integer

limited precision integers,
see
Int

natural,
56
,
110

unlimited precision integers,
see
Integer

O’Neill, M.,
237

O’Sullivan, B.,
21

offside rule,
36
,
242

one
,
134

Oppen, D.,
209

or
,
102

Ord
,
32

order of association,
2
–4,
17
,
25
,
62
,
196

Orwell,
x

otherwise
,
11

pairs,
2
,
74
,
76
,
82
,
177

palindromes,
41

paper–rock–scissors,
221

paragraphs,
191

parentheses,
15

parsers,
276

parsing,
239

partial application,
87

partial numbers,
58

partition
,
311

Patashnik, O.,
62

Paterson, R.,
337

patterns

n+k
,
111

as patterns,
77
,
83

disjoint,
68

don’t care,
67
,
73
,
103
,
268

exhaustive,
68

irrefutable,
231

matching,
57
,
67
,
68
,
74
,
115
,
194
,
332

wildcard,
67
,
268

perfect numbers,
65

Perlis, A.,
145

persistent data structures,
254

Peyton Jones, S.,
21
,
209

Pierce, B.,
87

plumbing combinators,
86

point-free calculations,
86
,
330

point-free reasoning,
298

pointers,
146

postconditions,
255
,
263

precedence,
14
,
25
,
37

preconditions,
255
,
263

prefix names,
25

prefix operators,
50

Prelude
,
25

primes
,
148
,
213
,
219
,
220
,
233

printing values,
33

profiling tools,
154

program variables,
251

programs,
7

prompt symbol,
13

prompts,
229
,
240

proof format,
xi
,
112

properFraction
,
56

putChar
,
240

putStrLn
,
16
,
33
,
239
,
240

Pythagorean triads,
66

Python,
x
,
239
,
252

qualified names,
306

quicksort,
see
sorting

Rabbi, F.,
180

Ramanujan, S.,
78

random numbers,
223
,
250

randomR
,
223

rank 2 polymorphic types,
253

Rational
,
49
,
50

Read
,
41
,
122
,
277

read
,
52
,
122

readFile
,
34

reading files,
34

ReadS
,
277

reads
,
277

readSTRef
,
251

Real
,
50

recursive definitions,
29
,
77
,
219

reduction,
see
evaluation

reduction steps,
155
,
156

reference variables,
251

reflexive relation,
217

repeat
,
108
,
212

return
,
241

reverse
,
42
,
72
,
113
,
117
,
123
,
159

running sums,
125

runST
,
252

SASL,
x

scanl
,
125
,
127

scanr
,
130

scientific notation,
60
,
112

scope,
11

scripts,
7
,
25
,
148

sections,
26
,
52
,
53

segments,
127
,
316

select
,
175

selection sort,
see
csorting

semicolon,
36

separator characters,
200

seq
,
150
,
153
,
226

sequence_
,
264

set theory,
211

shallow embeddings,
187
,
192

shared values,
146

Show
,
32
,
40
,
56
,
229
,
276
,
291

ShowS
,
289
,
311

showsPrec
,
290
,
291
,
308

side-effects,
243

sieve of Sundaram,
233

signum
,
50

Sijtsma, B.,
237

sin
,
2
,
14

sine function,
ix
,
xi
,
2
,
14

size measures,
156
,
202

snd
,
51

sort
,
14
,
75
,
154

sorting,
5
,
6
,
94
,
167

insertion sort,
172

mergesort,
76
,
168

numbers,
262

quicksort,
169
,
254
,
263

selection sort,
172

space character,
3

space efficiency,
29
,
84
,
147
,
149
,
154
,
171

space leaks,
147
,
151
,
170
,
171

span
,
75
,
102

Spivey, M.,
337

splitAt
,
80
,
168

sqrt
,
60

stand-alone programs,
34
,
227

standard prelude,
13
,
30
,
39
,
42
,
51
,
56
,
73
,
80
,
86
,
87
,
127
,
150
,
161
,
168
,
213
,
232