-
Notifications
You must be signed in to change notification settings - Fork 0
/
python-programming.html
502 lines (452 loc) · 87.1 KB
/
python-programming.html
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
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
<!DOCTYPE html SYSTEM "about:legacy-compat">
<html lang="en-US" data-preset="contrast" data-primary-color="#6860F6" data-link-color="#307FFF" data-resizable-sidebar="true" data-sidebar-width="260"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><meta charset="UTF-8"><meta name="built-on" content="2024-11-14T14:28:58.5830709"><title>Python Programming | Computer Science Study Notes</title><script type="application/json" id="virtual-toc-data">[{"id":"1-basic-python-knowledge","level":0,"title":"1 Basic Python Knowledge","anchor":"#1-basic-python-knowledge"},{"id":"1-1-strings","level":1,"title":"1.1 Strings","anchor":"#1-1-strings"},{"id":"1-1-1-string-representation","level":2,"title":"1.1.1 String Representation","anchor":"#1-1-1-string-representation"},{"id":"1-1-2-strings-in-python","level":2,"title":"1.1.2 Strings in Python","anchor":"#1-1-2-strings-in-python"},{"id":"1-2-lists","level":1,"title":"1.2 Lists","anchor":"#1-2-lists"},{"id":"1-3-tuple","level":1,"title":"1.3 Tuple","anchor":"#1-3-tuple"},{"id":"sets","level":1,"title":"1.4 Set","anchor":"#sets"},{"id":"dictionaries","level":1,"title":"1.5 Dictionary","anchor":"#dictionaries"},{"id":"1-6-bytes","level":1,"title":"1.6 Bytes","anchor":"#1-6-bytes"},{"id":"1-7-logical-operators","level":1,"title":"1.7 Logical Operators","anchor":"#1-7-logical-operators"},{"id":"2-higher-order-function","level":0,"title":"2 Higher-Order Function","anchor":"#2-higher-order-function"},{"id":"2-1-higher-order-function-functions-as-arguments","level":1,"title":"2.1 Higher-Order Function (Functions as Arguments)","anchor":"#2-1-higher-order-function-functions-as-arguments"},{"id":"2-2-nested-definitions-functions-as-returned-values","level":1,"title":"2.2 Nested Definitions (Functions as Returned Values)","anchor":"#2-2-nested-definitions-functions-as-returned-values"},{"id":"2-3-lambda-expressions","level":1,"title":"2.3 Lambda Expressions","anchor":"#2-3-lambda-expressions"},{"id":"2-4-currying","level":1,"title":"2.4 Currying","anchor":"#2-4-currying"},{"id":"3-recursion","level":0,"title":"3 Recursion","anchor":"#3-recursion"},{"id":"3-1-self-reference-return-by-its-own-name","level":1,"title":"3.1 Self-Reference: Return by its own name","anchor":"#3-1-self-reference-return-by-its-own-name"},{"id":"3-2-recursion-environment-diagrams","level":1,"title":"3.2 Recursion \u0026 Environment Diagrams","anchor":"#3-2-recursion-environment-diagrams"},{"id":"3-3-iteration-recursion","level":1,"title":"3.3 Iteration \u0026 Recursion","anchor":"#3-3-iteration-recursion"},{"id":"3-4-mutual-recursion","level":1,"title":"3.4 Mutual Recursion","anchor":"#3-4-mutual-recursion"},{"id":"4-iterators-generators","level":0,"title":"4 Iterators \u0026 Generators","anchor":"#4-iterators-generators"},{"id":"4-1-iterators","level":1,"title":"4.1 Iterators","anchor":"#4-1-iterators"},{"id":"4-2-iterables","level":1,"title":"4.2 Iterables","anchor":"#4-2-iterables"},{"id":"4-3-generators","level":1,"title":"4.3 Generators","anchor":"#4-3-generators"},{"id":"4-4-built-in-iterator-functions","level":1,"title":"4.4 Built-In Iterator Functions","anchor":"#4-4-built-in-iterator-functions"},{"id":"4-4-1-map","level":2,"title":"4.4.1 Map","anchor":"#4-4-1-map"},{"id":"4-4-2-filter","level":2,"title":"4.4.2 Filter","anchor":"#4-4-2-filter"},{"id":"4-4-3-zip","level":2,"title":"4.4.3 zip","anchor":"#4-4-3-zip"},{"id":"4-4-4-reversed","level":2,"title":"4.4.4 reversed","anchor":"#4-4-4-reversed"},{"id":"4-4-5-range-iterator","level":2,"title":"4.4.5 range iterator","anchor":"#4-4-5-range-iterator"},{"id":"5-efficiency","level":0,"title":"5 Efficiency","anchor":"#5-efficiency"},{"id":"5-1-order-of-growth","level":1,"title":"5.1 Order of Growth","anchor":"#5-1-order-of-growth"},{"id":"5-2-space","level":1,"title":"5.2 Space","anchor":"#5-2-space"},{"id":"6-object-oriented-programming","level":0,"title":"6 Object-Oriented Programming","anchor":"#6-object-oriented-programming"},{"id":"6-1-object-oriented-programming-in-python","level":1,"title":"6.1 Object-Oriented Programming in Python","anchor":"#6-1-object-oriented-programming-in-python"},{"id":"6-2-inheritance","level":1,"title":"6.2 Inheritance","anchor":"#6-2-inheritance"},{"id":"6-3-special-method-functions","level":1,"title":"6.3 Special Method Functions","anchor":"#6-3-special-method-functions"},{"id":"7-scheme","level":0,"title":"7 Scheme","anchor":"#7-scheme"},{"id":"7-1-scheme-fundamentals","level":1,"title":"7.1 Scheme Fundamentals","anchor":"#7-1-scheme-fundamentals"},{"id":"7-2-scheme-lists","level":1,"title":"7.2 Scheme Lists","anchor":"#7-2-scheme-lists"}]</script><script type="application/json" id="topic-shortcuts"></script><link href="https://resources.jetbrains.com/writerside/apidoc/6.10.0-b518/app.css" rel="stylesheet"><link href="static/custom.css" rel="stylesheet"><link rel="icon" type="image/png" sizes="16x16" href="Computer-Science-Study-Notes/photo.png"><meta name="image" content=""><!-- Open Graph --><meta property="og:title" content="Python Programming | Computer Science Study Notes"><meta property="og:description" content=""><meta property="og:image" content=""><meta property="og:site_name" content="Computer Science Study Notes Help"><meta property="og:type" content="website"><meta property="og:locale" content="en_US"><meta property="og:url" content="writerside-documentation/python-programming.html"><!-- End Open Graph --><!-- Twitter Card --><meta name="twitter:card" content="summary_large_image"><meta name="twitter:site" content=""><meta name="twitter:title" content="Python Programming | Computer Science Study Notes"><meta name="twitter:description" content=""><meta name="twitter:creator" content=""><meta name="twitter:image:src" content=""><!-- End Twitter Card --><!-- Schema.org WebPage --><script type="application/ld+json">{
"@context": "http://schema.org",
"@type": "WebPage",
"@id": "writerside-documentation/python-programming.html#webpage",
"url": "writerside-documentation/python-programming.html",
"name": "Python Programming | Computer Science Study Notes",
"description": "",
"image": "",
"inLanguage":"en-US"
}</script><!-- End Schema.org --><!-- Schema.org WebSite --><script type="application/ld+json">{
"@type": "WebSite",
"@id": "writerside-documentation/#website",
"url": "writerside-documentation/",
"name": "Computer Science Study Notes Help"
}</script><!-- End Schema.org --></head><body data-id="Python-Programming" data-main-title="Python Programming" data-article-props="{"seeAlsoStyle":"links"}" data-template="article" data-breadcrumbs=""><div class="wrapper"><main class="panel _main"><header class="panel__header"><div class="container"><h3>Computer Science Study Notes Help</h3><div class="panel-trigger"></div></div></header><section class="panel__content"><div class="container"><article class="article" data-shortcut-switcher="inactive"><h1 data-toc="Python-Programming" data-label-id="finish" id="Python-Programming.topic">Python Programming</h1><section class="chapter"><h2 id="1-basic-python-knowledge" data-toc="1-basic-python-knowledge">1 Basic Python Knowledge</h2><section class="chapter"><h3 id="1-1-strings" data-toc="1-1-strings">1.1 Strings</h3><section class="chapter"><h4 id="1-1-1-string-representation" data-toc="1-1-1-string-representation">1.1.1 String Representation</h4><p id="h2iaaf_21">In Python, all objects produce two string representations:</p><ul class="list _bullet" id="h2iaaf_22"><li class="list__item" id="h2iaaf_24"><p id="h2iaaf_26">The <span id="h2iaaf_27"><font style="color:#ff00ff">str</font></span> is legible to humans.</p></li><li class="list__item" id="h2iaaf_25"><p id="h2iaaf_28">The <span id="h2iaaf_29"><font style="color:#ff00ff">repr</font></span> is legible to Python interpreter.</p></li></ul><ol class="list _alpha-lower" id="h2iaaf_23" type="a"><li class="list__item" id="h2iaaf_30"><p id="h2iaaf_32"><span id="h2iaaf_35"><font style="color:#ff00ff">repr:</font></span> Provides a string representation that can be used to recreate the object. It's designed for debugging and introspection. It aims for a more precise and detailed description, often including the object's type.</p><p id="h2iaaf_33"><span id="h2iaaf_36"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="class MyClass:">
class MyClass:
def __init__(self, value):
self.value = value
def __repr__(self):
return f"MyClass({self.value})"
obj = MyClass(10)
print(repr(obj)) # Output: MyClass(10)
</div></li><li class="list__item" id="h2iaaf_31"><p id="h2iaaf_37"><span id="h2iaaf_40"><font style="color:#ff00ff">repr:</font></span> Provides a human- readable string representation of the object. It's designed to be easily understood by humans.</p><p id="h2iaaf_38"><span id="h2iaaf_41"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="class MyClass:">
class MyClass:
def __init__(self, value):
self.value = value
def __str__(self):
return f"MyClass with value: {self.value}"
obj = MyClass(10)
print(str(obj)) # Output: MyClass with value: 10
</div></li></ol></section><section class="chapter"><h4 id="1-1-2-strings-in-python" data-toc="1-1-2-strings-in-python">1.1.2 Strings in Python</h4><p id="h2iaaf_42">For more information on strings, please visit <a href="data-structures-and-algorithms-3.html#strings-in-java" id="h2iaaf_48" data-tooltip="Strings in Java">strings in Java</a>.</p><p id="h2iaaf_43"><span id="h2iaaf_49"><font style="color:#8a2be2">Examples in Python:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="name = "Nate"">
name = "Nate"
age = 19
s = "My name is %s and I am %d years old" % (name, age)
s1 = "My name is {} and I am {} years old".format(name, age)
s2 = f"My name is {name} and I am {age} years old"
print(f"2 + 2 = {(lambda x: x + x)(2)}") # 2 + 2 = 4
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="s = "I have a dream!"">
s = "I have a dream!"
print(s[2:6]) # "have"
print(s[2:]) # "have a dream!"
print(s[-3:-1]) # "am"
print(s[-1:-3]) # "" No result!
print(s[::-1]) # "!maerd a evah I", -1 refers to the step
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="s = "dream"">
s = "dream"
s1 = s.captialize() # "Dream"
s2 = "i have a dream!"
s3 = s2.title() # "I Have A Dream!"
s4 = "I HAVE A DREAM!"
s5 = s4.lower() # "i have a dream!"
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="s = " I have a dream! "">
s = " I have a dream! "
s1 = s.strip() # "I have a dream!" strip() can remove whitespace, \n, \t
s2 = "I have a dream!"
s3 = s2.replace("dream", "car") # "I have a car!"
s4 = s2.split(" ") # ["I", "have", "a", "dream!"]
s5 = "I have a dream!"
ret = s5.find("dream") # 9
ret = s5.find("car") # -1
ret = s5.index("dream") # 9
ret = s5.index("car") # ValueError
print("I" in s5) # True
print(s5.startswith("I")) # True
s6 = "123"
ret = s6.isdigit() # True
</div></section></section><section class="chapter"><h3 id="1-2-lists" data-toc="1-2-lists">1.2 Lists</h3><p id="h2iaaf_50"><span id="h2iaaf_54"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="lst = ["I", "have", "a", "dream!"]">
lst = ["I", "have", "a", "dream!"]
s = " ".join(lst) # "I have a dream!"
for item in lst:
print(item) # I have a dream!
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="lst = []">
lst = []
lst.append("I") # ["I"]
lst.insert(0, "have") # ["have", "I"]
lst.extend(["a", "dream!"]) # ["have", "I", "a", "dream!"]
lst.pop() # "dream!"
lst.pop(0) # "have"
lst.remove("I") # ["a"]
lst.[0] = "me" # ["me"]
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="lst = [1, 2, 4, 3, 5]">
lst = [1, 2, 4, 3, 5]
lst.sort() # [1, 2, 3, 4, 5]
lst.sort(reverse=True) # [5, 4, 3, 2, 1]
lst = ["I", "have", "a", "dream!"]
lst[1] = lst[1].upper() # string operations must return a new string
print(lst) # ["I", "HAVE", "a", "dream!"]
</div></section><section class="chapter"><h3 id="1-3-tuple" data-toc="1-3-tuple">1.3 Tuple</h3><p id="h2iaaf_55"><span id="h2iaaf_57"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="t = ()">
t = ()
t = (1, 2, 3)
t[1] = 4 # TypeError -> Tuple is unchangeable!
t = ("I have a dream!")
print(type(t)) # <class 'str'>
t = ("I have a dream!",)
print(type(t)) # <class 'tuple'>
t = ("I", "have", ["a", "dream"])
t[2].append("!")
print(t) # ("I", "have", ["a", "dream", "!"])
# "Tuple is unchangeable" means the cache address of the tuple is unchangeable.
</div></section><section class="chapter"><h3 id="sets" data-toc="sets">1.4 Set</h3><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="s = {}">
s = {}
print(type(s)) # <class 'dict'>
s = {1, 2, 3}
s = set()
</div><p id="h2iaaf_59">Set cannot contain unhashable type aka mutable type.</p><ul class="list _bullet" id="h2iaaf_60"><li class="list__item" id="h2iaaf_64"><p id="h2iaaf_66"><span id="h2iaaf_67"><font style="color:#ff00ff">Hashable type:</font></span> int, float, string, tuple, bool.</p></li><li class="list__item" id="h2iaaf_65"><p id="h2iaaf_68"><span id="h2iaaf_69"><font style="color:#ff00ff">Unhashable type:</font></span> list, set, dict.</p></li></ul><div class="code-block" data-lang="python">
s = {1, 2, 3, []} # TypeError: unhashable type: 'list'
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="s = set()">
s = set()
s.add(1)
s.add(2)
s.add(3)
s.pop()
s.remove(2)
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="s1 = {1, 2, 3}">
s1 = {1, 2, 3}
s2 = {3, 4, 5}
print(s1 & s2) # {3}
print(s1.intersection(s2)) # {3}
print(s1 | s2) # {1, 2, 3, 4, 5}
print(s1.union(s2)) # {1, 2, 3, 4, 5}
print(s1 - s2) # {1, 2}
print(s1.difference(s2)) # {1, 2}
</div></section><section class="chapter"><h3 id="dictionaries" data-toc="dictionaries">1.5 Dictionary</h3><aside class="prompt" data-type="note" data-title="" id="h2iaaf_70"><p id="h2iaaf_77">Some important notes:</p><ul class="list _bullet" id="h2iaaf_78"><li class="list__item" id="h2iaaf_79"><p id="h2iaaf_81">A key of a dictionary cannot be a list or a dictionary (or any mutable type).</p></li><li class="list__item" id="h2iaaf_80"><p id="h2iaaf_82">Two keys cannnot be equal.</p></li></ul></aside><div class="code-block" data-lang="python">
dic = {1: "I", 2: "have", 3: "a", 4: "dream!"}
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="dic = {} # dic = dict()">
dic = {} # dic = dict()
dic[1] = "I"
dic[2] = "have" # {1: "I", 2: "have"}
dic.setdefault(3, "a") # {1: "I", 2: "have", 3: "a"}
'''
If the key exists, skip;
otherwise, add and set the key-value pair to default in dictionary.
'''
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}">
dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}
dict.pop(4) # {1: "I", 2: "have", 3: "a"}
print(dict[0]) # KeyError
print(dict.get(0)) # None
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}">
dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}
for key in dict:
print(key, dict[key])
print(list(dict.keys())) # [1, 2, 3, 4]
print(list(dict.values())) # ["I", "have", "a", "dream!"]
for item in dict.items():
print(item)
for key, value in dict.items():
print(key, value)
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}">
dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}
for key in dict:
dict.pop(key) # RuntimeError: dictionary changed size during iteration
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}">
dict = {1: "I", 2: "have", 3: "a", 4: "dream!"}
for key in list(dict.keys()):
dict.pop(key) # No error
</div></section><section class="chapter"><h3 id="1-6-bytes" data-toc="1-6-bytes">1.6 Bytes</h3><ol class="list _decimal" id="h2iaaf_83" type="1"><li class="list__item" id="h2iaaf_84"><p id="h2iaaf_89"><span id="h2iaaf_90"><font style="color:#ff00ff">ASCII:</font></span> 1 bytes, 8 bits.</p></li><li class="list__item" id="h2iaaf_85"><p id="h2iaaf_91"><span id="h2iaaf_93"><font style="color:#ff00ff">ANSI:</font></span> A standard. 2 bytes, 16 bits.</p><ul class="list _bullet" id="h2iaaf_92"><li class="list__item" id="h2iaaf_94"><p id="h2iaaf_97"><span id="h2iaaf_98"><font style="color:#7cfc00">Mainland China:</font></span> GB2312 => GBK (Windows).</p></li><li class="list__item" id="h2iaaf_95"><p id="h2iaaf_99"><span id="h2iaaf_100"><font style="color:#7cfc00">Taiwan, China:</font></span> Big5.</p></li><li class="list__item" id="h2iaaf_96"><p id="h2iaaf_101"><span id="h2iaaf_102"><font style="color:#7cfc00">Japan:</font></span> JIS.</p></li></ul></li><li class="list__item" id="h2iaaf_86"><p id="h2iaaf_103"><span id="h2iaaf_105"><font style="color:#ff00ff">Unicode:</font></span></p><ul class="list _bullet" id="h2iaaf_104"><li class="list__item" id="h2iaaf_106"><p id="h2iaaf_108"><span id="h2iaaf_109"><font style="color:#7cfc00">UCS-2:</font></span> 2 bytes, 16 bits.</p></li><li class="list__item" id="h2iaaf_107"><p id="h2iaaf_110"><span id="h2iaaf_111"><font style="color:#7cfc00">UCS-4:</font></span> 4 bytes, 32 bits .</p></li></ul></li><li class="list__item" id="h2iaaf_87"><p id="h2iaaf_112"><span id="h2iaaf_114"><font style="color:#ff00ff">UTF:</font></span> All the same as Unicode, except that the length is changeable.</p><ul class="list _bullet" id="h2iaaf_113"><li class="list__item" id="h2iaaf_115"><p id="h2iaaf_118"><span id="h2iaaf_119"><font style="color:#7cfc00">English:</font></span> 1 byte, 8 bits .</p></li><li class="list__item" id="h2iaaf_116"><p id="h2iaaf_120"><span id="h2iaaf_121"><font style="color:#7cfc00">Some of European languages:</font></span> 2 bytes, 16 bits.</p></li><li class="list__item" id="h2iaaf_117"><p id="h2iaaf_122"><span id="h2iaaf_123"><font style="color:#7cfc00">Chinese:</font></span> 3 bytes, 24 bits.</p></li></ul></li><li class="list__item" id="h2iaaf_88"><p id="h2iaaf_124"><span id="h2iaaf_125"><font style="color:#ff00ff">UTF-16:</font></span> Shortest length is 16 bits.</p></li></ol></section><section class="chapter"><h3 id="1-7-logical-operators" data-toc="1-7-logical-operators">1.7 Logical Operators</h3><p id="h2iaaf_126">Priority:</p><p id="h2iaaf_127">() => not => and => or</p></section></section><section class="chapter"><h2 id="2-higher-order-function" data-toc="2-higher-order-function">2 Higher-Order Function</h2><p id="h2iaaf_128"><span id="h2iaaf_133"><font style="color:#ff8c00">Higher-order function:</font></span> A function that takes a function as an argument value or returns a function as a return value.</p><section class="chapter"><h3 id="2-1-higher-order-function-functions-as-arguments" data-toc="2-1-higher-order-function-functions-as-arguments">2.1 Higher-Order Function (Functions as Arguments)</h3><p id="h2iaaf_134"><span id="h2iaaf_140"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def summation(n, term):">
def summation(n, term):
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
def cube(k):
return k * k * k
def sum_cubes(n):
return summation(n, cube)
</div><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def apply_twice(f, x):">
def apply_twice(f, x):
return f(f(x))
def square(x):
return x * x
result = apply_twice(square, 2)
</div><section class="procedure-steps"><h3 id="apply-a-user-defined-function" data-toc="apply-a-user-defined-function">Apply a User-Defined Function</h3><ol class="list _decimal"><li class="list__item" id="h2iaaf_141"><p id="h2iaaf_144">Create a new frame.</p></li><li class="list__item" id="h2iaaf_142"><p id="h2iaaf_145">Bind formal parameters (f & x) to arguments.</p></li><li class="list__item" id="h2iaaf_143"><p id="h2iaaf_146">Execute the body: return f(f(x)).</p></li></ol></section><aside class="prompt" data-type="note" data-title="" id="h2iaaf_138"><p id="h2iaaf_147">This is the environment frame for the code above.</p></aside><figure id="h2iaaf_139"><img alt="Environments for Higher
-Order Functions" src="Computer-Science-Study-Notes/p2-1-1.png" title="Environments for Higher
-Order Functions" width="485" height="719"></figure></section><section class="chapter"><h3 id="2-2-nested-definitions-functions-as-returned-values" data-toc="2-2-nested-definitions-functions-as-returned-values">2.2 Nested Definitions (Functions as Returned Values)</h3><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def make_adder(n):">
def make_adder(n):
def adder(x):
return x + n
return adder
</div><p id="h2iaaf_149">Propositions:</p><ul class="list _bullet" id="h2iaaf_150"><li class="list__item" id="h2iaaf_152"><p id="h2iaaf_156">Every user-defined function has a parent frame (often global).</p></li><li class="list__item" id="h2iaaf_153"><p id="h2iaaf_157">The parent of a function is the frame in which it was defined.</p></li><li class="list__item" id="h2iaaf_154"><p id="h2iaaf_158">Every local frame has a parent frame (often global).</p></li><li class="list__item" id="h2iaaf_155"><p id="h2iaaf_159">The parent of a frame is the parent of function called.</p></li></ul><figure id="h2iaaf_151"><img alt="Environments for Nested
Definitions" src="Computer-Science-Study-Notes/p2-1-2.png" title="Environments for Nested
Definitions" width="563" height="560"></figure></section><section class="chapter"><h3 id="2-3-lambda-expressions" data-toc="2-3-lambda-expressions">2.3 Lambda Expressions</h3><p id="h2iaaf_160"><span id="h2iaaf_164"><font style="color:#8a2be2">Important notes:</font></span></p><ul class="list _bullet" id="h2iaaf_161"><li class="list__item" id="h2iaaf_165"><p id="h2iaaf_168">No "return" keyword!</p></li><li class="list__item" id="h2iaaf_166"><p id="h2iaaf_169">Lambda expressions are not common in Python, but important in general.</p></li><li class="list__item" id="h2iaaf_167"><p id="h2iaaf_170">Lambda expressions in Python cannot contain statements at all!</p></li></ul><div class="tabs" id="h2iaaf_162" data-anchors="[c,java,javascript,python]"><div class="tabs__content" data-gtm="tab" id="python" data-title="Python"><div class="code-block" data-lang="python" data-title="Python">
square = lambda x: x * x
</div></div><div class="tabs__content" data-gtm="tab" id="c" data-title="C++"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="auto lambda = [](int x, int y) {">
auto lambda = [](int x, int y) {
int sum = x + y;
int product = x * y;
return sum + product;
};
int result = lambda(5, 7); // result will be 47
</div></div><div class="tabs__content" data-gtm="tab" id="java" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="public static void main(String[] args) {">
public static void main(String[] args) {
IntBinaryOperator addAndMultiply = (x, y) -> {
int sum = x + y;
int product = x * y;
return sum + product;
};
int result = addAndMultiply.applyAsInt(5, 7); // result will be 47
System.out.println(result);
}
</div></div><div class="tabs__content" data-gtm="tab" id="javascript" data-title="JavaScript"><div class="code-collapse" data-lang="javascript" data-title="JavaScript" data-is-expanded="false" data-synopsis="let myFunction = (x, y) => {">
let myFunction = (x, y) => {
let sum = x + y;
let product = x * y;
return sum + product;
};
let result = myFunction(5, 7); // result will be 47
</div></div></div><aside class="prompt" data-type="tip" data-title="" id="h2iaaf_163"><ol class="list _decimal" id="h2iaaf_179" type="1"><li class="list__item" id="h2iaaf_180"><p id="h2iaaf_182">C++, Java and JavaScript all support multiple lines of code in the lambda expression.</p></li><li class="list__item" id="h2iaaf_181"><p id="h2iaaf_183">For more information on lambda functions in C++, please visit <a href="c-programming.html#Lambda" id="h2iaaf_184" data-tooltip="Lambda Functions in C++">C++ Programming</a>.</p></li></ol></aside></section><section class="chapter"><h3 id="2-4-currying" data-toc="2-4-currying">2.4 Currying</h3><p id="h2iaaf_185"><span id="h2iaaf_187"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def curry2(f):">
def curry2(f):
def g(x):
def h(y):
return f(x, y)
return h
return g
def add(x, y):
return x + y
s = curry2(add)(1)(2)
</div></section></section><section class="chapter"><h2 id="3-recursion" data-toc="3-recursion">3 Recursion</h2><p id="h2iaaf_188"><span id="h2iaaf_193"><font style="color:#ff8c00">Recursive Function:</font></span> A function is called <span id="h2iaaf_194"><i>recursive</i></span> if the body of that function calls itself, either directly or indirectly.</p><section class="chapter"><h3 id="3-1-self-reference-return-by-its-own-name" data-toc="3-1-self-reference-return-by-its-own-name">3.1 Self-Reference: Return by its own name</h3><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def print_all(x):">
def print_all(x):
print(x)
return print_all
print_all(1)(3)(5)
</div><figure id="h2iaaf_196"><img alt="Environment Diagram" src="Computer-Science-Study-Notes/p3-1-1.png" title="Environment Diagram" width="553" height="784"></figure><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def print_sums(x):">
def print_sums(x):
print(x)
def next_sum(y):
return print_sums(x + y)
return next_sum
print_sums(1)(3)(5)
</div><figure id="h2iaaf_198"><img alt="Environment Diagram" src="Computer-Science-Study-Notes/p3-1-2.png" title="Environment Diagram" width="521" height="840"></figure></section><section class="chapter"><h3 id="3-2-recursion-environment-diagrams" data-toc="3-2-recursion-environment-diagrams">3.2 Recursion & Environment Diagrams</h3><p id="h2iaaf_199"><span id="h2iaaf_205"><font style="color:#8a2be2">Example 1:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def split(n):">
def split(n):
return n // 10, n % 10
def sum_digits(n):
# Base Cases
if n < 10:
return n
else:
all_but_last, last = split(n)
return sum_digits(all_but_last) + last
</div><figure id="h2iaaf_201"><img alt="environment diagram
for example 1" src="Computer-Science-Study-Notes/p3-2-1.png" title="environment diagram
for example 1" width="448" height="762"></figure><p id="h2iaaf_202">Example 2:</p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def fact(n):">
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
</div><figure id="h2iaaf_204"><img alt="Environment Diagram" src="Computer-Science-Study-Notes/p3-2-2.png" title="Environment Diagram" width="318" height="724"></figure></section><section class="chapter"><h3 id="3-3-iteration-recursion" data-toc="3-3-iteration-recursion">3.3 Iteration & Recursion</h3><aside class="prompt" data-type="warning" data-title="" id="h2iaaf_206"><p id="h2iaaf_208">Iteration is a special case of recursion!</p></aside><div class="table-wrapper"><table class="left_header wide" id="h2iaaf_207"><thead><tr class="ijRowHead" id="h2iaaf_209"><th id="h2iaaf_213"></th><th id="h2iaaf_214"><p>Iteration</p></th><th id="h2iaaf_215"><p>Recursion</p></th></tr></thead><tbody><tr id="h2iaaf_210"><th id="h2iaaf_216"><p>Sample Implementation</p></th><td id="h2iaaf_217"><p id="h2iaaf_219">Using while:</p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def fact_iter(n):">
def fact_iter(n):
total, k = 1, 1
while k <= n:
total, k = total * k, k + 1
return total
</div></td><td id="h2iaaf_218"><p id="h2iaaf_221">Using recursion:</p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def fact(n):">
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
</div></td></tr><tr id="h2iaaf_211"><th id="h2iaaf_223"><p>Math</p></th><td id="h2iaaf_224"><div><mjx-container class="MathJax" jax="SVG" display="true"><svg style="vertical-align: -2.864ex;" xmlns="http://www.w3.org/2000/svg" width="9.451ex" height="6.416ex" role="img" focusable="false" viewBox="0 -1570.3 4177.2 2836"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path></g><g data-mml-node="mo" transform="translate(600,0)"><path data-c="21" d="M78 661Q78 682 96 699T138 716T180 700T199 661Q199 654 179 432T158 206Q156 198 139 198Q121 198 119 206Q118 209 98 431T78 661ZM79 61Q79 89 97 105T141 121Q164 119 181 104T198 61Q198 31 181 16T139 1Q114 1 97 16T79 61Z"></path></g><g data-mml-node="mo" transform="translate(1155.8,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="munderover" transform="translate(2211.6,0)"><g data-mml-node="mo"><path data-c="220F" d="M220 812Q220 813 218 819T214 829T208 840T199 853T185 866T166 878T140 887T107 893T66 896H56V950H1221V896H1211Q1080 896 1058 812V-311Q1076 -396 1211 -396H1221V-450H725V-396H735Q864 -396 888 -314Q889 -312 889 -311V896H388V292L389 -311Q405 -396 542 -396H552V-450H56V-396H66Q195 -396 219 -314Q220 -312 220 -311V812Z"></path></g><g data-mml-node="TeXAtom" transform="translate(3,-1068.1) scale(0.707)" data-mjx-texclass="ORD"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,-56)"><g data-mml-node="mtd"><g data-mml-node="mi"><path data-c="1D458" d="M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z"></path></g><g data-mml-node="mo" transform="translate(521,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="mn" transform="translate(1299,0)"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></g></g></g></g></g><g data-mml-node="TeXAtom" transform="translate(426.9,1133.4) scale(0.707)" data-mjx-texclass="ORD"><g data-mml-node="mtable"><g data-mml-node="mtr" transform="translate(0,34.5)"><g data-mml-node="mtd"><g data-mml-node="mi"><path data-c="1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path></g></g></g></g></g></g><g data-mml-node="mi" transform="translate(3656.2,0)"><path data-c="1D458" d="M121 647Q121 657 125 670T137 683Q138 683 209 688T282 694Q294 694 294 686Q294 679 244 477Q194 279 194 272Q213 282 223 291Q247 309 292 354T362 415Q402 442 438 442Q468 442 485 423T503 369Q503 344 496 327T477 302T456 291T438 288Q418 288 406 299T394 328Q394 353 410 369T442 390L458 393Q446 405 434 405H430Q398 402 367 380T294 316T228 255Q230 254 243 252T267 246T293 238T320 224T342 206T359 180T365 147Q365 130 360 106T354 66Q354 26 381 26Q429 26 459 145Q461 153 479 153H483Q499 153 499 144Q499 139 496 130Q455 -11 378 -11Q333 -11 305 15T277 90Q277 108 280 121T283 145Q283 167 269 183T234 206T200 217T182 220H180Q168 178 159 139T145 81T136 44T129 20T122 7T111 -2Q98 -11 83 -11Q66 -11 57 -1T48 16Q48 26 85 176T158 471L195 616Q196 629 188 632T149 637H144Q134 637 131 637T124 640T121 647Z"></path></g></g></g></svg></mjx-container></div></td><td id="h2iaaf_225"><div><mjx-container class="MathJax" jax="SVG" display="true"><svg style="vertical-align: -2.149ex;" xmlns="http://www.w3.org/2000/svg" width="28.917ex" height="5.43ex" role="img" focusable="false" viewBox="0 -1450 12781.4 2400"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path></g><g data-mml-node="mo" transform="translate(600,0)"><path data-c="21" d="M78 661Q78 682 96 699T138 716T180 700T199 661Q199 654 179 432T158 206Q156 198 139 198Q121 198 119 206Q118 209 98 431T78 661ZM79 61Q79 89 97 105T141 121Q164 119 181 104T198 61Q198 31 181 16T139 1Q114 1 97 16T79 61Z"></path></g><g data-mml-node="mo" transform="translate(1155.8,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="mrow" transform="translate(2211.6,0)"><g data-mml-node="mo" transform="translate(0 -0.5)"><path data-c="7B" d="M618 -943L612 -949H582L568 -943Q472 -903 411 -841T332 -703Q327 -682 327 -653T325 -350Q324 -28 323 -18Q317 24 301 61T264 124T221 171T179 205T147 225T132 234Q130 238 130 250Q130 255 130 258T131 264T132 267T134 269T139 272T144 275Q207 308 256 367Q310 436 323 519Q324 529 325 851Q326 1124 326 1154T332 1205Q369 1358 566 1443L582 1450H612L618 1444V1429Q618 1413 616 1411L608 1406Q599 1402 585 1393T552 1372T515 1343T479 1305T449 1257T429 1200Q425 1180 425 1152T423 851Q422 579 422 549T416 498Q407 459 388 424T346 364T297 318T250 284T214 264T197 254L188 251L205 242Q290 200 345 138T416 3Q421 -18 421 -48T423 -349Q423 -397 423 -472Q424 -677 428 -694Q429 -697 429 -699Q434 -722 443 -743T465 -782T491 -816T519 -845T548 -868T574 -886T595 -899T610 -908L616 -910Q618 -912 618 -928V-943Z"></path></g><g data-mml-node="mtable" transform="translate(750,0)"><g data-mml-node="mtr" transform="translate(0,700)"><g data-mml-node="mtd"><g data-mml-node="mn"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></g></g><g data-mml-node="mtd" transform="translate(5700.9,0)"><g data-mml-node="mtext"><path data-c="69" d="M69 609Q69 637 87 653T131 669Q154 667 171 652T188 609Q188 579 171 564T129 549Q104 549 87 564T69 609ZM247 0Q232 3 143 3Q132 3 106 3T56 1L34 0H26V46H42Q70 46 91 49Q100 53 102 60T104 102V205V293Q104 345 102 359T88 378Q74 385 41 385H30V408Q30 431 32 431L42 432Q52 433 70 434T106 436Q123 437 142 438T171 441T182 442H185V62Q190 52 197 50T232 46H255V0H247Z"></path><path data-c="66" d="M273 0Q255 3 146 3Q43 3 34 0H26V46H42Q70 46 91 49Q99 52 103 60Q104 62 104 224V385H33V431H104V497L105 564L107 574Q126 639 171 668T266 704Q267 704 275 704T289 705Q330 702 351 679T372 627Q372 604 358 590T321 576T284 590T270 627Q270 647 288 667H284Q280 668 273 668Q245 668 223 647T189 592Q183 572 182 497V431H293V385H185V225Q185 63 186 61T189 57T194 54T199 51T206 49T213 48T222 47T231 47T241 46T251 46H282V0H273Z" transform="translate(278,0)"></path><path data-c="A0" d="" transform="translate(584,0)"></path></g><g data-mml-node="mi" transform="translate(834,0)"><path data-c="1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path></g><g data-mml-node="mo" transform="translate(1711.8,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="mn" transform="translate(2767.6,0)"><path data-c="30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path></g></g></g><g data-mml-node="mtr" transform="translate(0,-700)"><g data-mml-node="mtd"><g data-mml-node="mi"><path data-c="1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path></g><g data-mml-node="mo" transform="translate(822.2,0)"><path data-c="22C5" d="M78 250Q78 274 95 292T138 310Q162 310 180 294T199 251Q199 226 182 208T139 190T96 207T78 250Z"></path></g><g data-mml-node="mo" transform="translate(1322.4,0)"><path data-c="28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path></g><g data-mml-node="mi" transform="translate(1711.4,0)"><path data-c="1D45B" d="M21 287Q22 293 24 303T36 341T56 388T89 425T135 442Q171 442 195 424T225 390T231 369Q231 367 232 367L243 378Q304 442 382 442Q436 442 469 415T503 336T465 179T427 52Q427 26 444 26Q450 26 453 27Q482 32 505 65T540 145Q542 153 560 153Q580 153 580 145Q580 144 576 130Q568 101 554 73T508 17T439 -10Q392 -10 371 17T350 73Q350 92 386 193T423 345Q423 404 379 404H374Q288 404 229 303L222 291L189 157Q156 26 151 16Q138 -11 108 -11Q95 -11 87 -5T76 7T74 17Q74 30 112 180T152 343Q153 348 153 366Q153 405 129 405Q91 405 66 305Q60 285 60 284Q58 278 41 278H27Q21 284 21 287Z"></path></g><g data-mml-node="mo" transform="translate(2533.7,0)"><path data-c="2212" d="M84 237T84 250T98 270H679Q694 262 694 250T679 230H98Q84 237 84 250Z"></path></g><g data-mml-node="mn" transform="translate(3533.9,0)"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></g><g data-mml-node="mo" transform="translate(4033.9,0)"><path data-c="29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></g><g data-mml-node="mo" transform="translate(4422.9,0)"><path data-c="21" d="M78 661Q78 682 96 699T138 716T180 700T199 661Q199 654 179 432T158 206Q156 198 139 198Q121 198 119 206Q118 209 98 431T78 661ZM79 61Q79 89 97 105T141 121Q164 119 181 104T198 61Q198 31 181 16T139 1Q114 1 97 16T79 61Z"></path></g></g><g data-mml-node="mtd" transform="translate(5700.9,0)"><g data-mml-node="mtext"><path data-c="6F" d="M28 214Q28 309 93 378T250 448Q340 448 405 380T471 215Q471 120 407 55T250 -10Q153 -10 91 57T28 214ZM250 30Q372 30 372 193V225V250Q372 272 371 288T364 326T348 362T317 390T268 410Q263 411 252 411Q222 411 195 399Q152 377 139 338T126 246V226Q126 130 145 91Q177 30 250 30Z"></path><path data-c="74" d="M27 422Q80 426 109 478T141 600V615H181V431H316V385H181V241Q182 116 182 100T189 68Q203 29 238 29Q282 29 292 100Q293 108 293 146V181H333V146V134Q333 57 291 17Q264 -10 221 -10Q187 -10 162 2T124 33T105 68T98 100Q97 107 97 248V385H18V422H27Z" transform="translate(500,0)"></path><path data-c="68" d="M41 46H55Q94 46 102 60V68Q102 77 102 91T102 124T102 167T103 217T103 272T103 329Q103 366 103 407T103 482T102 542T102 586T102 603Q99 622 88 628T43 637H25V660Q25 683 27 683L37 684Q47 685 66 686T103 688Q120 689 140 690T170 693T181 694H184V367Q244 442 328 442Q451 442 463 329Q464 322 464 190V104Q464 66 466 59T477 49Q498 46 526 46H542V0H534L510 1Q487 2 460 2T422 3Q319 3 310 0H302V46H318Q379 46 379 62Q380 64 380 200Q379 335 378 343Q372 371 358 385T334 402T308 404Q263 404 229 370Q202 343 195 315T187 232V168V108Q187 78 188 68T191 55T200 49Q221 46 249 46H265V0H257L234 1Q210 2 183 2T145 3Q42 3 33 0H25V46H41Z" transform="translate(889,0)"></path><path data-c="65" d="M28 218Q28 273 48 318T98 391T163 433T229 448Q282 448 320 430T378 380T406 316T415 245Q415 238 408 231H126V216Q126 68 226 36Q246 30 270 30Q312 30 342 62Q359 79 369 104L379 128Q382 131 395 131H398Q415 131 415 121Q415 117 412 108Q393 53 349 21T250 -11Q155 -11 92 58T28 218ZM333 275Q322 403 238 411H236Q228 411 220 410T195 402T166 381T143 340T127 274V267H333V275Z" transform="translate(1445,0)"></path><path data-c="72" d="M36 46H50Q89 46 97 60V68Q97 77 97 91T98 122T98 161T98 203Q98 234 98 269T98 328L97 351Q94 370 83 376T38 385H20V408Q20 431 22 431L32 432Q42 433 60 434T96 436Q112 437 131 438T160 441T171 442H174V373Q213 441 271 441H277Q322 441 343 419T364 373Q364 352 351 337T313 322Q288 322 276 338T263 372Q263 381 265 388T270 400T273 405Q271 407 250 401Q234 393 226 386Q179 341 179 207V154Q179 141 179 127T179 101T180 81T180 66V61Q181 59 183 57T188 54T193 51T200 49T207 48T216 47T225 47T235 46T245 46H276V0H267Q249 3 140 3Q37 3 28 0H20V46H36Z" transform="translate(1889,0)"></path><path data-c="77" d="M90 368Q84 378 76 380T40 385H18V431H24L43 430Q62 430 84 429T116 428Q206 428 221 431H229V385H215Q177 383 177 368Q177 367 221 239L265 113L339 328L333 345Q323 374 316 379Q308 384 278 385H258V431H264Q270 428 348 428Q439 428 454 431H461V385H452Q404 385 404 369Q404 366 418 324T449 234T481 143L496 100L537 219Q579 341 579 347Q579 363 564 373T530 385H522V431H529Q541 428 624 428Q692 428 698 431H703V385H697Q696 385 691 385T682 384Q635 377 619 334L559 161Q546 124 528 71Q508 12 503 1T487 -11H479Q460 -11 456 -4Q455 -3 407 133L361 267Q359 263 266 -4Q261 -11 243 -11H238Q225 -11 220 -3L90 368Z" transform="translate(2281,0)"></path><path data-c="69" d="M69 609Q69 637 87 653T131 669Q154 667 171 652T188 609Q188 579 171 564T129 549Q104 549 87 564T69 609ZM247 0Q232 3 143 3Q132 3 106 3T56 1L34 0H26V46H42Q70 46 91 49Q100 53 102 60T104 102V205V293Q104 345 102 359T88 378Q74 385 41 385H30V408Q30 431 32 431L42 432Q52 433 70 434T106 436Q123 437 142 438T171 441T182 442H185V62Q190 52 197 50T232 46H255V0H247Z" transform="translate(3003,0)"></path><path data-c="73" d="M295 316Q295 356 268 385T190 414Q154 414 128 401Q98 382 98 349Q97 344 98 336T114 312T157 287Q175 282 201 278T245 269T277 256Q294 248 310 236T342 195T359 133Q359 71 321 31T198 -10H190Q138 -10 94 26L86 19L77 10Q71 4 65 -1L54 -11H46H42Q39 -11 33 -5V74V132Q33 153 35 157T45 162H54Q66 162 70 158T75 146T82 119T101 77Q136 26 198 26Q295 26 295 104Q295 133 277 151Q257 175 194 187T111 210Q75 227 54 256T33 318Q33 357 50 384T93 424T143 442T187 447H198Q238 447 268 432L283 424L292 431Q302 440 314 448H322H326Q329 448 335 442V310L329 304H301Q295 310 295 316Z" transform="translate(3281,0)"></path><path data-c="65" d="M28 218Q28 273 48 318T98 391T163 433T229 448Q282 448 320 430T378 380T406 316T415 245Q415 238 408 231H126V216Q126 68 226 36Q246 30 270 30Q312 30 342 62Q359 79 369 104L379 128Q382 131 395 131H398Q415 131 415 121Q415 117 412 108Q393 53 349 21T250 -11Q155 -11 92 58T28 218ZM333 275Q322 403 238 411H236Q228 411 220 410T195 402T166 381T143 340T127 274V267H333V275Z" transform="translate(3675,0)"></path></g></g></g></g><g data-mml-node="mo" transform="translate(10569.9,0) translate(0 250)"></g></g></g></g></svg></mjx-container></div></td></tr><tr id="h2iaaf_212"><th id="h2iaaf_228"><p id="h2iaaf_231">Conversion</p><p id="h2iaaf_232">(to another)</p></th><td id="h2iaaf_229"><p id="h2iaaf_233">More formulaic:</p><p id="h2iaaf_234">The <span id="h2iaaf_235"><i>state</i></span> of an iteration can be passed as arguments.</p></td><td id="h2iaaf_230"><p id="h2iaaf_236">Can be tricky:</p><p id="h2iaaf_237">Find out what state must be maintained by the iterative function.</p></td></tr></tbody></table></div></section><section class="chapter"><h3 id="3-4-mutual-recursion" data-toc="3-4-mutual-recursion">3.4 Mutual Recursion</h3><p id="h2iaaf_238"><span id="h2iaaf_242"><font style="color:#ff8c00">Luhn Algorithm</font></span> - Used to verify credit card numbers.</p><ol class="list _decimal" id="h2iaaf_239" type="1"><li class="list__item" id="h2iaaf_243"><p id="h2iaaf_245">From the rightmost digit, which is the check digit, moving left, double the value of every second digit; if product of this doubling operation is greater than 9 (e.g., <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.186ex;" xmlns="http://www.w3.org/2000/svg" width="10.308ex" height="1.717ex" role="img" focusable="false" viewBox="0 -677 4556 759"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><path data-c="37" d="M55 458Q56 460 72 567L88 674Q88 676 108 676H128V672Q128 662 143 655T195 646T364 644H485V605L417 512Q408 500 387 472T360 435T339 403T319 367T305 330T292 284T284 230T278 162T275 80Q275 66 275 52T274 28V19Q270 2 255 -10T221 -22Q210 -22 200 -19T179 0T168 40Q168 198 265 368Q285 400 349 489L395 552H302Q128 552 119 546Q113 543 108 522T98 479L95 458V455H55V458Z"></path></g><g data-mml-node="mo" transform="translate(722.2,0)"><path data-c="D7" d="M630 29Q630 9 609 9Q604 9 587 25T493 118L389 222L284 117Q178 13 175 11Q171 9 168 9Q160 9 154 15T147 29Q147 36 161 51T255 146L359 250L255 354Q174 435 161 449T147 471Q147 480 153 485T168 490Q173 490 175 489Q178 487 284 383L389 278L493 382Q570 459 587 475T609 491Q630 491 630 471Q630 464 620 453T522 355L418 250L522 145Q606 61 618 48T630 29Z"></path></g><g data-mml-node="mn" transform="translate(1722.4,0)"><path data-c="32" d="M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z"></path></g><g data-mml-node="mo" transform="translate(2500.2,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="mn" transform="translate(3556,0)"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path><path data-c="34" d="M462 0Q444 3 333 3Q217 3 199 0H190V46H221Q241 46 248 46T265 48T279 53T286 61Q287 63 287 115V165H28V211L179 442Q332 674 334 675Q336 677 355 677H373L379 671V211H471V165H379V114Q379 73 379 66T385 54Q393 47 442 46H471V0H462ZM293 211V545L74 212L183 211H293Z" transform="translate(500,0)"></path></g></g></g></svg></mjx-container>), then sum the digits of the products (e.g., 10: <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.186ex;" xmlns="http://www.w3.org/2000/svg" width="9.176ex" height="1.692ex" role="img" focusable="false" viewBox="0 -666 4056 748"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></g><g data-mml-node="mo" transform="translate(722.2,0)"><path data-c="2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path></g><g data-mml-node="mn" transform="translate(1722.4,0)"><path data-c="30" d="M96 585Q152 666 249 666Q297 666 345 640T423 548Q460 465 460 320Q460 165 417 83Q397 41 362 16T301 -15T250 -22Q224 -22 198 -16T137 16T82 83Q39 165 39 320Q39 494 96 585ZM321 597Q291 629 250 629Q208 629 178 597Q153 571 145 525T137 333Q137 175 145 125T181 46Q209 16 250 16Q290 16 318 46Q347 76 354 130T362 333Q362 478 354 524T321 597Z"></path></g><g data-mml-node="mo" transform="translate(2500.2,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="mn" transform="translate(3556,0)"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></g></g></g></svg></mjx-container>, 14: <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.186ex;" xmlns="http://www.w3.org/2000/svg" width="9.176ex" height="1.717ex" role="img" focusable="false" viewBox="0 -677 4056 759"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><path data-c="31" d="M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z"></path></g><g data-mml-node="mo" transform="translate(722.2,0)"><path data-c="2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path></g><g data-mml-node="mn" transform="translate(1722.4,0)"><path data-c="34" d="M462 0Q444 3 333 3Q217 3 199 0H190V46H221Q241 46 248 46T265 48T279 53T286 61Q287 63 287 115V165H28V211L179 442Q332 674 334 675Q336 677 355 677H373L379 671V211H471V165H379V114Q379 73 379 66T385 54Q393 47 442 46H471V0H462ZM293 211V545L74 212L183 211H293Z"></path></g><g data-mml-node="mo" transform="translate(2500.2,0)"><path data-c="3D" d="M56 347Q56 360 70 367H707Q722 359 722 347Q722 336 708 328L390 327H72Q56 332 56 347ZM56 153Q56 168 72 173H708Q722 163 722 153Q722 140 707 133H70Q56 140 56 153Z"></path></g><g data-mml-node="mn" transform="translate(3556,0)"><path data-c="35" d="M164 157Q164 133 148 117T109 101H102Q148 22 224 22Q294 22 326 82Q345 115 345 210Q345 313 318 349Q292 382 260 382H254Q176 382 136 314Q132 307 129 306T114 304Q97 304 95 310Q93 314 93 485V614Q93 664 98 664Q100 666 102 666Q103 666 123 658T178 642T253 634Q324 634 389 662Q397 666 402 666Q410 666 410 648V635Q328 538 205 538Q174 538 149 544L139 546V374Q158 388 169 396T205 412T256 420Q337 420 393 355T449 201Q449 109 385 44T229 -22Q148 -22 99 32T50 154Q50 178 61 192T84 210T107 214Q132 214 148 197T164 157Z"></path></g></g></g></svg></mjx-container>).</p></li><li class="list__item" id="h2iaaf_244"><p id="h2iaaf_249">Take the sum of all the digits. The Luhn sum of a valid credit card number is a multiple of 10.</p></li></ol><figure id="h2iaaf_240"><img alt="Luhn Algorithm" src="Computer-Science-Study-Notes/p3-4-1.png" title="Luhn Algorithm" width="949" height="267"></figure><div class="code-block" data-lang="python">
def luhn_sum(n):
if n < 10:
return n
else:
all_but_last, last = split(n)
return luhn_sum_double(all_but_last) + last
def luhn_sum_double(n):
all_but_last, last = split(n)
luhn_digit = sum_digits(2 * last)
if n < 10:
return luhn_digit
else:
return luhn_sum(all_but_last) + luhn_digit
</div></section></section><section class="chapter"><h2 id="4-iterators-generators" data-toc="4-iterators-generators">4 Iterators & Generators</h2><section class="chapter"><h3 id="4-1-iterators" data-toc="4-1-iterators">4.1 Iterators</h3><p id="h2iaaf_254"><span id="h2iaaf_262"><font style="color:#8a2be2">Definitions:</font></span></p><ol class="list _alpha-lower" id="h2iaaf_255" type="a"><li class="list__item" id="h2iaaf_263"><p id="h2iaaf_265"><span id="h2iaaf_266"><font style="color:#ff8c00">Iterable:</font></span> An object capable of returning its members one at a time.</p></li><li class="list__item" id="h2iaaf_264"><p id="h2iaaf_267"><span id="h2iaaf_268"><font style="color:#ff8c00">Iterator:</font></span> An object that progressively provides access to each item of a collection, in order.</p></li></ol><aside class="prompt" data-type="warning" data-title="" id="h2iaaf_256"><p id="h2iaaf_269">Iterators themselves are iterables!</p></aside><p id="h2iaaf_257"><span id="h2iaaf_270"><font style="color:#8a2be2">Types of iterables:</font></span></p><p id="h2iaaf_258"><span id="h2iaaf_271"><font style="color:#8a2be2">Operations on iterators:</font></span></p><ul class="list _bullet" id="h2iaaf_259"><li class="list__item" id="h2iaaf_272"><p id="h2iaaf_274"><span id="h2iaaf_275"><font style="color:#ff4500">iter</font></span> (iterable): Return an iterator over the elements of an iterable value.</p></li><li class="list__item" id="h2iaaf_273"><p id="h2iaaf_276"><span id="h2iaaf_277"><font style="color:#ff4500">next</font></span> (iterable): Return the next element in an iterator.</p></li></ul><p id="h2iaaf_260"><span id="h2iaaf_278"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-block" data-lang="python">
s = [5, 2, 0]
iterator = iter(s)
item1 = next(iterator) # 5
item2 = next(iterator) # 2
item3 = next(iterator) # 0
item4 = next(iterator) # StopIteration
</div></section><section class="chapter"><h3 id="4-2-iterables" data-toc="4-2-iterables">4.2 Iterables</h3><ul class="list _bullet" id="h2iaaf_279"><li class="list__item" id="h2iaaf_286"><p id="h2iaaf_293">Lists: [1, 2, 3, 4]</p></li><li class="list__item" id="h2iaaf_287"><p id="h2iaaf_294">Tuples: (10, 20, 30)</p></li><li class="list__item" id="h2iaaf_288"><p id="h2iaaf_295">Strings: "Hello"</p></li><li class="list__item" id="h2iaaf_289"><p id="h2iaaf_296">Dictionaries: {"name": "Alice", "age": 30} (iterates over keys by default)</p></li><li class="list__item" id="h2iaaf_290"><p id="h2iaaf_297">Sets: {1, 2, 3}</p></li><li class="list__item" id="h2iaaf_291"><p id="h2iaaf_298">Ranges: range(1, 5)</p></li><li class="list__item" id="h2iaaf_292"><p id="h2iaaf_299">File Objects: Used for reading data from files line by line.</p></li></ul><p id="h2iaaf_280"><span id="h2iaaf_300"><font style="color:#8a2be2">Special case: Dictionaries</font></span></p><ul class="list _bullet" id="h2iaaf_281"><li class="list__item" id="h2iaaf_301"><p id="h2iaaf_303">The order of items of a dictionary is the order in which they were added (Python 3.6+).</p></li><li class="list__item" id="h2iaaf_302"><p id="h2iaaf_304">Historically, items appeared in an arbitrary order (Python 3.5 and earlier).</p></li></ul><p id="h2iaaf_282"><span id="h2iaaf_305"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="# Iterate keys">
# Iterate keys
d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux":
"Open Source"}
k = iter(d.keys()) # or iter(d)
print(next(k)) # MacOS
# Iterate values
v = iter(d.values())
print(next(v)) # Apple
# Iterate items
i = iter(d.items())
print(next(i)) # ('MacOS', 'Apple')
</div><aside class="prompt" data-type="note" data-title="" id="h2iaaf_284"><p id="h2iaaf_306">During iteration, you can't change the size of dictionary, aka change the structure of it, which may initiate runtime error; you can, however, change the value of the key.</p></aside><div class="code-comparer" id="h2iaaf_285" data-comparing="horizontally"><div class="code-block" data-lang="python" data-title="change the size">
d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux": "Open Source"}
k = iter(d.values())
print(next(k)) # Apple
d["Android"] = "Google"
print(next(k)) # RuntimeError: dictionary changed size during iteration
</div><div class="code-collapse" data-lang="python" data-title="change the key" data-is-expanded="false" data-synopsis="d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux": "Open Source"}">
d = {"MacOS": "Apple", "Windows": "Microsoft", "Linux": "Open Source"}
k = iter(d.values())
print(next(k)) # Apple
d["Windows"] = "Microsoft Corporation"
print(next(k)) # Microsoft Corporation
</div></div></section><section class="chapter"><h3 id="4-3-generators" data-toc="4-3-generators">4.3 Generators</h3><p id="h2iaaf_309"><span id="h2iaaf_320"><font style="color:#8a2be2">Definitions:</font></span></p><ol class="list _alpha-lower" id="h2iaaf_310" type="a"><li class="list__item" id="h2iaaf_321"><p id="h2iaaf_323"><span id="h2iaaf_324"><font style="color:#ff8c00">Generator:</font></span> A function that <span id="h2iaaf_325"><font style="color:#ff4500">yields</font></span> value instead of <span id="h2iaaf_326"><font style="color:#ff4500">returning</font></span> them.</p></li><li class="list__item" id="h2iaaf_322"><p id="h2iaaf_327"><span id="h2iaaf_328"><font style="color:#ff8c00">Generator:</font></span> An iterator created automatically by calling a generator function.</p></li></ol><aside class="prompt" data-type="note" data-title="" id="h2iaaf_311"><p id="h2iaaf_329">A normal function returns once; a generator function can yield multiple times.</p></aside><p id="h2iaaf_312"><span id="h2iaaf_330"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-collapse" data-lang="python" data-is-expanded="false" data-synopsis="def even(start, end):">
def even(start, end):
current = start + (start % 2)
while current <= end:
yield current
current += 2
lst1 = list(even(1, 10)) # [2, 4, 6, 8, 10]
t = even(1, 10)
item1 = next(t) # 2
item2 = next(t) # 4
</div><p id="h2iaaf_314"><span id="h2iaaf_331"><font style="color:#8a2be2">Generators can yield form iterators:</font></span></p><p id="h2iaaf_315">A <span id="h2iaaf_332"><font style="color:#ff4500">yield from</font></span> statement yields all values from an iterator or iterable (Python 3.3).</p><p id="h2iaaf_316">Example 1:</p><div class="code-comparer" id="h2iaaf_317" data-comparing="vertically"><div class="code-block" data-lang="python" data-title="yield">
def a_then_b(a, b):
for x in a:
yield x
for x in b:
yield x
</div><div class="code-block" data-lang="python" data-title="yield from">
def a_then_b(a, b):
yield from a
yield from b
</div></div><p id="h2iaaf_318">Example 2:</p><div class="code-comparer" id="h2iaaf_319" data-comparing="horizontally"><div class="code-block" data-lang="python" data-title="yield">
def countdown(k):
if k > 0:
yield k
yield countdown(k - 1)
t = countdown(3)
item1 = next(t) # 3
item2 = next(t) # <generator object countdown at 0x0000021D7D3D3F90>
</div><div class="code-block" data-lang="python" data-title="yield from">
def countdown(k):
if k > 0:
yield k
yield from countdown(k - 1)
t = countdown(3)
item1 = next(t) # 3
item2 = next(t) # 2
</div></div></section><section class="chapter"><h3 id="4-4-built-in-iterator-functions" data-toc="4-4-built-in-iterator-functions">4.4 Built-In Iterator Functions</h3><p id="h2iaaf_337">Many built-in Python sequence operations return iterators that compute results lazily.</p><p id="h2iaaf_338">To view the contents of an iterator, place the resulting elements into a container.</p><ul class="list _bullet" id="h2iaaf_339"><li class="list__item" id="h2iaaf_345"><p id="h2iaaf_348"><span id="h2iaaf_349"><font style="color:#ff4500">list</font></span> (iterable): Create a list containing all x in iterable.</p></li><li class="list__item" id="h2iaaf_346"><p id="h2iaaf_350"><span id="h2iaaf_351"><font style="color:#ff4500">tuple</font></span> (iterable): Create a tuple containing all x in iterable.</p></li><li class="list__item" id="h2iaaf_347"><p id="h2iaaf_352"><span id="h2iaaf_353"><font style="color:#ff4500">sorted</font></span> (iterable): Create a sorted list containing x in iterable.</p></li></ul><section class="chapter"><h4 id="4-4-1-map" data-toc="4-4-1-map">4.4.1 Map</h4><p id="h2iaaf_354"><span id="h2iaaf_357"><font style="color:#ff4500">map</font></span> (func, iterable): Iterate over func(x) for x in iterable.</p><p id="h2iaaf_355"><span id="h2iaaf_358"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-block" data-lang="python">
def square(x):
return x * x
numbers = [1, 2, 3, 4]
squared_numbers = map(square, numbers) # map object (iterator)
item1 = next(squared_numbers) # 1
</div></section><section class="chapter"><h4 id="4-4-2-filter" data-toc="4-4-2-filter">4.4.2 Filter</h4><p id="h2iaaf_359"><span id="h2iaaf_362"><font style="color:#ff4500">filter</font></span> (func, iterable): Iterate over x in iterable if func(x).</p><p id="h2iaaf_360"><span id="h2iaaf_363"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-block" data-lang="python">
def square(x):
return x * x
def is_even(x):
return x % 2 == 0
numbers = [1, 2, 3, 4]
even_numbers = filter(is_even, numbers) # filter object (iterator)
</div></section><section class="chapter"><h4 id="4-4-3-zip" data-toc="4-4-3-zip">4.4.3 zip</h4><p id="h2iaaf_364"><span id="h2iaaf_370"><font style="color:#ff4500">zip</font></span> (first_iter, second_iter, ...): Iterate over co-indexed (x, y) pairs.</p><p id="h2iaaf_365"><span id="h2iaaf_371"><font style="color:#8a2be2">Example usage:</font></span></p><p id="h2iaaf_366">Example 1:</p><div class="code-block" data-lang="python">
list(zip([1, 2], [3, 4, 5], [6, 7])) # [(1, 3, 6), (2, 4, 7)]
</div><p id="h2iaaf_368">Example 2:</p><div class="code-block" data-lang="python">
def palindrome(s):
return all(a == b for a, b in zip(s, reversed(s)))
</div></section><section class="chapter"><h4 id="4-4-4-reversed" data-toc="4-4-4-reversed">4.4.4 reversed</h4><p id="h2iaaf_372"><span id="h2iaaf_375"><font style="color:#ff4500">reversed</font></span> (sequence): Iterate over x in a sequence in reverse order.</p><p id="h2iaaf_373"><span id="h2iaaf_376"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-block" data-lang="python">
t = [1, 2, 3, 2, 1]
print(reverse(t) == t) # False
# Because reversed(t) is a list_reverseiterator object
print(list(reversed(t) == t) # True
</div></section><section class="chapter"><h4 id="4-4-5-range-iterator" data-toc="4-4-5-range-iterator">4.4.5 range iterator</h4><p id="h2iaaf_377"><span id="h2iaaf_379"><font style="color:#8a2be2">Example usage:</font></span></p><div class="code-block" data-lang="python">
r = range(3, 6)
ri = iter(r) # range_iterator object
for i in ri:
print(i)
# 3
# 4
# 5
</div></section></section></section><section class="chapter"><h2 id="5-efficiency" data-toc="5-efficiency">5 Efficiency</h2><section class="chapter"><h3 id="5-1-order-of-growth" data-toc="5-1-order-of-growth">5.1 Order of Growth</h3><p id="h2iaaf_382">For more information on order of growth, please refer to <a href="data-structures-and-algorithms.html#Growth" id="h2iaaf_383" data-tooltip="Order of Growth">Data Structures and Algorithms 1</a>.</p></section><section class="chapter"><h3 id="5-2-space" data-toc="5-2-space">5.2 Space</h3><ul class="list _bullet" id="h2iaaf_384"><li class="list__item" id="h2iaaf_385"><p id="h2iaaf_388">At any moment there is a set of active environments. Values and frames in active environments consume memory.</p></li><li class="list__item" id="h2iaaf_386"><p id="h2iaaf_389">Memory that is used for other values and frames can be recycled.</p></li><li class="list__item" id="h2iaaf_387"><p id="h2iaaf_390"><span id="h2iaaf_392"><font style="color:#ff00ff">Active Environments:</font></span></p><ul class="list _bullet" id="h2iaaf_391"><li class="list__item" id="h2iaaf_393"><p id="h2iaaf_395">Environments for any function calls currently being evaluated => call the function but hasn't returned yet.</p></li><li class="list__item" id="h2iaaf_394"><p id="h2iaaf_396">Parent environments of functions named in active environments => define a function in another function, so the function defined is not in the global frame, the parent frame is needed.</p></li></ul></li></ul></section></section><section class="chapter"><h2 id="6-object-oriented-programming" data-toc="6-object-oriented-programming">6 Object-Oriented Programming</h2><section class="chapter"><h3 id="6-1-object-oriented-programming-in-python" data-toc="6-1-object-oriented-programming-in-python">6.1 Object-Oriented Programming in Python</h3><p id="h2iaaf_400">For more information about the details of Object-Oriented Programming, refer to <a href="c-programming.html#object" id="h2iaaf_405" data-tooltip="Object-Oriented Programming">Object-Oriented Programming in C++</a>.</p><aside class="prompt" data-type="note" data-title="" id="h2iaaf_401"><p id="h2iaaf_406">The following content is details of OOP in Python.</p></aside><aside class="prompt" data-type="warning" data-title="" id="h2iaaf_402"><p id="h2iaaf_407">In Python, every value is an object!</p></aside><div class="code-block" data-lang="python">
class Account:
# _init_ is a special method name for the function that constructs
# an Account instance
def __init__(self, account_holder):
self.balance = 0
self.holder = account_holder
# self is the instance of the Account class on which deposit was
# invoked
def deposit(self, amount):
self.balance = self.balance + amount
return self.balance
def withdraw(self, amount):
if amount > self.balance:
return "Insufficient funds"
self.balance = self.balance - amount
return self.balance
a = Account("Nate")
a.deposit(100)
a.withdraw(50)
print(a.balance) # 50
</div><ol class="list _alpha-lower" id="h2iaaf_404" type="a"><li class="list__item" id="h2iaaf_408"><p id="h2iaaf_410">When a class is called:</p><ul class="list _bullet" id="h2iaaf_411"><li class="list__item" id="h2iaaf_412"><p id="h2iaaf_416">A new instance of that class (aka an object) is created.</p></li><li class="list__item" id="h2iaaf_413"><p id="h2iaaf_417">The <span id="h2iaaf_418"><font style="color:#ff4500">_init_</font></span> method of the class is called with the new object as its first argument (named <span id="h2iaaf_419"><font style="color:#ff4500">self</font></span>), along with any additional arguments provided in the call expression.</p></li><li class="list__item" id="h2iaaf_414"><p id="h2iaaf_420">An object's attributes can be accessed and modified using dot expressions.</p></li><li class="list__item" id="h2iaaf_415"><p id="h2iaaf_421">Every object that is an instance of a class has a unique identity.</p></li></ul></li><li class="list__item" id="h2iaaf_409"><p id="h2iaaf_422">All invoked methods have access to the object via the self parameter, and so they can all access and manipulate the object's attributes.</p></li></ol></section><section class="chapter"><h3 id="6-2-inheritance" data-toc="6-2-inheritance">6.2 Inheritance</h3><p id="h2iaaf_423">For more information about inheritance, please visit <a href="c-programming.html#inheritance" id="h2iaaf_424" data-tooltip="Object-Oriented Programming">Object-Oriented Programming in C++</a>.</p></section><section class="chapter"><h3 id="6-3-special-method-functions" data-toc="6-3-special-method-functions">6.3 Special Method Functions</h3><p id="h2iaaf_425">Certain names are special because they have built-in behavior.</p><p id="h2iaaf_426">These names always start and end with two underscores.</p><ol class="list _decimal" id="h2iaaf_427" type="1"><li class="list__item" id="h2iaaf_428"><p><span id="h2iaaf_433"><font style="color:#ff00ff">__init__</font></span> Method invoked automatically when an object is constructed</p></li><li class="list__item" id="h2iaaf_429"><p><span id="h2iaaf_434"><font style="color:#ff00ff">__repr__</font></span> Method invoked to display an object as a Python expression</p></li><li class="list__item" id="h2iaaf_430"><p><span id="h2iaaf_435"><font style="color:#ff00ff">__add__</font></span> Method invoked to add one object to another</p></li><li class="list__item" id="h2iaaf_431"><p><span id="h2iaaf_436"><font style="color:#ff00ff">__bool__</font></span> Method invoked to convert an object to True or False.</p></li><li class="list__item" id="h2iaaf_432"><p><span id="h2iaaf_437"><font style="color:#ff00ff">__float__</font></span> Method invoked to convert an object to a float (real number).</p></li></ol></section></section><section class="chapter"><h2 id="7-scheme" data-toc="7-scheme">7 Scheme</h2><section class="chapter"><h3 id="7-1-scheme-fundamentals" data-toc="7-1-scheme-fundamentals">7.1 Scheme Fundamentals</h3><p id="h2iaaf_440">Scheme programs consist of expressions, which can be:</p><ul class="list _bullet" id="h2iaaf_441"><li class="list__item" id="h2iaaf_459"><p>Primitive expressions: 2, 3.3, true, +, quotient...</p></li><li class="list__item" id="h2iaaf_460"><p>Combinations: (quotient 10 2), (not true)...</p></li></ul><p id="h2iaaf_442">Numbers are self-evaluating; symbols are bound to values.</p><p id="h2iaaf_443">Call expressions include an operator and 0 or more operands in parenthesis.</p><p id="h2iaaf_444"><span id="h2iaaf_461"><font style="color:#8a2be2">Example:</font></span></p><div class="code-block" data-lang="none">
(quotient 10 2) ; 5
(- (* 3 5) (+ 10 1)) ; 14
(- (* 2 2 3)
(+ 3 2 1)) ; 9
(number? 3) ; #t
</div><p id="h2iaaf_446"><span id="h2iaaf_462"><font style="color:#8a2be2">Special forms:</font></span></p><p id="h2iaaf_447"><span id="h2iaaf_463"><font style="color:#ff4500">Special forms:</font></span> A combination taht is not a call expression is a <span id="h2iaaf_464"><i>special form</i></span>:</p><ul class="list _bullet" id="h2iaaf_448"><li class="list__item" id="h2iaaf_465"><p><span id="h2iaaf_470"><font style="color:#ff00ff"><span id="h2iaaf_471"><b>If</b></span> statement :</font></span> (if <predicate> <consequent> <alternative >)</p></li><li class="list__item" id="h2iaaf_466"><p><span id="h2iaaf_472"><font style="color:#ff00ff"><span id="h2iaaf_477"><b>And</b></span> and <span id="h2iaaf_478"><b>or</b></span>:</font></span> (and <e <sub class="subscript" id="h2iaaf_473">1</sub> > ... <e <sub class="subscript" id="h2iaaf_474">n</sub> >), (or <e <sub class="subscript" id="h2iaaf_475">1</sub> > ... <e <sub class="subscript" id="h2iaaf_476">n</sub> >)</p></li><li class="list__item" id="h2iaaf_467"><p><span id="h2iaaf_479"><font style="color:#ff00ff">Binding symbols:</font></span> (define < symbol> <expression>)</p></li><li class="list__item" id="h2iaaf_468"><p><span id="h2iaaf_480"><font style="color:#ff00ff">New procedures:</font></span> (define < symbol> <formal parameters>) <body></p></li><li class="list__item" id="h2iaaf_469"><p><span id="h2iaaf_481"><font style="color:#ff00ff">Lambda Expressions:</font></span> (lambda (<formal-parameters>) <body></p></li></ul><p id="h2iaaf_449"><span id="h2iaaf_482"><font style="color:#8a2be2">Examples:</font></span></p><div class="code-block" data-lang="none">
(define pi 3.14)
(define (abs x)
(if (>= x 0)
x
(- x)))
</div><div class="code-comparer" id="h2iaaf_451" data-comparing="vertically"><div class="code-block" data-lang="none" data-title="Procedure">
(define (plus4 x) (+ x 4))
</div><div class="code-block" data-lang="none" data-title="Lambda Expressions">
(define plus4 (lambda (x) (+ x 4)))
</div></div><p id="h2iaaf_452"><span id="h2iaaf_485"><font style="color:#8a2be2">Cond & Begin:</font></span></p><p id="h2iaaf_453"><span id="h2iaaf_486"><font style="color:#ff00ff">Cond</font></span></p><div class="code-comparer" id="h2iaaf_454" data-comparing="vertically"><div class="code-block" data-lang="python" data-title="if-elif-else in Python">
if x > 10:
print("big")
elif x > 5:
print("medium")
else:
print("small")
</div><div class="code-block" data-lang="none" data-title="Cond in Scheme">
(cond ((> x 10) (print 'big))
((> x 5) (print 'medium))
(else (print 'small)))
</div></div><p id="h2iaaf_455"><span id="h2iaaf_489"><font style="color:#ff00ff">Begin</font></span></p><div class="code-comparer" id="h2iaaf_456" data-comparing="vertically"><div class="code-block" data-lang="python" data-title="Python">
if x > 10:
print("big")
print("guy")
else:
print("small")
print("fry")
</div><div class="code-block" data-lang="none" data-title="Scheme">
(if (> x 10)
(begin
(print 'big)
(print 'guy))
(begin
(print 'small)
(print 'fry)))
</div></div><p id="h2iaaf_457"><span id="h2iaaf_492"><font style="color:#8a2be2">Let:</font></span></p><div class="code-comparer" id="h2iaaf_458" data-comparing="vertically"><div class="code-block" data-lang="python" data-title="Bound in Python">
a = 3
b = 2 + 2
c = math.sqrt(a * a + b * b)
</div><div class="code-block" data-lang="none" data-title="Not Bound in
Scheme">
(let ((a 3)
(b (+ 2 2)))
(sqrt (+ (* a a) (* b b))))
</div></div></section><section class="chapter"><h3 id="7-2-scheme-lists" data-toc="7-2-scheme-lists">7.2 Scheme Lists</h3><ul class="list _bullet" id="h2iaaf_495"><li class="list__item" id="h2iaaf_501"><p id="h2iaaf_505"><span id="h2iaaf_506"><font style="color:#ff00ff">cons:</font></span> Two-argument procedure that creates a linked list.</p></li><li class="list__item" id="h2iaaf_502"><p id="h2iaaf_507"><span id="h2iaaf_508"><font style="color:#ff00ff">car:</font></span> Procedure that returns the first element of the list.</p></li><li class="list__item" id="h2iaaf_503"><p id="h2iaaf_509"><span id="h2iaaf_510"><font style="color:#ff00ff">cdr:</font></span> Procedure that returns the rest of a list.</p></li><li class="list__item" id="h2iaaf_504"><p id="h2iaaf_511"><span id="h2iaaf_512"><font style="color:#ff00ff">nil:</font></span> The empty list.</p></li></ul><div class="code-block" data-lang="none">
(cons 1 (cons 2 (cons 3 nil))) ; (1 2 3)
</div><p id="h2iaaf_497"><span id="h2iaaf_513"><font style="color:#8a2be2">Symbolic programming:</font></span></p><div class="code-block" data-lang="none">
(define a 1)
(define b 2)
(list a b) ; (1 2)
(list 'a 'b) ; (a b)
</div><p id="h2iaaf_499"><span id="h2iaaf_514"><font style="color:#8a2be2">Built-In List Processing Procedures</font></span></p><ul class="list _bullet" id="h2iaaf_500"><li class="list__item" id="h2iaaf_515"><p id="h2iaaf_519"><span id="h2iaaf_520"><font style="color:#ff00ff">(append s t):</font></span> list the elements of s and t; append can be called on more than 2 lists.</p></li><li class="list__item" id="h2iaaf_516"><p id="h2iaaf_521"><span id="h2iaaf_522"><font style="color:#ff00ff">(map f s):</font></span> call a procedure f on each element of a list s and list the results.</p></li><li class="list__item" id="h2iaaf_517"><p id="h2iaaf_523"><span id="h2iaaf_524"><font style="color:#ff00ff">(filter f s):</font></span> call a procedure f on each element of a list s and list the elements for which a true value is the result.</p></li><li class="list__item" id="h2iaaf_518"><p id="h2iaaf_525"><span id="h2iaaf_526"><font style="color:#ff00ff">(apply f s):</font></span> call a procedure f with the elements of a list as its arguments.</p></li></ul></section></section><div class="last-modified">Last modified: 14 November 2024</div><div data-feedback-placeholder="true"></div><div class="navigation-links _bottom"><a href="operating-system.html" class="navigation-links__prev">Operating System</a><a href="rust-programming.html" class="navigation-links__next">Rust Programming</a></div></article><div id="disqus_thread"></div></div></section></main></div><script src="https://resources.jetbrains.com/writerside/apidoc/6.10.0-b518/app.js"></script></body></html>