-
Notifications
You must be signed in to change notification settings - Fork 14
/
08-AdvancedFunctions.html
85 lines (79 loc) · 33.5 KB
/
08-AdvancedFunctions.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
<html><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta charset="utf-8">
<title>08-AdvancedFunctions</title>
<script type="text/javascript" src="08-AdvancedFunctions_files/MathJax.js" charset="utf-8"></script>
<script type="text/javascript">
// MathJax disabled, set as null to distingish from *missing* MathJax,
// where it will be undefined, and should prompt a dialog later.
window.mathjax_url = "mathjax/MathJax.js";
</script>
<link rel="stylesheet" href="08-AdvancedFunctions_files/jquery-wijmo.css" type="text/css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/codemirror.css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/markdown.css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/rst.css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/ipython.css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/default.css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/prettify.css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/boilerplate.css" type="text/css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/layout.css" type="text/css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/base.css" type="text/css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/notebook.css" type="text/css">
<link rel="stylesheet" href="08-AdvancedFunctions_files/renderedhtml.css" type="text/css">
<meta name="read_only" content="False">
<style type="text/css">#MathJax_Zoom {position: absolute; background-color: #F0F0F0; overflow: auto; display: block; z-index: 301; padding: .5em; border: 1px solid black; margin: 0; font-family: serif; font-size: 85%; font-weight: normal; font-style: normal; text-align: left; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; box-shadow: 5px 5px 15px #AAAAAA; -webkit-box-shadow: 5px 5px 15px #AAAAAA; -moz-box-shadow: 5px 5px 15px #AAAAAA; -khtml-box-shadow: 5px 5px 15px #AAAAAA; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
#MathJax_ZoomOverlay {position: absolute; left: 0; top: 0; z-index: 300; display: inline-block; width: 100%; height: 100%; border: 0; padding: 0; margin: 0; background-color: white; opacity: 0; filter: alpha(opacity=0)}
</style><style type="text/css">#MathJax_About {position: fixed; left: 50%; width: auto; text-align: center; border: 3px outset; padding: 1em 2em; background-color: #DDDDDD; cursor: default; font-family: message-box; font-size: 120%; font-style: normal; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; z-index: 201; border-radius: 15px; -webkit-border-radius: 15px; -moz-border-radius: 15px; -khtml-border-radius: 15px; box-shadow: 0px 10px 20px #808080; -webkit-box-shadow: 0px 10px 20px #808080; -moz-box-shadow: 0px 10px 20px #808080; -khtml-box-shadow: 0px 10px 20px #808080; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
.MathJax_Menu {position: absolute; background-color: white; color: black; width: auto; padding: 5px 0px; border: 1px solid #CCCCCC; margin: 0; cursor: default; font: menu; text-align: left; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; z-index: 201; border-radius: 5px; -webkit-border-radius: 5px; -moz-border-radius: 5px; -khtml-border-radius: 5px; box-shadow: 0px 10px 20px #808080; -webkit-box-shadow: 0px 10px 20px #808080; -moz-box-shadow: 0px 10px 20px #808080; -khtml-box-shadow: 0px 10px 20px #808080; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
.MathJax_MenuItem {padding: 1px 2em; background: transparent}
.MathJax_MenuTitle {background-color: #CCCCCC; margin: -5px 0 0 0; text-align: center; font-style: italic; font-size: 80%; color: #444444; padding: 2px 0; overflow: hidden}
.MathJax_MenuArrow {position: absolute; right: .5em; color: #666666}
.MathJax_MenuActive .MathJax_MenuArrow {color: white}
.MathJax_MenuCheck {position: absolute; left: .7em}
.MathJax_MenuRadioCheck {position: absolute; left: .7em}
.MathJax_MenuLabel {padding: 1px 2em 3px 1.33em; font-style: italic}
.MathJax_MenuRule {border-top: 1px solid #DDDDDD; margin: 4px 3px}
.MathJax_MenuDisabled {color: GrayText}
.MathJax_MenuActive {background-color: #606872; color: white}
</style><style type="text/css">#MathJax_Message {position: fixed; left: 1px; bottom: 2px; background-color: #E6E6E6; border: 1px solid #959595; margin: 0px; padding: 2px 8px; z-index: 102; color: black; font-size: 80%; width: auto; white-space: nowrap}
#MathJax_MSIE_Frame {position: absolute; top: 0; left: 0; width: 0px; z-index: 101; border: 0px; margin: 0px; padding: 0px}
.MathJax_Error {color: #CC0000; font-style: italic}
</style><style type="text/css">@media print { body { overflow: visible !important; } }.ui-widget-content { border: 0px; }</style><style type="text/css">#MathJax_Zoom {position: absolute; background-color: #F0F0F0; overflow: auto; display: block; z-index: 301; padding: .5em; border: 1px solid black; margin: 0; font-family: serif; font-size: 85%; font-weight: normal; font-style: normal; text-align: left; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; box-shadow: 5px 5px 15px #AAAAAA; -webkit-box-shadow: 5px 5px 15px #AAAAAA; -moz-box-shadow: 5px 5px 15px #AAAAAA; -khtml-box-shadow: 5px 5px 15px #AAAAAA; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
#MathJax_ZoomOverlay {position: absolute; left: 0; top: 0; z-index: 300; display: inline-block; width: 100%; height: 100%; border: 0; padding: 0; margin: 0; background-color: white; opacity: 0; filter: alpha(opacity=0)}
</style><style type="text/css">#MathJax_About {position: fixed; left: 50%; width: auto; text-align: center; border: 3px outset; padding: 1em 2em; background-color: #DDDDDD; cursor: default; font-family: message-box; font-size: 120%; font-style: normal; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; z-index: 201; border-radius: 15px; -webkit-border-radius: 15px; -moz-border-radius: 15px; -khtml-border-radius: 15px; box-shadow: 0px 10px 20px #808080; -webkit-box-shadow: 0px 10px 20px #808080; -moz-box-shadow: 0px 10px 20px #808080; -khtml-box-shadow: 0px 10px 20px #808080; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
.MathJax_Menu {position: absolute; background-color: white; color: black; width: auto; padding: 5px 0px; border: 1px solid #CCCCCC; margin: 0; cursor: default; font: menu; text-align: left; text-indent: 0; text-transform: none; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; z-index: 201; border-radius: 5px; -webkit-border-radius: 5px; -moz-border-radius: 5px; -khtml-border-radius: 5px; box-shadow: 0px 10px 20px #808080; -webkit-box-shadow: 0px 10px 20px #808080; -moz-box-shadow: 0px 10px 20px #808080; -khtml-box-shadow: 0px 10px 20px #808080; filter: progid:DXImageTransform.Microsoft.dropshadow(OffX=2, OffY=2, Color='gray', Positive='true')}
.MathJax_MenuItem {padding: 1px 2em; background: transparent}
.MathJax_MenuTitle {background-color: #CCCCCC; margin: -5px 0 0 0; text-align: center; font-style: italic; font-size: 80%; color: #444444; padding: 2px 0; overflow: hidden}
.MathJax_MenuArrow {position: absolute; right: .5em; color: #666666}
.MathJax_MenuActive .MathJax_MenuArrow {color: white}
.MathJax_MenuCheck {position: absolute; left: .7em}
.MathJax_MenuRadioCheck {position: absolute; left: .7em}
.MathJax_MenuLabel {padding: 1px 2em 3px 1.33em; font-style: italic}
.MathJax_MenuRule {border-top: 1px solid #DDDDDD; margin: 4px 3px}
.MathJax_MenuDisabled {color: GrayText}
.MathJax_MenuActive {background-color: #606872; color: white}
</style><style type="text/css">#MathJax_Message {position: fixed; left: 1px; bottom: 2px; background-color: #E6E6E6; border: 1px solid #959595; margin: 0px; padding: 2px 8px; z-index: 102; color: black; font-size: 80%; width: auto; white-space: nowrap}
#MathJax_MSIE_Frame {position: absolute; top: 0; left: 0; width: 0px; z-index: 101; border: 0px; margin: 0px; padding: 0px}
.MathJax_Error {color: #CC0000; font-style: italic}
</style></head><body style="overflow: auto;"><div tabindex="2" class="cell text_cell border-box-sizing ui-widget-content ui-corner-all"><div style="display: none;" class="text_cell_input"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-default"><div style="position: relative; height: 4px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre>x</pre></div><div style="position: relative"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative" draggable="true"><pre class="CodeMirror-cursor"> </pre><div></div></div></div></div></div></div></div></div><div tabindex="-1" class="text_cell_render rendered_html"><h1>Advanced Functions</h1>
<p>We can write a function that calls another function, even itself. When a function calls itself,
this is referred to as <em>recursion</em>:</p></div></div><div tabindex="2" class="cell border-box-sizing code_cell vbox"><div class="input hbox"><div class="prompt input_prompt">In [13]:</div><div class="input_area box-flex1"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px; top: 0px; left: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-ipython"><div style="position: relative; height: 135px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre><span> print 'Call recursive_adder(%r, *%r)' % (first, rest)</span></pre></div><div style="position: relative; top: 0px;"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative;" draggable="true"><pre style="top: 0px; left: 0px;" class="CodeMirror-cursor"> </pre><div style=""><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">recursive_adder</span><span class="cm-null">(</span><span class="cm-variable">first</span><span class="cm-null">, </span><span class="cm-operator">*</span><span class="cm-variable">rest</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">print</span><span class="cm-null"> </span><span class="cm-string">'Call recursive_adder(%r, *%r)'</span><span class="cm-null"> </span><span class="cm-operator">%</span><span class="cm-null"> (</span><span class="cm-variable">first</span><span class="cm-null">, </span><span class="cm-variable">rest</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">if</span><span class="cm-null"> </span><span class="cm-variable">rest</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">first</span><span class="cm-null"> </span><span class="cm-operator">+</span><span class="cm-null"> </span><span class="cm-variable">recursive_adder</span><span class="cm-null">(</span><span class="cm-operator">*</span><span class="cm-variable">rest</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">else</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">first</span></pre><pre><span class="cm-variable">recursive_adder</span><span class="cm-null">(</span><span class="cm-number">1</span><span class="cm-null">,</span><span class="cm-number">2</span><span class="cm-null">,</span><span class="cm-number">3</span><span class="cm-null">)</span></pre></div></div></div></div></div></div></div></div></div><div style="display: -moz-box;" class="output vbox"><div class="hbox output_area"><div class="prompt"></div><div class="box_flex1 output_subarea output_text output_stream output_stdout"><pre>Call recursive_adder(1, *(2, 3))
Call recursive_adder(2, *(3,))
Call recursive_adder(3, *())</pre></div></div><div class="hbox output_area"><div class="prompt output_prompt">Out[13]:</div><div class="box_flex1 output_subarea output_text"><pre>6</pre></div></div></div></div><div tabindex="2" class="cell text_cell border-box-sizing"><div style="display: none;" class="text_cell_input"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-default"><div style="position: relative; height: 2px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre>x</pre></div><div style="position: relative"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative" draggable="true"><pre class="CodeMirror-cursor"> </pre><div></div></div></div></div></div></div></div></div><div tabindex="-1" class="text_cell_render rendered_html"><p>Functions are just regular Python objects (they are so-called <em>first class</em> functions). This
means that they can be passed as arguments to other functions or assigned variable names:</p></div></div><div tabindex="2" class="cell border-box-sizing code_cell vbox"><div class="input hbox"><div class="prompt input_prompt">In [14]:</div><div class="input_area box-flex1"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px; top: 0px; left: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-ipython"><div style="position: relative; height: 188px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre><span> result.append(mapf(item))</span></pre></div><div style="position: relative; top: 0px;"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative;" draggable="true"><pre style="top: 0px; left: 0px;" class="CodeMirror-cursor"> </pre><div style=""><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">doubler</span><span class="cm-null">(</span><span class="cm-variable">a</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">a</span><span class="cm-null"> </span><span class="cm-operator">*</span><span class="cm-null"> </span><span class="cm-number">2</span></pre><pre> </pre><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">my_map</span><span class="cm-null">(</span><span class="cm-variable">mapf</span><span class="cm-null">, </span><span class="cm-variable">sequence</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> = []</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">for</span><span class="cm-null"> </span><span class="cm-variable">item</span><span class="cm-null"> </span><span class="cm-operator">in</span><span class="cm-null"> </span><span class="cm-variable">sequence</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result.append</span><span class="cm-null">(</span><span class="cm-variable">mapf</span><span class="cm-null">(</span><span class="cm-variable">item</span><span class="cm-null">))</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">result</span></pre><pre> </pre><pre><span class="cm-variable">my_map</span><span class="cm-null">(</span><span class="cm-variable">doubler</span><span class="cm-null">, [</span><span class="cm-number">1</span><span class="cm-null">,</span><span class="cm-number">2</span><span class="cm-null">,</span><span class="cm-number">3</span><span class="cm-null">])</span></pre></div></div></div></div></div></div></div></div></div><div style="display: -moz-box;" class="output vbox"><div class="hbox output_area"><div class="prompt output_prompt">Out[14]:</div><div class="box_flex1 output_subarea output_text"><pre>[2, 4, 6]</pre></div></div></div></div><div tabindex="2" class="cell text_cell border-box-sizing"><div style="display: none;" class="text_cell_input"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-default"><div style="position: relative; height: 2px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre>x</pre></div><div style="position: relative"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative" draggable="true"><pre class="CodeMirror-cursor"> </pre><div></div></div></div></div></div></div></div></div><div tabindex="-1" class="text_cell_render rendered_html"><p>As seen above, first class functions can be used to traverse data structures. Another common
data structure is a tree. We can implement tree traversal functions to visit each node:</p></div></div><div tabindex="2" class="cell border-box-sizing code_cell vbox"><div class="input hbox"><div class="prompt input_prompt">In [28]:</div><div class="input_area box-flex1"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px; top: 0px; left: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-ipython"><div style="position: relative; height: 399px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre><span> result += preorder_tree_map(function, right, level+1)</span></pre></div><div style="position: relative; top: 0px;"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative;" draggable="true"><pre style="top: 0px; left: 0px;" class="CodeMirror-cursor"> </pre><div style=""><pre><span class="cm-comment"># Store the tree as nodes of (value, left, right)</span></pre><pre> </pre><pre><span class="cm-variable">mytree</span><span class="cm-null"> = (</span><span class="cm-string">'root'</span><span class="cm-null">, </span></pre><pre><span class="cm-null"> (</span><span class="cm-string">'child-L'</span><span class="cm-null">, (), ()), </span></pre><pre><span class="cm-null"> (</span><span class="cm-string">'child-R'</span><span class="cm-null">, </span></pre><pre><span class="cm-null"> (</span><span class="cm-string">'child-RL'</span><span class="cm-null">, (), ()),</span></pre><pre><span class="cm-null"> (</span><span class="cm-string">'child-RR'</span><span class="cm-null">, (), ())))</span></pre><pre> </pre><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">preorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">, </span><span class="cm-variable">node</span><span class="cm-null">, </span><span class="cm-variable">level</span><span class="cm-null">=</span><span class="cm-number">0</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">value</span><span class="cm-null">, </span><span class="cm-variable">left</span><span class="cm-null">, </span><span class="cm-variable">right</span><span class="cm-null"> = </span><span class="cm-variable">node</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> = [</span><span class="cm-variable">function</span><span class="cm-null">(</span><span class="cm-variable">level</span><span class="cm-null">, </span><span class="cm-variable">value</span><span class="cm-null">)]</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">if</span><span class="cm-null"> </span><span class="cm-variable">left</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> += </span><span class="cm-variable">preorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">, </span><span class="cm-variable">left</span><span class="cm-null">, </span><span class="cm-variable">level</span><span class="cm-operator">+</span><span class="cm-number">1</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">if</span><span class="cm-null"> </span><span class="cm-variable">right</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> += </span><span class="cm-variable">preorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">, </span><span class="cm-variable">right</span><span class="cm-null">, </span><span class="cm-variable">level</span><span class="cm-operator">+</span><span class="cm-number">1</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">result</span></pre><pre><span class="cm-null"> </span></pre><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">print_node</span><span class="cm-null">(</span><span class="cm-variable">level</span><span class="cm-null">, </span><span class="cm-variable">value</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">print</span><span class="cm-null"> (</span><span class="cm-string">' '</span><span class="cm-null"> </span><span class="cm-operator">*</span><span class="cm-null"> </span><span class="cm-variable">level</span><span class="cm-null">) </span><span class="cm-operator">+</span><span class="cm-null"> </span><span class="cm-variable">repr</span><span class="cm-null">(</span><span class="cm-variable">value</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">value</span></pre><pre> </pre><pre><span class="cm-variable">preorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">print_node</span><span class="cm-null">, </span><span class="cm-variable">mytree</span><span class="cm-null">)</span></pre></div></div></div></div></div></div></div></div></div><div style="display: -moz-box;" class="output vbox"><div class="hbox output_area"><div class="prompt"></div><div class="box_flex1 output_subarea output_text output_stream output_stdout"><pre>'root'
'child-L'
'child-R'
'child-RL'
'child-RR'</pre></div></div><div class="hbox output_area"><div class="prompt output_prompt">Out[28]:</div><div class="box_flex1 output_subarea output_text"><pre>['root', 'child-L', 'child-R', 'child-RL', 'child-RR']</pre></div></div></div></div><div tabindex="2" class="cell border-box-sizing code_cell vbox"><div class="input hbox"><div class="prompt input_prompt">In [29]:</div><div class="input_area box-flex1"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px; top: 0px; left: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-ipython"><div style="position: relative; height: 206px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre><span> result += inorder_tree_map(function, right, level+1)</span></pre></div><div style="position: relative; top: 0px;"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative;" draggable="true"><pre style="top: 0px; left: 0px;" class="CodeMirror-cursor"> </pre><div style=""><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">inorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">, </span><span class="cm-variable">node</span><span class="cm-null">, </span><span class="cm-variable">level</span><span class="cm-null">=</span><span class="cm-number">0</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">value</span><span class="cm-null">, </span><span class="cm-variable">left</span><span class="cm-null">, </span><span class="cm-variable">right</span><span class="cm-null"> = </span><span class="cm-variable">node</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> = []</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">if</span><span class="cm-null"> </span><span class="cm-variable">left</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> += </span><span class="cm-variable">inorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">, </span><span class="cm-variable">left</span><span class="cm-null">, </span><span class="cm-variable">level</span><span class="cm-operator">+</span><span class="cm-number">1</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result.append</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">(</span><span class="cm-variable">level</span><span class="cm-null">, </span><span class="cm-variable">value</span><span class="cm-null">))</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">if</span><span class="cm-null"> </span><span class="cm-variable">right</span><span class="cm-null">:</span></pre><pre><span class="cm-null"> </span><span class="cm-variable">result</span><span class="cm-null"> += </span><span class="cm-variable">inorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">function</span><span class="cm-null">, </span><span class="cm-variable">right</span><span class="cm-null">, </span><span class="cm-variable">level</span><span class="cm-operator">+</span><span class="cm-number">1</span><span class="cm-null">)</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">result</span></pre><pre><span class="cm-null"> </span></pre><pre><span class="cm-variable">inorder_tree_map</span><span class="cm-null">(</span><span class="cm-variable">print_node</span><span class="cm-null">, </span><span class="cm-variable">mytree</span><span class="cm-null">)</span></pre></div></div></div></div></div></div></div></div></div><div style="display: -moz-box;" class="output vbox"><div class="hbox output_area"><div class="prompt"></div><div class="box_flex1 output_subarea output_text output_stream output_stdout"><pre> 'child-L'
'root'
'child-RL'
'child-R'
'child-RR'</pre></div></div><div class="hbox output_area"><div class="prompt output_prompt">Out[29]:</div><div class="box_flex1 output_subarea output_text"><pre>['child-L', 'root', 'child-RL', 'child-R', 'child-RR']</pre></div></div></div></div><div tabindex="2" class="cell text_cell border-box-sizing"><div style="display: none;" class="text_cell_input"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-default"><div style="position: relative; height: 1px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre>x</pre></div><div style="position: relative"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative" draggable="true"><pre class="CodeMirror-cursor"> </pre><div></div></div></div></div></div></div></div></div><div tabindex="-1" class="text_cell_render rendered_html"><h2>Closures and lexical scoping</h2></div></div><div tabindex="2" class="cell border-box-sizing code_cell vbox"><div class="input hbox"><div class="prompt input_prompt">In [1]:</div><div class="input_area box-flex1"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px; top: 0px; left: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-ipython"><div style="position: relative; height: 188px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre><span> return value + other_value</span></pre></div><div style="position: relative; top: 0px;"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative;" draggable="true"><pre style="top: 0px; left: 0px;" class="CodeMirror-cursor"> </pre><div style=""><pre><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">make_adder</span><span class="cm-null">(</span><span class="cm-variable">value</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">def</span><span class="cm-null"> </span><span class="cm-variable">adder</span><span class="cm-null">(</span><span class="cm-variable">other_value</span><span class="cm-null">):</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">value</span><span class="cm-null"> </span><span class="cm-operator">+</span><span class="cm-null"> </span><span class="cm-variable">other_value</span></pre><pre><span class="cm-null"> </span><span class="cm-keyword">return</span><span class="cm-null"> </span><span class="cm-variable">adder</span></pre><pre> </pre><pre><span class="cm-variable">add5</span><span class="cm-null"> = </span><span class="cm-variable">make_adder</span><span class="cm-null">(</span><span class="cm-number">5</span><span class="cm-null">)</span></pre><pre><span class="cm-keyword">print</span><span class="cm-null"> </span><span class="cm-variable">add5</span><span class="cm-null">(</span><span class="cm-number">10</span><span class="cm-null">)</span></pre><pre> </pre><pre><span class="cm-variable">add2</span><span class="cm-null"> = </span><span class="cm-variable">make_adder</span><span class="cm-null">(</span><span class="cm-number">2</span><span class="cm-null">)</span></pre><pre><span class="cm-keyword">print</span><span class="cm-null"> </span><span class="cm-variable">add2</span><span class="cm-null">(</span><span class="cm-number">10</span><span class="cm-null">)</span></pre></div></div></div></div></div></div></div></div></div><div style="display: -moz-box;" class="output vbox"><div class="hbox output_area"><div class="prompt"></div><div class="box_flex1 output_subarea output_text output_stream output_stdout"><pre>15
12</pre></div></div></div></div><div tabindex="2" class="cell text_cell border-box-sizing"><div style="display: none;" class="text_cell_input"><div class="CodeMirror"><div style="overflow: hidden; position: relative; width: 1px; height: 0px;"><textarea style="position: absolute; width: 2px;" wrap="off" autocorrect="off" autocapitalize="off"></textarea></div><div class="CodeMirror-scroll cm-s-default"><div style="position: relative; height: 6px;"><div style="position: absolute; height: 0; width: 0; overflow: hidden;"><pre>x</pre></div><div style="position: relative"><div style="display: none;" class="CodeMirror-gutter"><div class="CodeMirror-gutter-text"></div></div><div class="CodeMirror-lines"><div style="position: relative" draggable="true"><pre class="CodeMirror-cursor"> </pre><div></div></div></div></div></div></div></div></div><div tabindex="-1" class="text_cell_render rendered_html"><h3>Exercise</h3>
<ul>
<li>Write a function that traverses the tree above in <em>post</em>-order (recursing to the left and right
children <em>before</em> running the function on the node's value itself.</li>
<li>Write a version of <code>filter(function, sequence)</code> that returns the values in a sequence for which
<code>function(item)</code> evaluates to <code>True</code></li>
</ul></div></div><div style="height: 30%;" class="end_space"></div></body></html>