{"topic":{"id":1494,"title":"CS61a 2023 暑期学习日记","slug":"topic","categoryId":11,"createdAt":"2023-06-26 16:59:14.68811","bumpedAt":"2023-09-24 17:38:14.19699","views":1369,"postsCount":22,"highestPostNumber":31,"likeCount":13,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"种种原因，本来说暑假学完 cs61b, 但因为 cs61a 此前没学，于是决定先速通 cs61a 选择的是 fa20, 因为听说这个学期开源的最多这是个日记贴，按道理来说会每天更新，也是对自己的一个督促 [date-range from=2023-06-26T07:30:00 to=2023-06-27T01:00:00 timezone=\"Asia/Shanghai\"] 先从 Textbook 阅读开始，阅读了 ch1.1, ch1…","deletedAt":null,"isAnonymous":false,"category":{"id":11,"name":"深入交流","slug":"distilled","color":"c01c28"},"author":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif"},"tags":["study"]},"posts":[{"id":3509,"postNumber":1,"raw":"种种原因，本来说暑假学完 [cs61b](https://www2.eecs.berkeley.edu/Courses/CS61B/), 但因为 [cs61a](https://cs61a.org/) 此前没学，于是决定先速通 cs61a\n选择的是 [fa20](https://inst.eecs.berkeley.edu/~cs61a/fa20/), 因为听说这个学期开源的最多\n\n*这是个日记贴，按道理来说会每天更新，也是对自己的一个督促*\n\n# [date-range from=2023-06-26T07:30:00 to=2023-06-27T01:00:00 timezone=\"Asia/Shanghai\"]\n先从 Textbook 阅读开始，阅读了 ch1.1, ch1.2, ch1.3, 虽然上个学期自学过 python, 但是大片的英文读的我属实是有点不适应 (感觉语法之类阅读难度都胜于之前读一些文档，, ,).\n这样一对比，看完 textbook 再看 videos 就很享受了，20fa 的 John 教授口语十分清晰好听很容易听明白.\n然后试了下课程配套的 lab, 很好用孩子很喜欢吃 (bushi\n\n一天下来没写什么东西，倒是十分感叹别人家教学的先进和人性化.\n\n# 笔记\n\n## Expressions\n\n- Expressions\n- Call Expressions\n\n## Name\n\nName -- *bind* -- object\n\nThe name of a function is repeated twice, once in the frame and again as part of the function itself. The name appearing in the function is called the *intrinsic name*. The name in a frame is a *bound name*. \n\nThere is a difference between the two: different names may refer to the same function, but that function itself has only one intrinsic name.\n\n## Environment\n\nThe possibility of binding names to values and later retrieving those values by name means that the interpreter must maintain some sort of memory that keeps track of the names, values, and bindings. This memory is called an *environment*.\n\nAn environment in which an expression is evaluated consists of a sequence of *frames*.\n\n Each frame contains *bindings*, each of which associates a name with its corresponding value.\n\nThere is a single *global* frame. \n\n![environment-frame-1|690x233](/uploads/image/7d/25/7d251e11b4977145fd37aa120bcaef58a40157a9abe13432e8bce84d7710836d.avif)\n\n\nAssignment and import statements add entries to the first frame of the current environment. \n\n## Evaluating Nested Expressions\n\n*expression tree*: \n\n![expression_tree|508x356](/uploads/image/69/eb/69eb850e7aa41ae99c3d320cc7560a85127ed6168826aec7f14af186cf5bad06.avif)\n\n\n## The Non-Pure Print Function\n\nIn addition to returning a value, applying a non-pure function can generate *side effects*, which make some change to the state of the interpreter or computer. A common side effect is to generate additional output beyond the return value, using the `print` function.\n\n````python\n>>> print(print(1), print(2))\n1\n2\nNone None\n````\n\n## Calling User-Defined Functions\n\nTo evaluate a call expression whose operator names a user-defined function, the Python interpreter follows a computational process. As with any call expression, the interpreter evaluates the operator and operand expressions, and then applies the named function to the resulting arguments.\n\nApplying a user-defined function introduces a second *local* frame, which is only accessible to that function. To apply a user-defined function to some arguments:\n\n1. Bind the arguments to the names of the function's formal parameters in a new *local* frame.\n2. Execute the body of the function in the environment that starts with this frame.\n\nThe environment in which the body is evaluated consists of two frames: first the local frame that contains formal parameter bindings, then the global frame that contains everything else. Each instance of a function application has its own independent local frame.\n\n![local-names-in-func|690x491](/uploads/image/4c/e3/4ce339d5c1c3e133d25f568cf11a84a3b890c50f0acd4359e19bbefe30194e2f.avif)\n\n\n## Functions as Abstractions\n\n**Aspects of a functional abstraction.** To master the use of a functional abstraction, it is often useful to consider its three core attributes. The *domain* of a function is the set of arguments it can take. The *range* of a function is the set of values it can return. The *intent* of a function is the relationship it computes between inputs and output (as well as any side effects it might generate). Understanding functional abstractions via their domain, range, and intent is critical to using them correctly in a complex program.\n\nFor example, any `square` function that we use to implement `sum_squares` should have these attributes:\n\n- The *domain* is any single real number.\n- The *range* is any non-negative real number.\n- The *intent* is that the output is the square of the input.\n\n\n\n\n# [date-range from=2023-06-27T08:00:00 to=2023-06-28T01:00:00 timezone=\"Asia/Shanghai\"]\n今天睡觉睡得很多 (下午从 13:00 睡到 17:00), 有点低效率，只读完了 textbook ch.1.4-ch.1.5, 看完了 lec3 的 videos, 完成了 lab01 和 hw01\n照这个速度看速通比较困难，所以明天 (今天早上起来) 开始需要尽可能保持高效才行 :exhale:\n# 笔记\n## Ch.1.4 Designing Functions\n\n**Remember, code is written only once, but often read many times.**\n\n### Documentation\n\nA function definition will often include documentation describing the function, called a *docstring*, which must be indented along with the function body. Docstrings are conventionally triple quoted. The first line describes the job of the function in one line. The following lines can describe arguments and clarify the behavior of the function.\n\nComments in Python can be attached to the end of a line following the `#` symbol.\n\n### Default Argument Values\n\nIn Python, we can provide default values for the arguments of a function. When calling that function, arguments with default values are optional. If they are not provided, then the default value is bound to the formal parameter name instead. \n\nAs a guideline, most data values used in a function's body should be expressed as default values to named arguments, so that they are easy to inspect and can be changed by the function caller. Some values that never change, such as the fundamental constant `k`, can be bound in the function body or in the global frame.\n\n````python\ndef pressure(v, t, n=6.022e23):\n\t\"\"\"Compute the pressure in pascals of an ideal gas.\n\n v -- volume of gas, in cubic meters\n t -- absolute temperature in degrees kelvin\n n -- particles of gas (default: one mole)\n \"\"\"\n k = 1.38e-23 # Boltzmann's constant\n return n * k * t / v\n>>> pressure(1, 273.15)\n2269.974834\n>>> pressure(1, 273.15, 3 * 6.022e23)\n6809.924502\n````\n\n## Ch.1.5 Control\n\n### Statements\n\nAt its highest level, the Python interpreter's job is to execute programs, composed of statements. However, much of the interesting work of computation comes from evaluating expressions. Statements govern the relationship among different expressions in a program and what happens to their results.\n\n### Compound Statements\n\n- A simple statement is a single line that doesn't end in a colon. \n- A compound statement is so called because it is composed of other statements (simple and compound). \n\nTogether, a header and an indented suite of statements is called a clause. A compound statement consists of one or more clauses:\n\n```python\n

:\n \n \n ...\n:\n \n \n ...\n```\n\nWe can now know that, \n\n- Expressions, return statements, and assignment statements are simple statements.\n- A `def` statement is a compound statement. The suite that follows the `def` header defines the function body.\n\n**We say that the header controls its suite.**\n\n### Defining Functions II: Local Assignment\n\nThe effect of an assignment statement is to bind a name to a value in the *first* frame of the current environment. As a consequence, assignment statements within a function body cannot affect the global frame.\n\n### Conditional Statements\n\nA conditional statement in Python consists of a series of headers and suites: a required `if` clause, an optional sequence of `elif` clauses, and finally an optional `else` clause\n\nThere is *short-circuiting* in Python when executing logical expressions\n\nFunctions that perform comparisons and return boolean values typically begin with `is`, not followed by an underscore (e.g., `isfinite`, `isdigit`, `isinstance`, etc.).\n\n- `not` has the highest priority\n- `and`\n- `or` has the lowest priority\n\n### Iteration\n\nA `while` clause contains a header expression followed by a suite:\n\n```python\nwhile :\n \n```\n\nA `while` statement that does not terminate is called an infinite loop. Press `-C` to force Python to stop looping.\n\n### Testing\n\n#### Assertions\n\nProgrammers use `assert` statements to verify expectations, such as the output of a function being tested. An `assert` statement has an expression in a boolean context, followed by a quoted line of text (single or double quotes are both fine, but be consistent) that will be displayed if the expression evaluates to a false value.\n\n```python\n>>> assert fib(8) == 13, 'The 8th Fibonacci number should be 13'\n```\n\nWhen the expression being asserted evaluates to a true value, executing an assert statement has no effect. When it is a false value, `assert` causes an error that halts execution.\n\nA test function for `fib` should test several arguments, including extreme values of `n`.\n\n```python\n>>> def fib_test():\n assert fib(2) == 1, 'The 2nd Fibonacci number should be 1'\n assert fib(3) == 1, 'The 3rd Fibonacci number should be 1'\n assert fib(50) == 7778742049, 'Error at the 50th Fibonacci number'\n```\n\nWhen writing Python in files, rather than directly into the interpreter, tests are typically written in the same file or a neighboring file with the suffix `_test.py`.\n\n#### Doctests\n\nPython provides a convenient method for placing simple tests directly in the docstring of a function. The first line of a docstring should contain a one-line description of the function, followed by a blank line. A detailed description of arguments and behavior may follow. In addition, the docstring may include a sample interactive session that calls the function:\n\n```python\n>>> def sum_naturals(n):\n \"\"\"Return the sum of the first n natural numbers.\n\n >>> sum_naturals(10)\n 55\n >>> sum_naturals(100)\n 5050\n \"\"\"\n total, k = 0, 1\n while k <= n:\n total, k = total + k, k + 1\n return total\n```\n\n**Test all functions:** \n\nthe interaction can be verified via the [doctest module](http://docs.python.org/py3k/library/doctest.html).\n\n```python\n>>> from doctest import testmod\n>>> testmod()\nTestResults(failed=0, attempted=2)\n```\n\n**Test one function:**\n\nwe use a `doctest` function called `run_docstring_examples`.\n\nIts first argument is the function to test. The second should always be the result of the expression `globals()`, a built-in function that returns the global environment. The third argument is `True` to indicate that we would like \"verbose\" output: a catalog of all tests run.\n\n```python\n>>> from doctest import run_docstring_examples\n>>> run_docstring_examples(sum_naturals, globals(), True)\nFinding tests in NoName\nTrying:\n sum_naturals(10)\nExpecting:\n 55\nok\nTrying:\n sum_naturals(100)\nExpecting:\n 5050\nok\n```\n\nWhen writing Python in files, all doctests in a file can be run by starting Python with the doctest command line option:\n\n```shell\npython3 -m doctest \npython3 -m doctest -v \n```\n\nThe key to effective testing is to write (and run) tests immediately after implementing new functions. It is even good practice to write some tests before you implement, in order to have some example inputs and outputs in your mind. A test that applies a single function is called a *unit test*. Exhaustive unit testing is a hallmark of good program design.","cooked":"

种种原因，本来说暑假学完 cs61b, 但因为 cs61a 此前没学，于是决定先速通 cs61a
\n选择的是 fa20, 因为听说这个学期开源的最多

这是个日记贴，按道理来说会每天更新，也是对自己的一个督促

[date-range from=2023-06-26T07:30:00 to=2023-06-27T01:00:00 timezone=\"Asia/Shanghai\"]

先从 Textbook 阅读开始，阅读了 ch1.1, ch1.2, ch1.3, 虽然上个学期自学过 python, 但是大片的英文读的我属实是有点不适应 (感觉语法之类阅读难度都胜于之前读一些文档，, ,).
\n这样一对比，看完 textbook 再看 videos 就很享受了，20fa 的 John 教授口语十分清晰好听很容易听明白.
\n然后试了下课程配套的 lab, 很好用孩子很喜欢吃 (bushi

一天下来没写什么东西，倒是十分感叹别人家教学的先进和人性化.

笔记

Expressions

Expressions
Call Expressions

Name

Name -- bind -- object

The name of a function is repeated twice, once in the frame and again as part of the function itself. The name appearing in the function is called the intrinsic name. The name in a frame is a bound name.

There is a difference between the two: different names may refer to the same function, but that function itself has only one intrinsic name.

Environment

The possibility of binding names to values and later retrieving those values by name means that the interpreter must maintain some sort of memory that keeps track of the names, values, and bindings. This memory is called an environment.

An environment in which an expression is evaluated consists of a sequence of frames.

Each frame contains bindings, each of which associates a name with its corresponding value.

There is a single global frame.

$\"environment-frame-1\"$

Assignment and import statements add entries to the first frame of the current environment.

Evaluating Nested Expressions

expression tree:

$\"expression_tree\"$

The Non-Pure Print Function

In addition to returning a value, applying a non-pure function can generate side effects, which make some change to the state of the interpreter or computer. A common side effect is to generate additional output beyond the return value, using the print function.

>>> print(print(1), print(2))\n1\n2\nNone None\n

Calling User-Defined Functions

To evaluate a call expression whose operator names a user-defined function, the Python interpreter follows a computational process. As with any call expression, the interpreter evaluates the operator and operand expressions, and then applies the named function to the resulting arguments.

Applying a user-defined function introduces a second local frame, which is only accessible to that function. To apply a user-defined function to some arguments:

Bind the arguments to the names of the function's formal parameters in a new local frame.
Execute the body of the function in the environment that starts with this frame.

The environment in which the body is evaluated consists of two frames: first the local frame that contains formal parameter bindings, then the global frame that contains everything else. Each instance of a function application has its own independent local frame.

$\"local-names-in-func\"$

Functions as Abstractions

Aspects of a functional abstraction. To master the use of a functional abstraction, it is often useful to consider its three core attributes. The domain of a function is the set of arguments it can take. The range of a function is the set of values it can return. The intent of a function is the relationship it computes between inputs and output (as well as any side effects it might generate). Understanding functional abstractions via their domain, range, and intent is critical to using them correctly in a complex program.

For example, any square function that we use to implement sum_squares should have these attributes:

The domain is any single real number.
The range is any non-negative real number.
The intent is that the output is the square of the input.

[date-range from=2023-06-27T08:00:00 to=2023-06-28T01:00:00 timezone=\"Asia/Shanghai\"]

今天睡觉睡得很多 (下午从 13:00 睡到 17:00), 有点低效率，只读完了 textbook ch.1.4-ch.1.5, 看完了 lec3 的 videos, 完成了 lab01 和 hw01
\n照这个速度看速通比较困难，所以明天 (今天早上起来) 开始需要尽可能保持高效才行 😮‍💨

笔记

Ch.1.4 Designing Functions

Remember, code is written only once, but often read many times.

Documentation

A function definition will often include documentation describing the function, called a docstring, which must be indented along with the function body. Docstrings are conventionally triple quoted. The first line describes the job of the function in one line. The following lines can describe arguments and clarify the behavior of the function.

Comments in Python can be attached to the end of a line following the # symbol.

Default Argument Values

In Python, we can provide default values for the arguments of a function. When calling that function, arguments with default values are optional. If they are not provided, then the default value is bound to the formal parameter name instead.

As a guideline, most data values used in a function's body should be expressed as default values to named arguments, so that they are easy to inspect and can be changed by the function caller. Some values that never change, such as the fundamental constant k, can be bound in the function body or in the global frame.

def pressure(v, t, n=6.022e23):\n\t\"\"\"Compute the pressure in pascals of an ideal gas.\n\n    v -- volume of gas, in cubic meters\n    t -- absolute temperature in degrees kelvin\n    n -- particles of gas (default: one mole)\n    \"\"\"\n    k = 1.38e-23  # Boltzmann's constant\n    return n * k * t / v\n>>> pressure(1, 273.15)\n2269.974834\n>>> pressure(1, 273.15, 3 * 6.022e23)\n6809.924502\n

Ch.1.5 Control

Statements

At its highest level, the Python interpreter's job is to execute programs, composed of statements. However, much of the interesting work of computation comes from evaluating expressions. Statements govern the relationship among different expressions in a program and what happens to their results.

Compound Statements

A simple statement is a single line that doesn't end in a colon.
A compound statement is so called because it is composed of other statements (simple and compound).

Together, a header and an indented suite of statements is called a clause. A compound statement consists of one or more clauses:

<header>:\n    <statement>\n    <statement>\n    ...\n<separating header>:\n    <statement>\n    <statement>\n    ...\n

We can now know that,

Expressions, return statements, and assignment statements are simple statements.
A def statement is a compound statement. The suite that follows the def header defines the function body.

We say that the header controls its suite.

Defining Functions II: Local Assignment

The effect of an assignment statement is to bind a name to a value in the first frame of the current environment. As a consequence, assignment statements within a function body cannot affect the global frame.

Conditional Statements

A conditional statement in Python consists of a series of headers and suites: a required if clause, an optional sequence of elif clauses, and finally an optional else clause

There is short-circuiting in Python when executing logical expressions

Functions that perform comparisons and return boolean values typically begin with is, not followed by an underscore (e.g., isfinite, isdigit, isinstance, etc.).

not has the highest priority
and
or has the lowest priority

Iteration

A while clause contains a header expression followed by a suite:

while <expression>:\n    <suite>\n

A while statement that does not terminate is called an infinite loop. Press <Control>-C to force Python to stop looping.

Testing

Assertions

Programmers use assert statements to verify expectations, such as the output of a function being tested. An assert statement has an expression in a boolean context, followed by a quoted line of text (single or double quotes are both fine, but be consistent) that will be displayed if the expression evaluates to a false value.

>>> assert fib(8) == 13, 'The 8th Fibonacci number should be 13'\n

When the expression being asserted evaluates to a true value, executing an assert statement has no effect. When it is a false value, assert causes an error that halts execution.

A test function for fib should test several arguments, including extreme values of n.

>>> def fib_test():\n        assert fib(2) == 1, 'The 2nd Fibonacci number should be 1'\n        assert fib(3) == 1, 'The 3rd Fibonacci number should be 1'\n        assert fib(50) == 7778742049, 'Error at the 50th Fibonacci number'\n

When writing Python in files, rather than directly into the interpreter, tests are typically written in the same file or a neighboring file with the suffix _test.py.

Doctests

Python provides a convenient method for placing simple tests directly in the docstring of a function. The first line of a docstring should contain a one-line description of the function, followed by a blank line. A detailed description of arguments and behavior may follow. In addition, the docstring may include a sample interactive session that calls the function:

>>> def sum_naturals(n):\n        \"\"\"Return the sum of the first n natural numbers.\n\n        >>> sum_naturals(10)\n        55\n        >>> sum_naturals(100)\n        5050\n        \"\"\"\n        total, k = 0, 1\n        while k <= n:\n            total, k = total + k, k + 1\n        return total\n

Test all functions:

the interaction can be verified via the doctest module.

>>> from doctest import testmod\n>>> testmod()\nTestResults(failed=0, attempted=2)\n

Test one function:

we use a doctest function called run_docstring_examples.

Its first argument is the function to test. The second should always be the result of the expression globals(), a built-in function that returns the global environment. The third argument is True to indicate that we would like \"verbose\" output: a catalog of all tests run.

>>> from doctest import run_docstring_examples\n>>> run_docstring_examples(sum_naturals, globals(), True)\nFinding tests in NoName\nTrying:\n    sum_naturals(10)\nExpecting:\n    55\nok\nTrying:\n    sum_naturals(100)\nExpecting:\n    5050\nok\n

When writing Python in files, all doctests in a file can be run by starting Python with the doctest command line option:

python3 -m doctest <python_source_file> \npython3 -m doctest -v <python_source_file> \n

The key to effective testing is to write (and run) tests immediately after implementing new functions. It is even good practice to write some tests before you implement, in order to have some example inputs and outputs in your mind. A test that applies a single function is called a unit test. Exhaustive unit testing is a hallmark of good program design.

\n","createdAt":"2023-06-26 16:59:14.938302","updatedAt":"2023-09-09 08:29:42.360959","replyToPostNumber":null,"replyCount":0,"likeCount":6,"wordCount":1886,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":6,"users":[{"id":46,"username":"Alice","name":null},{"id":172,"username":"HCCH","name":"HCCH"},{"id":182,"username":"duroy","name":"duroy"},{"id":370,"username":"Qiaoben","name":null},{"id":492,"username":"leester","name":null},{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":5,"publicVersion":5,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3514,"postNumber":6,"raw":"但是我之前除了 [The Missing Semester of Your CS Education (mit.edu)](https://missing.csail.mit.edu/) 再没接触过别的英文课程，知识方面也是只会做一些题没写过 project. 先从 cs61a 开始一方面满足了我的强迫症 (bushi), 我也想系统的接收知识，一方面可以让我练练英语，一方面可以让我接触一些简单的 project.\n\n还好暑假还长，一个一个来，问题不大！","cooked":"

但是我之前除了 The Missing Semester of Your CS Education (mit.edu) 再没接触过别的英文课程，知识方面也是只会做一些题没写过 project. 先从 cs61a 开始一方面满足了我的强迫症 (bushi), 我也想系统的接收知识，一方面可以让我练练英语，一方面可以让我接触一些简单的 project.

还好暑假还长，一个一个来，问题不大！

\n","createdAt":"2023-06-26 17:19:18.157761","updatedAt":"2023-06-26 17:19:18.157761","replyToPostNumber":2,"replyCount":0,"likeCount":0,"wordCount":116,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3517,"postNumber":9,"raw":"我可能会学后面自己感兴趣的 ( 上个学期的 c 语言课我就是在开课后火速跟 mooc 上浙大翁恺老师的课\n[程序设计入门——C 语言_中国大学 MOOC(慕课) (icourse163.org)](https://www.icourse163.org/learn/ZJU-199001?tid=1468796457#/learn/announce)\n[C 语言程序设计进阶_中国大学 MOOC(慕课) (icourse163.org)](https://www.icourse163.org/learn/ZJU-200001?tid=1467811465#/learn/announce)\n学完了课程要求内容，然后继续上浙大的课学数据结构\n[数据结构_中国大学 MOOC(慕课) (icourse163.org)](https://www.icourse163.org/learn/ZJU-93001?tid=1459700443#/learn/announce), \n期间还学了点 the missing semester 的课\n\n上个学期实践过后感觉这种节奏是我喜欢的 (x","cooked":"

我可能会学后面自己感兴趣的 ( 上个学期的 c 语言课我就是在开课后火速跟 mooc 上浙大翁恺老师的课
\n程序设计入门——C 语言_中国大学 MOOC(慕课) (icourse163.org)
\nC 语言程序设计进阶_中国大学 MOOC(慕课) (icourse163.org)
\n学完了课程要求内容，然后继续上浙大的课学数据结构
\n数据结构_中国大学 MOOC(慕课) (icourse163.org),
\n期间还学了点 the missing semester 的课

上个学期实践过后感觉这种节奏是我喜欢的 (x

\n","createdAt":"2023-06-26 17:29:22.054507","updatedAt":"2023-06-30 00:13:03.880034","replyToPostNumber":7,"replyCount":0,"likeCount":1,"wordCount":152,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":474,"username":"shireu","name":"shirleu"}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3518,"postNumber":10,"raw":"我是从 61b 入门的","cooked":"

我是从 61b 入门的

\n","createdAt":"2023-06-27 00:05:01.143578","updatedAt":"2023-06-27 00:05:01.143578","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":7,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":45,"username":"vamossaka","name":"someone","avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":3577,"postNumber":12,"raw":"unit test 是好习惯","cooked":"

unit test 是好习惯

\n","createdAt":"2023-06-28 01:25:26.964106","updatedAt":"2024-03-17 13:04:46.193081","replyToPostNumber":11,"replyCount":1,"likeCount":0,"wordCount":6,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":3579,"postNumber":14,"raw":"我才知道这种东西也是会被放到教科书里教给学生的，而且是给刚刚入门计算机的学生们教的。","cooked":"

我才知道这种东西也是会被放到教科书里教给学生的，而且是给刚刚入门计算机的学生们教的。

\n","createdAt":"2023-06-28 01:29:03.830117","updatedAt":"2023-06-28 01:29:03.830117","replyToPostNumber":12,"replyCount":1,"likeCount":0,"wordCount":42,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3580,"postNumber":15,"raw":"还有一个有趣的概念叫 [Test-Driven Development](https://doc.rust-lang.org/book/ch12-04-testing-the-librarys-functionality.html#developing-the-librarys-functionality-with-test-driven-development)","cooked":"

还有一个有趣的概念叫 Test-Driven Development

\n","createdAt":"2023-06-28 01:34:03.710258","updatedAt":"2024-03-17 13:04:46.290318","replyToPostNumber":14,"replyCount":1,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":3594,"postNumber":16,"raw":"在做 cs61a 的 lab01 时，教授提供的 https://inst.eecs.berkeley.edu/~cs61a/fa20/articles/debugging.html 文档就提到了这个:\n> * **Write some tests before you write code**: this is called test-driven development. Writing down how you expect the function to behave first -- this can guide you when writing the actual code.","cooked":"

在做 cs61a 的 lab01 时，教授提供的 CAS - CalNet Authentication Service 登录文档就提到了这个:

\n
\n
Write some tests before you write code: this is called test-driven development. Writing down how you expect the function to behave first -- this can guide you when writing the actual code.
\n
\n

\n","createdAt":"2023-06-28 03:38:29.931567","updatedAt":"2023-06-28 03:38:29.931567","replyToPostNumber":15,"replyCount":0,"likeCount":1,"wordCount":56,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3633,"postNumber":17,"raw":"# [date-range from=2023-06-28T12:00:00 to=2023-06-29T01:00:00 timezone=\"Asia/Shanghai\"]\n\n

\n\n看了 [Debugging | CS 61A Fall 2020](https://inst.eecs.berkeley.edu/~cs61a/fa20/articles/debugging.html) 文档和噩梦般的 [ch.1.6: Higher-Order Functions](https://composingprograms.com/pages/16-higher-order-functions.html)\n看的过程有点痛苦，看到 Newton's Method 的时候彻底晕了，然后就跳过 Newton's Method 看完了.\nNewton's Method 到时候看 videos 再说吧\n*However, 好消息是明天 (今早) 开始可以连续看好多 videos 而不用看书，这是福报啊!!*\n# 笔记\n## Something About The Document: Debugging\n\n**Traceback Messages**\n\n````shell\nFile \"\", line , in \n````\n\n**Error Messages**\n\n````shell\n: \n````\n\n### Debugging Techniques\n\n- **Running doctests**\n\n- **Using `print` statements**\n\n - Long-term debugging\n\n Sometimes we would like to leave the debugging code if we need to periodically test our file. It can get kind of annoying if every time we run our file, debugging messages pop up. One way to avoid this is to use a global `debug` variable:\n\n ````python\n debug = True\n \n def foo(n):\n i = 0\n while i < n:\n i += func(i)\n if debug:\n print('DEBUG: i is', i)\n ````\n\n- **Interactive Debugging**\n\n One way a lot of programmers like to investigate their code is by use of an interactive REPL. That is, a terminal where you can directly run functions and inspect their outputs.\n\n Typically, to accomplish this, you can run\n\n ```shell\n python -i file.py\n ```\n\n and one then has a session of python where all the definitions of `file.py` have already been executed.\n\n- **Python Tutor Debugging**\n\n Sometimes the best way to understand what is going on with a given piece of python code is to create an environment diagram. While creating an environment diagram by hand can sometimes be tedious, the tool [Python Tutor](https://tutor.cs61a.org/) creates environment diagrams automatically.\n\n- **Using `assert` statements**\n\n For example, if you are writing a function that takes in an integer and doubles it, it might be useful to ensure that your input is in fact an integer. You can then write the following code\n\n ```python\n def double(x):\n assert isinstance(x, int), \"The input to double(x) must be an integer\"\n return 2 * x\n ```\n\n Note that we aren't really debugging the `double` function here, what we're doing is ensuring that anyone who calls `double` is doing so with the right arguments. \n\n One *major* benefit of assert statements is that they are more than a debugging tool, you can leave them in code permanantly. A key principle in software development is that it is generally better for code to crash than produce an incorrect result, and having asserts in your code makes it far more likely that your code will crash if it has a bug in it.\n\n### Error Types\n\n- `SyntaxError`\n\n This is different from other errors, which are only raised during runtime.\n\n- `IndentationError`\n\n- `TypeError`\n\n- `NameError`\n\n variable not assigned to anything OR it doesn't exist. This includes function names.\n\n- `IndexError`\n\n### Lab01 quiz back-up\n\n````shell\nQ: What is the best way to open an interactive terminal to investigate a failing test for question sum_digits in assignment lab01?\nChoose the number of the correct choice:\n\n0) python3 ok -q sum_digits --trace\n1) python3 -i lab01.py\n2) python3 ok -q sum_digits -i\n3) python3 ok -q sum_digits\n ? 2\n -- OK! --\n````\n\n## Ch.1.6 Higher-Order Functions\n\n*One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the names directly.*\n\n**Functions that manipulate functions are called higher-order functions.**\n\n### Functions as Arguments\n\nUsing an `identity` function that returns its argument, we can sum natural numbers using exactly the same `summation` function.\n\n```python\n>>> def summation(n, term):\n total, k = 0, 1\n while k <= n:\n total, k = total + term(k), k + 1\n return total\n>>> def identity(x):\n return x\n>>> def sum_naturals(n):\n return summation(n, identity)\n>>> sum_naturals(10)\n55\n```\n\n### Functions as General Methods\n\nWith higher-order functions, we begin to see a more powerful kind of abstraction: some functions express general methods of computation, independent of the particular functions they call.\n\nWhen a user-defined function is applied to some arguments, the formal parameters are bound to the values of those arguments (which may be functions) in a new local frame.\n\nConsider the following example, which implements a general method for iterative improvement and uses it to compute the [golden ratio](http://www.geom.uiuc.edu/~demo5337/s97b/art.htm). The golden ratio, often called \"phi\", is a number near 1.6 that appears frequently in nature, art, and architecture.\n\nAn iterative improvement algorithm begins with a `guess` of a solution to an equation. It repeatedly applies an `update` function to improve that guess, and applies a `close` comparison to check whether the current `guess` is \"close enough\" to be considered correct.\n\n```python\n>>> def improve(update, close, guess=1):\n while not close(guess):\n guess = update(guess)\n return guess\n```\n\nThis `improve` function is a general expression of **repetitive refinement**. It doesn't specify what problem is being solved: those details are left to the `update` and `close` functions passed in as arguments.\n\nAmong the well-known properties of the golden ratio are that it can be computed by repeatedly summing the inverse of any positive number with 1, and that it is one less than its square. We can express these properties as functions to be used with `improve`.\n\n```python\n>>> def golden_update(guess):\n return 1/guess + 1\n>>> def square_close_to_successor(guess):\n return approx_eq(guess * guess, guess + 1)\n```\n\nAbove, we introduce a call to `approx_eq` that is meant to return `True` if its arguments are approximately equal to each other. To implement, `approx_eq`, we can compare the absolute value of the difference between two numbers to a small tolerance value.\n\n```python\n>>> def approx_eq(x, y, tolerance=1e-15):\n return abs(x - y) < tolerance\n```\n\nCalling `improve` with the arguments `golden_update` and `square_close_to_successor` will compute a finite approximation to the golden ratio.\n\n```python\n>>> improve(golden_update, square_close_to_successor)\n1.6180339887498951\n```\n\nThis example illustrates two related big ideas in computer science. \n\n- First, naming and functions allow us to abstract away a vast amount of complexity. While each function definition has been trivial, the computational process set in motion by our evaluation procedure is quite intricate. \n- Second, it is only by virtue of the fact that we have an extremely general evaluation procedure for the Python language that small components can be composed into complex processes. Understanding the procedure of interpreting programs allows us to validate and inspect the process we have created.\n\n### Defining Functions III: Nested Definitions\n\nLet's consider a new problem: computing the square root of a number. In programming languages, \"square root\" is often abbreviated as `sqrt`. Repeated application of the following update converges to the square root of `a`:\n\n```python\n>>> def average(x, y):\n return (x + y)/2\n>>> def sqrt_update(x, a):\n return average(x, a/x)\n```\n\nThis two-argument update function is incompatible with `improve` (it takes two arguments, not one), and it provides only a single update, while we really care about taking square roots by repeated updates. The solution to both of these issues is to place function definitions inside the body of other definitions.\n\n```python\n>>> def sqrt(a):\n def sqrt_update(x):\n return average(x, a/x)\n def sqrt_close(x):\n return approx_eq(x * x, a)\n return improve(sqrt_update, sqrt_close)\n```\n\n**Lexical scope:**\n\nLocally defined functions also have access to the name bindings in the scope in which they are defined. In this example, `sqrt_update` refers to the name `a`, which is a formal parameter of its enclosing function `sqrt`. This discipline of sharing names among nested definitions is called *lexical scoping*. Critically, the inner functions have access to the names in the environment where they are defined (not where they are called).\n\nWe require two extensions to our environment model to enable lexical scoping.\n\n1. Each user-defined function has a parent environment: the environment in which it was defined.\n2. When a user-defined function is called, its local frame extends its parent environment.\n\nPrevious to `sqrt`, all functions were defined in the global environment, and so they all had the same parent: the global environment. By contrast, when Python evaluates the first two clauses of `sqrt`, it create functions that are associated with a local environment.\n\n![Nested_Func|689x397](/uploads/image/61/6e/616e39b9b87b67873317c71c5ceff4a0e36fd28a084f4f1ed07487a599af02b5.avif)\n\n\n> Only after calling `sqrt(a)`, `sqrt_update` and `sqrt_close` will be defined\n\nFunction values each have a new annotation that we will include in environment diagrams from now on, a *parent*. The parent of a function value is the first frame of the environment in which that function was defined. Functions without parent annotations were defined in the global environment. When a user-defined function is called, the frame created has the same parent as that function.\n\n![Nested_Func_2|690x371](/uploads/image/ff/7c/ff7c6598b6cf0caf2e9af6ac9e4d28a5d054db9bd35eb77ba70f732235a1719b.avif)\n\n\n> The most critical part of this evaluation procedure is the transfer of the parent for `sqrt_update`and `sqrt_close` to the frame created by calling `sqrt_update`. This frame is also annotated with `[parent=f1]`.\n\n**Extended Environments:**\n\nAn environment can consist of an arbitrarily long chain of frames, which always concludes with the global frame. Previous to this `sqrt` example, environments had at most two frames: a local frame and the global frame. By calling functions that were defined within other functions, via nested `def` statements, we can create longer chains. The environment for this call to `sqrt_update` consists of three frames: the local `sqrt_update` frame, the `sqrt` frame in which `sqrt_update` was defined (labeled `f1`), and the global frame.\n\nThe return expression in the body of `sqrt_update` can resolve a value for `a` by following this chain of frames. Looking up a name finds the first value bound to that name in the current environment. Python checks first in the `sqrt_update` frame -- no `a` exists. Python checks next in the parent frame, `f1`, and finds a binding for `a` to 256.\n\nHence, we realize two key advantages of lexical scoping in Python.\n\n- The names of a local function do not interfere with names external to the function in which it is defined, because the local function name will be bound in the current local environment in which it was defined, rather than the global environment.\n- A local function can access the environment of the enclosing function, because the body of the local function is evaluated in an environment that extends the evaluation environment in which it was defined.\n\nThe `sqrt_update` function carries with it some data: the value for `a` referenced in the environment in which it was defined. Because they \"enclose\" information in this way, locally defined functions are often called *closures*.\n\n### Functions as Returned Values\n\nOnce many simple functions are defined, function *composition* is a natural method of combination to include in our programming language. That is, given two functions `f(x)` and `g(x)`, we might want to define `h(x) = f(g(x))`. We can define function composition using our existing tools:\n\n```python\n>>> def compose1(f, g):\n def h(x):\n return f(g(x))\n return h\n```\n\nThe 1 in `compose1` is meant to signify that the composed functions all take a single argument. This naming convention is not enforced by the interpreter; the 1 is just part of the function name.\n\n### Example: Newton's Method\n\nNewton's method is an iterative improvement algorithm: it improves a guess of the zero for any function that is *differentiable*, which means that it can be approximated by a straight line at any point. Newton's method follows these linear approximations to find function zeros.\n\n![newton|399x302](/uploads/image/8b/0b/8b0b3fc86eaf192e6d2837451818b3197751d11ff84bd14d4e53125a9a85eb4a.avif)\n\nImagine a line through the point (*x*,*f*(*x*)) that has the same slope as the curve for function *f*(*x*) at that point. Such a line is called the *tangent*, and its slope is called the *derivative* of *f*(*x*) at *x*.\n\nHence, translating *x* by *f*(*x*) divided by the slope will give the argument value at which this tangent line touches 0.\n\nA `newton_update` expresses the computational process of following this tangent line to 0, for a function `f` and its derivative `df`.\n\n后面看课本没看懂了，到时候再看 videos 吧\n\n**TODO**\n\n\n\n### Currying\n\nWe can use higher-order functions to convert a function that takes multiple arguments into a chain of functions that each take a single argument.More specifically, given a function `f(x, y)`, we can define a function `g` such that `g(x)(y)` is equivalent to `f(x, y)`. Here, `g` is a higher-order function that takes in a single argument `x` and returns another function that takes in a single argument `y`. This transformation is called *currying*.\n\nAs an example, we can define a curried version of the `pow` function:\n\n```python\n>>> def curried_pow(x):\n def h(y):\n return pow(x, y)\n return h\n>>> curried_pow(2)(3)\n8\n```\n\nwe manually performed the currying transformation on the `pow` function to obtain `curried_pow`. Instead, we can define functions to automate currying, as well as the inverse *uncurrying* transformation:\n\n```python\n>>> def curry2(f):\n \"\"\"Return a curried version of the given two-argument function.\"\"\"\n def g(x):\n def h(y):\n return f(x, y)\n return h\n return g\n>>> def uncurry2(g):\n \"\"\"Return a two-argument version of the given curried function.\"\"\"\n def f(x, y):\n return g(x)(y)\n return f\n\n>>> # can be more concise using lambda expressions introduced later\n>>> curry2 = lambda f: (lambda x: (lambda y: f(x, y)))\n>>> uncurry2 = lambda f: (lambda x,y: f(x)(y))\n\n>>> pow_curried = curry2(pow)\n>>> pow_curried(2)(5)\n32\n>>> map_to_range(0, 10, pow_curried(2))\n1\n2\n4\n8\n16\n32\n64\n128\n256\n512\n```\n\n### Lambda Expressions\n\nWe can understand the structure of a `lambda` expression by constructing a corresponding English sentence:\n\n```python\n lambda x : f(g(x))\n\"A function that takes x and returns f(g(x))\"\n```\n\n![lambda|690x426](/uploads/image/1a/74/1a74607e2cc0bed6e543df1d6ee35ab8bbacc35e0341cb0c4709ed6be6ea6f8d.avif)\n\n\nIn general, Python style prefers explicit `def` statements to lambda expressions, but allows them in cases where a simple function is needed as an argument or return value.\n\n### Abstractions and First-Class Functions\n\nThe significance of higher-order functions is that they enable us to represent these abstractions explicitly as elements in our programming language, so that they can be handled just like other computational elements.\n\nIn general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the \"rights and privileges\" of first-class elements are:\n\n1. They may be bound to names.\n2. They may be passed as arguments to functions.\n3. They may be returned as the results of functions.\n4. They may be included in data structures.\n\nPython awards functions full first-class status, and the resulting gain in expressive power is enormous.\n

","cooked":"

[date-range from=2023-06-28T12:00:00 to=2023-06-29T01:00:00 timezone=\"Asia/Shanghai\"]

看了 Debugging | CS 61A Fall 2020 文档和噩梦般的 ch.1.6: Higher-Order Functions
\n看的过程有点痛苦，看到 Newton's Method 的时候彻底晕了，然后就跳过 Newton's Method 看完了.
\nNewton's Method 到时候看 videos 再说吧
\nHowever, 好消息是明天 (今早) 开始可以连续看好多 videos 而不用看书，这是福报啊!!

笔记

Something About The Document: Debugging

Traceback Messages

File \"<file name>\", line <number>, in <function>\n

Error Messages

<error type>: <error message>\n

Debugging Techniques

\n
Running doctests
\n
\n
Using print statements
\n
- \n
  Long-term debugging
  \n
  Sometimes we would like to leave the debugging code if we need to periodically test our file. It can get kind of annoying if every time we run our file, debugging messages pop up. One way to avoid this is to use a global debug variable:
  \n
```
debug = True\n\ndef foo(n):\ni = 0\nwhile i < n:\n    i += func(i)\n    if debug:\n        print('DEBUG: i is', i)\n
```
  \n
\n
\n
Interactive Debugging
\n
One way a lot of programmers like to investigate their code is by use of an interactive REPL. That is, a terminal where you can directly run functions and inspect their outputs.
\n
Typically, to accomplish this, you can run
\n
```
python -i file.py\n
```
\n
and one then has a session of python where all the definitions of file.py have already been executed.
\n
\n
Python Tutor Debugging
\n
Sometimes the best way to understand what is going on with a given piece of python code is to create an environment diagram. While creating an environment diagram by hand can sometimes be tedious, the tool Python Tutor creates environment diagrams automatically.
\n
\n
Using assert statements
\n
For example, if you are writing a function that takes in an integer and doubles it, it might be useful to ensure that your input is in fact an integer. You can then write the following code
\n
```
def double(x):\n    assert isinstance(x, int), \"The input to double(x) must be an integer\"\n    return 2 * x\n
```
\n
Note that we aren't really debugging the double function here, what we're doing is ensuring that anyone who calls double is doing so with the right arguments.
\n
One major benefit of assert statements is that they are more than a debugging tool, you can leave them in code permanantly. A key principle in software development is that it is generally better for code to crash than produce an incorrect result, and having asserts in your code makes it far more likely that your code will crash if it has a bug in it.
\n

Error Types

\n
SyntaxError
\n
This is different from other errors, which are only raised during runtime.
\n
\n
IndentationError
\n
\n
TypeError
\n
\n
NameError
\n

variable not assigned to anything OR it doesn't exist. This includes function names.

IndexError

Lab01 quiz back-up

Q: What is the best way to open an interactive terminal to investigate a failing test for question sum_digits in assignment lab01?\nChoose the number of the correct choice:\n\n0) python3 ok -q sum_digits --trace\n1) python3 -i lab01.py\n2) python3 ok -q sum_digits -i\n3) python3 ok -q sum_digits\n   ? 2\n   -- OK! --\n

Ch.1.6 Higher-Order Functions

One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the names directly.

Functions that manipulate functions are called higher-order functions.

Functions as Arguments

Using an identity function that returns its argument, we can sum natural numbers using exactly the same summation function.

>>> def summation(n, term):\n        total, k = 0, 1\n        while k <= n:\n            total, k = total + term(k), k + 1\n        return total\n>>> def identity(x):\n        return x\n>>> def sum_naturals(n):\n        return summation(n, identity)\n>>> sum_naturals(10)\n55\n

Functions as General Methods

With higher-order functions, we begin to see a more powerful kind of abstraction: some functions express general methods of computation, independent of the particular functions they call.

When a user-defined function is applied to some arguments, the formal parameters are bound to the values of those arguments (which may be functions) in a new local frame.

Consider the following example, which implements a general method for iterative improvement and uses it to compute the golden ratio. The golden ratio, often called \"phi\", is a number near 1.6 that appears frequently in nature, art, and architecture.

An iterative improvement algorithm begins with a guess of a solution to an equation. It repeatedly applies an update function to improve that guess, and applies a close comparison to check whether the current guess is \"close enough\" to be considered correct.

>>> def improve(update, close, guess=1):\n        while not close(guess):\n            guess = update(guess)\n        return guess\n

This improve function is a general expression of repetitive refinement. It doesn't specify what problem is being solved: those details are left to the update and close functions passed in as arguments.

Among the well-known properties of the golden ratio are that it can be computed by repeatedly summing the inverse of any positive number with 1, and that it is one less than its square. We can express these properties as functions to be used with improve.

>>> def golden_update(guess):\n        return 1/guess + 1\n>>> def square_close_to_successor(guess):\n        return approx_eq(guess * guess, guess + 1)\n

Above, we introduce a call to approx_eq that is meant to return True if its arguments are approximately equal to each other. To implement, approx_eq, we can compare the absolute value of the difference between two numbers to a small tolerance value.

>>> def approx_eq(x, y, tolerance=1e-15):\n        return abs(x - y) < tolerance\n

Calling improve with the arguments golden_update and square_close_to_successor will compute a finite approximation to the golden ratio.

>>> improve(golden_update, square_close_to_successor)\n1.6180339887498951\n

This example illustrates two related big ideas in computer science.

First, naming and functions allow us to abstract away a vast amount of complexity. While each function definition has been trivial, the computational process set in motion by our evaluation procedure is quite intricate.
Second, it is only by virtue of the fact that we have an extremely general evaluation procedure for the Python language that small components can be composed into complex processes. Understanding the procedure of interpreting programs allows us to validate and inspect the process we have created.

Defining Functions III: Nested Definitions

Let's consider a new problem: computing the square root of a number. In programming languages, \"square root\" is often abbreviated as sqrt. Repeated application of the following update converges to the square root of a:

>>> def average(x, y):\n        return (x + y)/2\n>>> def sqrt_update(x, a):\n        return average(x, a/x)\n

This two-argument update function is incompatible with improve (it takes two arguments, not one), and it provides only a single update, while we really care about taking square roots by repeated updates. The solution to both of these issues is to place function definitions inside the body of other definitions.

>>> def sqrt(a):\n        def sqrt_update(x):\n            return average(x, a/x)\n        def sqrt_close(x):\n            return approx_eq(x * x, a)\n        return improve(sqrt_update, sqrt_close)\n

Lexical scope:

Locally defined functions also have access to the name bindings in the scope in which they are defined. In this example, sqrt_update refers to the name a, which is a formal parameter of its enclosing function sqrt. This discipline of sharing names among nested definitions is called lexical scoping. Critically, the inner functions have access to the names in the environment where they are defined (not where they are called).

We require two extensions to our environment model to enable lexical scoping.

Each user-defined function has a parent environment: the environment in which it was defined.
When a user-defined function is called, its local frame extends its parent environment.

Previous to sqrt, all functions were defined in the global environment, and so they all had the same parent: the global environment. By contrast, when Python evaluates the first two clauses of sqrt, it create functions that are associated with a local environment.

$\"Nested_Func\"$

\n
Only after calling sqrt(a), sqrt_update and sqrt_close will be defined
\n

Function values each have a new annotation that we will include in environment diagrams from now on, a parent. The parent of a function value is the first frame of the environment in which that function was defined. Functions without parent annotations were defined in the global environment. When a user-defined function is called, the frame created has the same parent as that function.

$\"Nested_Func_2\"$

\n
The most critical part of this evaluation procedure is the transfer of the parent for sqrt_updateand sqrt_close to the frame created by calling sqrt_update. This frame is also annotated with [parent=f1].
\n

Extended Environments:

An environment can consist of an arbitrarily long chain of frames, which always concludes with the global frame. Previous to this sqrt example, environments had at most two frames: a local frame and the global frame. By calling functions that were defined within other functions, via nested def statements, we can create longer chains. The environment for this call to sqrt_update consists of three frames: the local sqrt_update frame, the sqrt frame in which sqrt_update was defined (labeled f1), and the global frame.

The return expression in the body of sqrt_update can resolve a value for a by following this chain of frames. Looking up a name finds the first value bound to that name in the current environment. Python checks first in the sqrt_update frame -- no a exists. Python checks next in the parent frame, f1, and finds a binding for a to 256.

Hence, we realize two key advantages of lexical scoping in Python.

The names of a local function do not interfere with names external to the function in which it is defined, because the local function name will be bound in the current local environment in which it was defined, rather than the global environment.
A local function can access the environment of the enclosing function, because the body of the local function is evaluated in an environment that extends the evaluation environment in which it was defined.

The sqrt_update function carries with it some data: the value for a referenced in the environment in which it was defined. Because they \"enclose\" information in this way, locally defined functions are often called closures.

Functions as Returned Values

Once many simple functions are defined, function composition is a natural method of combination to include in our programming language. That is, given two functions f(x) and g(x), we might want to define h(x) = f(g(x)). We can define function composition using our existing tools:

>>> def compose1(f, g):\n        def h(x):\n            return f(g(x))\n        return h\n

The 1 in compose1 is meant to signify that the composed functions all take a single argument. This naming convention is not enforced by the interpreter; the 1 is just part of the function name.

Example: Newton's Method

Newton's method is an iterative improvement algorithm: it improves a guess of the zero for any function that is differentiable, which means that it can be approximated by a straight line at any point. Newton's method follows these linear approximations to find function zeros.

$\"newton\"$

Imagine a line through the point (x,f(x)) that has the same slope as the curve for function f(x) at that point. Such a line is called the tangent, and its slope is called the derivative of f(x) at x.

Hence, translating x by f(x) divided by the slope will give the argument value at which this tangent line touches 0.

A newton_update expresses the computational process of following this tangent line to 0, for a function f and its derivative df.

后面看课本没看懂了，到时候再看 videos 吧

TODO

Currying

We can use higher-order functions to convert a function that takes multiple arguments into a chain of functions that each take a single argument.More specifically, given a function f(x, y), we can define a function g such that g(x)(y) is equivalent to f(x, y). Here, g is a higher-order function that takes in a single argument x and returns another function that takes in a single argument y. This transformation is called currying.

As an example, we can define a curried version of the pow function:

>>> def curried_pow(x):\n        def h(y):\n            return pow(x, y)\n        return h\n>>> curried_pow(2)(3)\n8\n

we manually performed the currying transformation on the pow function to obtain curried_pow. Instead, we can define functions to automate currying, as well as the inverse uncurrying transformation:

>>> def curry2(f):\n        \"\"\"Return a curried version of the given two-argument function.\"\"\"\n        def g(x):\n            def h(y):\n                return f(x, y)\n            return h\n        return g\n>>> def uncurry2(g):\n        \"\"\"Return a two-argument version of the given curried function.\"\"\"\n        def f(x, y):\n            return g(x)(y)\n        return f\n\n>>> # can be more concise using lambda expressions introduced later\n>>> curry2 = lambda f: (lambda x: (lambda y: f(x, y)))\n>>> uncurry2 = lambda f: (lambda x,y: f(x)(y))\n\n>>> pow_curried = curry2(pow)\n>>> pow_curried(2)(5)\n32\n>>> map_to_range(0, 10, pow_curried(2))\n1\n2\n4\n8\n16\n32\n64\n128\n256\n512\n

Lambda Expressions

We can understand the structure of a lambda expression by constructing a corresponding English sentence:

     lambda            x            :          f(g(x))\n\"A function that    takes x    and returns     f(g(x))\"\n

$\"lambda\"$

In general, Python style prefers explicit def statements to lambda expressions, but allows them in cases where a simple function is needed as an argument or return value.

Abstractions and First-Class Functions

The significance of higher-order functions is that they enable us to represent these abstractions explicitly as elements in our programming language, so that they can be handled just like other computational elements.

In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the \"rights and privileges\" of first-class elements are:

They may be bound to names.
They may be passed as arguments to functions.
They may be returned as the results of functions.
They may be included in data structures.

Python awards functions full first-class status, and the resulting gain in expressive power is enormous.

","createdAt":"2023-06-28 17:05:56.238337","updatedAt":"2023-08-07 10:59:17.654873","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":2428,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":8,"publicVersion":8,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3657,"postNumber":18,"raw":"这个好有趣，反复观摩感觉好美\n\n````python\nsquare = lambda x: x*x\n\ndef search(y):\n \"\"\"Search x until y(x) is true. x must be a positive int\"\"\"\n x = 1\n while True:\n if y(x):\n return x\n x += 1\n\ndef inverse(f):\n \"\"\"return g(y) that g(f(x)) == x\n >>> sqrt = inverse(square)\n >>> sqrt(16)\n 4\n \"\"\"\n return lambda y: search(lambda x: f(x) == y)\n````","cooked":"

这个好有趣，反复观摩感觉好美

square = lambda x: x*x\n\ndef search(y):\n    \"\"\"Search x until y(x) is true. x must be a positive int\"\"\"\n    x = 1\n    while True:\n        if y(x):\n            return x\n        x += 1\n\ndef inverse(f):\n    \"\"\"return g(y) that g(f(x)) == x\n    >>> sqrt = inverse(square)\n    >>> sqrt(16)\n    4\n    \"\"\"\n    return lambda y: search(lambda x: f(x) == y)\n

\n","createdAt":"2023-06-29 15:50:44.511555","updatedAt":"2023-06-29 15:52:17.493787","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":71,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":3677,"postNumber":19,"raw":"函数式编程可用 `filter` 消除控制流\n```python\nimport itertools\n\ndef inverse(f):\n \"\"\"return g(y) that g(f(x)) == x\n >>> sqrt = inverse(lambda x: x*x)\n >>> sqrt(16)\n 4\n \"\"\"\n return lambda y: next(filter(lambda x: f(x) == y, itertools.count()))\n```","cooked":"

函数式编程可用 filter 消除控制流

import itertools\n\ndef inverse(f):\n    \"\"\"return g(y) that g(f(x)) == x\n    >>> sqrt = inverse(lambda x: x*x)\n    >>> sqrt(16)\n    4\n    \"\"\"\n    return lambda y: next(filter(lambda x: f(x) == y, itertools.count()))\n

\n","createdAt":"2023-06-30 03:50:46.579365","updatedAt":"2024-03-17 13:04:46.38346","replyToPostNumber":18,"replyCount":0,"likeCount":1,"wordCount":44,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":31,"username":"TsuinoSora","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":3717,"postNumber":20,"raw":"每次看到 1000+ days 都难绷\n这次是 1024 days\n好吉利的数字啊\n![image|690x54](/uploads/image/52/a3/52a31252544dbcd1d55eb2bf55a50bade438b3b1e972ff023557e25684d49820.avif)","cooked":"

每次看到 1000+ days 都难绷
\n这次是 1024 days
\n好吉利的数字啊
\n $\"image\"$

\n","createdAt":"2023-06-30 17:58:39.0086","updatedAt":"2023-06-30 17:58:39.0086","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":22,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":4087,"postNumber":21,"raw":"# [date-range from=2023-07-05T21:00:00 to=2023-07-07T02:00:00 timezone=\"Asia/Shanghai\"]\n之前几天因为有各种事情摆了什么也没学\n然后这近 30 个小时主要就是完成了 [project1: hog](https://inst.eecs.berkeley.edu/~cs61a/fa20/proj/hog/), 其实就是简单的代码填充，不过还是很有趣的\n\n另外为了解释为什么要学 high order function, 教授还举了不少 function examples\n有个比较有趣的是这个生成 .wav 的程序\n````python\nfrom wave import open\nfrom struct import Struct\nfrom math import floor\n\nframe_rate = 11025\n\ndef encode(x):\n \"\"\"Encode float x between -1 and 1 as two bytes.\n (See https://docs.python.org/3/library/struct.html)\n \"\"\"\n i = int(16384 * x)\n return Struct('h').pack(i)\n\ndef play(sampler, name='song.wav', seconds=2):\n \"\"\"Write the output of a sampler function as a wav file.\n (See https://docs.python.org/3/library/wave.html)\n \"\"\"\n out = open(name, 'wb')\n out.setnchannels(1)\n out.setsampwidth(2)\n out.setframerate(frame_rate)\n t = 0\n while t < seconds * frame_rate:\n sample = sampler(t)\n out.writeframes(encode(sample))\n t = t + 1\n out.close()\n\ndef tri(frequency, amplitude=0.3):\n \"\"\"A continuous triangle wave.\"\"\"\n period = frame_rate // frequency # 1 个周期中有 period 个采样点\n def sampler(t):\n saw_wave = t / period - floor(t / period + 0.5)\n tri_wave = 2 * abs(2 * saw_wave) - 1\n return amplitude * tri_wave\n return sampler\n\nc_freq, e_freq, g_freq = 261.63, 329.63, 392.00\nc = tri(c_freq)\ne = tri(e_freq)\ng = tri(g_freq)\nlow_g = tri(g_freq / 2)\n\ndef both(f, g):\n return lambda t: f(t) + g(t)\n\ndef note(f, start, end, fade=0.01):\n \"\"\"Play f for a fixed duration.\"\"\"\n def sampler(t):\n seconds = t / frame_rate\n if seconds < start:\n return 0\n elif seconds > end:\n return 0\n elif seconds < start + fade:\n return (seconds - start) / fade * f(t)\n elif seconds > end - fade:\n return (end - seconds) / fade * f(t)\n else:\n return f(t)\n return sampler\n\ndef mario(c, e, g, low_g):\n z = 0\n song = note(e, z, z + 1/8)\n z += 1/8\n song = both(song, note(e, z, z + 1/8))\n z += 1/4\n song = both(song, note(e, z, z + 1/8))\n z += 1/4\n song = both(song, note(c, z, z + 1/8))\n z += 1/8\n song = both(song, note(e, z, z + 1/8))\n z += 1/4\n song = both(song, note(g, z, z + 1/4))\n z += 1/2\n song = both(song, note(low_g, z, z + 1/4))\n return song\n\ndef mario_at(octave):\n c = tri(octave * c_freq)\n e = tri(octave * e_freq)\n g = tri(octave * g_freq)\n low_g = tri(octave * g_freq / 2)\n return mario(c, e, g, low_g)\n\nplay(both(mario_at(1), mario_at(1/2)))\n````\n^这段可以成功生成马里奥的开场音乐","cooked":"

[date-range from=2023-07-05T21:00:00 to=2023-07-07T02:00:00 timezone=\"Asia/Shanghai\"]

之前几天因为有各种事情摆了什么也没学
\n然后这近 30 个小时主要就是完成了 project1: hog, 其实就是简单的代码填充，不过还是很有趣的

另外为了解释为什么要学 high order function, 教授还举了不少 function examples
\n有个比较有趣的是这个生成 .wav 的程序

from wave import open\nfrom struct import Struct\nfrom math import floor\n\nframe_rate = 11025\n\ndef encode(x):\n    \"\"\"Encode float x between -1 and 1 as two bytes.\n    (See https://docs.python.org/3/library/struct.html)\n    \"\"\"\n    i = int(16384 * x)\n    return Struct('h').pack(i)\n\ndef play(sampler, name='song.wav', seconds=2):\n    \"\"\"Write the output of a sampler function as a wav file.\n    (See https://docs.python.org/3/library/wave.html)\n    \"\"\"\n    out = open(name, 'wb')\n    out.setnchannels(1)\n    out.setsampwidth(2)\n    out.setframerate(frame_rate)\n    t = 0\n    while t < seconds * frame_rate:\n        sample = sampler(t)\n        out.writeframes(encode(sample))\n        t = t + 1\n    out.close()\n\ndef tri(frequency, amplitude=0.3):\n    \"\"\"A continuous triangle wave.\"\"\"\n    period = frame_rate // frequency    # 1 个周期中有 period 个采样点\n    def sampler(t):\n        saw_wave = t / period - floor(t / period + 0.5)\n        tri_wave = 2 * abs(2 * saw_wave) - 1\n        return amplitude * tri_wave\n    return sampler\n\nc_freq, e_freq, g_freq = 261.63, 329.63, 392.00\nc = tri(c_freq)\ne = tri(e_freq)\ng = tri(g_freq)\nlow_g = tri(g_freq / 2)\n\ndef both(f, g):\n    return lambda t: f(t) + g(t)\n\ndef note(f, start, end, fade=0.01):\n    \"\"\"Play f for a fixed duration.\"\"\"\n    def sampler(t):\n        seconds = t / frame_rate\n        if seconds < start:\n            return 0\n        elif seconds > end:\n            return 0\n        elif seconds < start + fade:\n            return (seconds - start) / fade * f(t)\n        elif seconds > end - fade:\n            return (end - seconds) / fade * f(t)\n        else:\n            return f(t)\n    return sampler\n\ndef mario(c, e, g, low_g):\n    z = 0\n    song = note(e, z, z + 1/8)\n    z += 1/8\n    song = both(song, note(e, z, z + 1/8))\n    z += 1/4\n    song = both(song, note(e, z, z + 1/8))\n    z += 1/4\n    song = both(song, note(c, z, z + 1/8))\n    z += 1/8\n    song = both(song, note(e, z, z + 1/8))\n    z += 1/4\n    song = both(song, note(g, z, z + 1/4))\n    z += 1/2\n    song = both(song, note(low_g, z, z + 1/4))\n    return song\n\ndef mario_at(octave):\n    c = tri(octave * c_freq)\n    e = tri(octave * e_freq)\n    g = tri(octave * g_freq)\n    low_g = tri(octave * g_freq / 2)\n    return mario(c, e, g, low_g)\n\nplay(both(mario_at(1), mario_at(1/2)))\n

^这段可以成功生成马里奥的开场音乐

\n","createdAt":"2023-07-06 18:28:31.184628","updatedAt":"2023-07-07 02:58:15.907361","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":458,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":219,"username":"Cqer","name":null}],"hasReacted":false}],"wiki":false,"version":3,"publicVersion":3,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":4261,"postNumber":23,"raw":"# [date-range from=2023-07-08 to=2023-07-09T12:00:00 timezone=\"Asia/Shanghai\"]\n讲的是 recursion, 讲的比较基础，书看完视频看完就过了，明天开始军训，希望能继续学.\n\n# 笔记\n## Ch.1.7 Recursive Functions\n\nA simple recursive function:\n\n````python\ndef sum_digits(n):\n \"\"\"Return the sum of the digits of positive integer n.\"\"\"\n if n < 10:\n return n\n else:\n all_but_last, last = n // 10, n % 10\n \treturn sum_digits(all_but_last) + last\n````\n\n### The Anatomy of Recursive Functions\n\nTreating a recursive call as a functional abstraction has been called a *recursive leap of faith*. We define a function in terms of itself, but simply trust that the simpler cases will work correctly when verifying the correctness of the function.\n\n### Mutual Recursion\n\nWhen a recursive procedure is divided among two functions that call each other, the functions are said to be *mutually recursive*. As an example, consider the following definition of even and odd for non-negative integers:\n\n- a number is even if it is one more than an odd number\n- a number is odd if it is one more than an even number\n- 0 is even\n\nUsing this definition, we can implement mutually recursive functions to determine whether a number is even or odd:\n\n````python\ndef is_even(n):\n if n == 0:\n return True\n else:\n return is_odd(n-1)\n \ndef is_odd(n):\n if n == 0:\n return False\n else:\n return is_even(n-1)\n````\n\nMutually recursive functions can be turned into a single recursive function by breaking the abstraction boundary between the two functions.\n\n````python\ndef is_even(n):\n if n == 0:\n return True\n else:\n if (n-1) == 0:\n return False\n else:\n return is_even((n-1)-1)\n````\n\n### Printing in Recursive Functions\n\n````python\ndef cascade(n):\n \"\"\"Print a cascade of prefixes of n.\n >>> cascade(1234)\n 1234\n 123\n 12\n 1\n 12\n 123\n 1234\n \"\"\"\n if n < 10:\n print(n)\n else:\n print(n)\n cascade(n//10)\n print(n)\n# this function can be expressed more compactly by observing that \n# print(n) is repeated in both clauses of the conditional statement\n\ndef cascade(n):\n print(n)\n if n >= 10:\n cascade(n//10)\n print(n)\n````\n\nThen consider a two-player game in which there are `n` initial pebbles on a table. The players take turns, removing either one or two pebbles from the table, and the player who removes the final pebble wins. Suppose that Alice and Bob play this game, each using a simple strategy:\n\n- Alice always removes a single pebble\n- Bob removes two pebbles if an even number of pebbles is on the table, and one otherwise\n\nGiven `n` initial pebbles and Alice starting, who wins the game?\n\nA natural decomposition of this problem is to encapsulate each strategy in its own function. This allows us to modify one strategy without affecting the other, maintaining the abstraction barrier between the two. In order to incorporate the turn-by-turn nature of the game, **these two functions call each other at the end of each turn**.\n\n````python\ndef play_alice(n):\n if n == 0:\n print(\"Bob wins!\")\n else:\n play_bob(n-1)\ndef play_bob(n):\n if n == 0:\n print(\"Alice wins!\")\n elif n % 2 == 0:\n play_alice(n-2)\n else:\n play_alice(n-1)\n````\n\n### Tree Recursion\n\nAnother common pattern of computation is called tree recursion, in which a function calls itself more than once. As an example, consider computing the sequence of Fibonacci numbers, in which each number is the sum of the preceding two.\n\n````python\ndef fib(n):\n if n == 1:\n return 0\n if n == 2:\n return 1\n else:\n return fib(n-2) + fib(n-1)\n````\n\n### Example: Partitions\n\nThe number of partitions of a positive integer `n`, using parts up to size `m`, is the number of ways in which `n` can be expressed as the sum of positive integer parts up to `m` in increasing order.\n\nThe number of ways to partition `n` using integers up to `m` equals\n\n1. the number of ways to partition `n-m` using integers up to `m`, and\n2. the number of ways to partition `n` using integers up to `m-1`.\n\nTo see why this is true, observe that all the ways of partitioning `n` can be divided into two groups: those that include at least one `m` and those that do not. Moreover, each partition in the first group is a partition of `n-m`, followed by `m` added at the end. In the example above, the first two partitions contain 4, and the rest do not.\n\nTherefore, we can recursively reduce the problem of partitioning `n` using integers up to `m` into two simpler problems: (1) partition a smaller number `n-m`, and (2) partition with smaller components up to `m-1`.\n\nTo complete the implementation, we need to specify the following base cases:\n\n1. There is one way to partition 0: include no parts.\n2. There are 0 ways to partition a negative `n`.\n3. There are 0 ways to partition any `n` greater than 0 using parts of size 0 or less.\n\n````python\ndef count_partitions(n, m):\n \"\"\"Count the ways to partition n using parts up to m.\"\"\"\n if n == 0:\n return 1\n elif n < 0:\n return 0\n elif m == 0:\n return 0\n else:\n return count_partitions(n-m, m) + count_partitions(n, m-1)\n````\n\nWe can think of a tree-recursive function as exploring different possibilities. In this case, we explore the possibility that we use a part of size `m` and the possibility that we do not. The first and second recursive calls correspond to these possibilities.","cooked":"

[date-range from=2023-07-08 to=2023-07-09T12:00:00 timezone=\"Asia/Shanghai\"]

讲的是 recursion, 讲的比较基础，书看完视频看完就过了，明天开始军训，希望能继续学.

笔记

Ch.1.7 Recursive Functions

A simple recursive function:

def sum_digits(n):\n    \"\"\"Return the sum of the digits of positive integer n.\"\"\"\n    if n < 10:\n        return n\n    else:\n        all_but_last, last = n // 10, n % 10\n    \treturn sum_digits(all_but_last) + last\n

The Anatomy of Recursive Functions

Treating a recursive call as a functional abstraction has been called a recursive leap of faith. We define a function in terms of itself, but simply trust that the simpler cases will work correctly when verifying the correctness of the function.

Mutual Recursion

When a recursive procedure is divided among two functions that call each other, the functions are said to be mutually recursive. As an example, consider the following definition of even and odd for non-negative integers:

a number is even if it is one more than an odd number
a number is odd if it is one more than an even number
0 is even

Using this definition, we can implement mutually recursive functions to determine whether a number is even or odd:

def is_even(n):\n    if n == 0:\n        return True\n    else:\n        return is_odd(n-1)\n    \ndef is_odd(n):\n    if n == 0:\n        return False\n    else:\n        return is_even(n-1)\n

Mutually recursive functions can be turned into a single recursive function by breaking the abstraction boundary between the two functions.

def is_even(n):\n    if n == 0:\n        return True\n    else:\n        if (n-1) == 0:\n            return False\n        else:\n            return is_even((n-1)-1)\n

Printing in Recursive Functions

def cascade(n):\n    \"\"\"Print a cascade of prefixes of n.\n    >>> cascade(1234)\n    1234\n    123\n    12\n    1\n    12\n    123\n    1234\n    \"\"\"\n    if n < 10:\n        print(n)\n    else:\n        print(n)\n        cascade(n//10)\n        print(n)\n# this function can be expressed more compactly by observing that \n# print(n) is repeated in both clauses of the conditional statement\n\ndef cascade(n):\n    print(n)\n    if n >= 10:\n        cascade(n//10)\n        print(n)\n

Then consider a two-player game in which there are n initial pebbles on a table. The players take turns, removing either one or two pebbles from the table, and the player who removes the final pebble wins. Suppose that Alice and Bob play this game, each using a simple strategy:

Alice always removes a single pebble
Bob removes two pebbles if an even number of pebbles is on the table, and one otherwise

Given n initial pebbles and Alice starting, who wins the game?

A natural decomposition of this problem is to encapsulate each strategy in its own function. This allows us to modify one strategy without affecting the other, maintaining the abstraction barrier between the two. In order to incorporate the turn-by-turn nature of the game, these two functions call each other at the end of each turn.

def play_alice(n):\n    if n == 0:\n        print(\"Bob wins!\")\n    else:\n        play_bob(n-1)\ndef play_bob(n):\n    if n == 0:\n        print(\"Alice wins!\")\n    elif n % 2 == 0:\n        play_alice(n-2)\n    else:\n        play_alice(n-1)\n

Tree Recursion

Another common pattern of computation is called tree recursion, in which a function calls itself more than once. As an example, consider computing the sequence of Fibonacci numbers, in which each number is the sum of the preceding two.

def fib(n):\n    if n == 1:\n        return 0\n    if n == 2:\n        return 1\n    else:\n        return fib(n-2) + fib(n-1)\n

Example: Partitions

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

The number of ways to partition n using integers up to m equals

the number of ways to partition n-m using integers up to m, and
the number of ways to partition n using integers up to m-1.

To see why this is true, observe that all the ways of partitioning n can be divided into two groups: those that include at least one m and those that do not. Moreover, each partition in the first group is a partition of n-m, followed by m added at the end. In the example above, the first two partitions contain 4, and the rest do not.

Therefore, we can recursively reduce the problem of partitioning n using integers up to m into two simpler problems: (1) partition a smaller number n-m, and (2) partition with smaller components up to m-1.

To complete the implementation, we need to specify the following base cases:

There is one way to partition 0: include no parts.
There are 0 ways to partition a negative n.
There are 0 ways to partition any n greater than 0 using parts of size 0 or less.

def count_partitions(n, m):\n    \"\"\"Count the ways to partition n using parts up to m.\"\"\"\n    if n == 0:\n        return 1\n    elif n < 0:\n        return 0\n    elif m == 0:\n        return 0\n    else:\n        return count_partitions(n-m, m) + count_partitions(n, m-1)\n

We can think of a tree-recursive function as exploring different possibilities. In this case, we explore the possibility that we use a part of size m and the possibility that we do not. The first and second recursive calls correspond to these possibilities.

\n","createdAt":"2023-07-09 03:25:02.528476","updatedAt":"2023-07-09 03:25:02.528476","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":902,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":8198,"postNumber":24,"raw":"时隔好久又回来了，说说最近干了什么吧:\n\n[quote=\"TsuinoSora, post:23, topic:1494\"]\n明天开始军训，希望能继续学.\n[/quote]\n7 月 28 日回复：然后军训期间我一直在间隙性玉玉，什么都没干\n\n军训后狠狠现充了几天，然后前几天一直在对着 [mdn](https://developer.mozilla.org/zh-CN/) 学前端，目前学了 [guides](https://developer.mozilla.org/zh-CN/docs/Learn) 里面的 html 和 css, js 只了解了 [web 入门](https://developer.mozilla.org/zh-CN/docs/Learn/Getting_started_with_the_web) 里的那点东西。之后计划和 cs61a 同步推进\n\n然后今天把 cs61a chapter 1 彻底结束了。明天希望可以再干点事情","cooked":"

时隔好久又回来了，说说最近干了什么吧:

\n\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\tTsuinoSora:\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t

\n\t\t\t\t\t\t\t

\n
明天开始军训，希望能继续学.
\n

\n\t\t\t\t\t\t

7 月 28 日回复：然后军训期间我一直在间隙性玉玉，什么都没干

军训后狠狠现充了几天，然后前几天一直在对着 mdn 学前端，目前学了 guides 里面的 html 和 css, js 只了解了 web 入门里的那点东西。之后计划和 cs61a 同步推进

然后今天把 cs61a chapter 1 彻底结束了。明天希望可以再干点事情

\n","createdAt":"2023-07-28 14:53:10.028654","updatedAt":"2023-07-28 14:53:10.028654","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":153,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":8671,"postNumber":25,"raw":"

\n最近在看教材，记了点笔记，感觉难度一般就没怎么更新\n另外最近在看前端三大件\n## Ch.2.1 Introduction\n\nEvery value in Python has a *class* that determines what type of value it is. Values that share a class also share behavior. For example, the integers `1` and `2` are both instances of the `int` class. \n\nPython includes three native numeric types: integers (`int`), real numbers (`float`), and complex numbers (`complex`).\n\n```python\n>>> type(1.5)\n\n>>> type(1+1j)\n\n```\n\n### Floats\n\nIn particular, `int` objects represent integers exactly, without any approximation or limits on their size. On the other hand, `float` objects can represent a wide range of fractional numbers, but not all numbers can be represented exactly, and there are minimum and maximum values. Therefore, `float` values should be treated as approximations to real values.\n\n```python\n>>> 7 / 3 * 3\n7.0\n>>> 1 / 3 * 7 * 3\n6.999999999999999\n```\n## Ch.2.2 Data Abstraction\n\nThe general technique of isolating the parts of a program that deal with how data are represented from the parts that deal with how data are manipulated is a powerful design methodology called *data abstraction*.\n\n### Example: Rational Numbers\n\nA rational number is a ratio of integers, and rational numbers constitute an important sub-class of real numbers. A rational number such as `1/3` or `17/29` is typically written as:\n\n```python\n/\n```\n\nwhere both the `` and `` are placeholders for integer values.\n\nActually dividing integers produces a `float` approximation, losing the exact precision of integers. However, we can create an exact representation for rational numbers by combining together the numerator and denominator.\n\n- `rational(n, d)` returns the rational number with numerator `n` and denominator `d`.\n- `numer(x)` returns the numerator of the rational number `x`.\n- `denom(x)` returns the denominator of the rational number `x`.\n\nWe are using here a powerful strategy for designing programs: *wishful thinking*. We haven't yet said how a rational number is represented, or how the functions `numer`, `denom`, and `rational` should be implemented. Even so, if we did define these three functions, we could then add, multiply, print, and test equality of rational numbers:\n\n```python\n>>> def add_rationals(x, y):\n nx, dx = numer(x), denom(x)\n ny, dy = numer(y), denom(y)\n return rational(nx * dy + ny * dx, dx * dy)\n>>> def mul_rationals(x, y):\n return rational(numer(x) * numer(y), denom(x) * denom(y))\n>>> def print_rational(x):\n print(numer(x), '/', denom(x))\n>>> def rationals_are_equal(x, y):\n return numer(x) * denom(y) == numer(y) * denom(x)\n```\n\nNow we have the operations on rational numbers defined in terms of the selector functions `numer` and `denom`, and the constructor function `rational`, but we haven't yet defined these functions. What we need is some way to glue together a numerator and a denominator into a compound value.\n\n### Pairs\n\nUnpack a list into its elements and binds each element to a different name\n\n```python\n>>> pair = [10, 20]\n>>> x, y = pair\n>>> x\n10\n>>> y\n20\n```\n\nTwo-element lists are not the only method of representing pairs in Python. Any way of bundling two values together into one can be considered a pair. Lists are a common method to do so.\n\nWe can now represent a rational number as a pair of two integers: a numerator and a denominator.\n\n```python\n>>> from fractions import gcd\n>>> def rational(n, d):\n g = gcd(n, d)\n return (n//g, d//g)\n>>> def numer(x):\n return x[0]\n>>> def denom(x):\n return x[1]\n```\n\nTogether with the arithmetic operations we defined earlier, we can manipulate rational numbers with the functions we have defined.\n\nThis improvement was accomplished by changing the constructor without changing any of the functions that implement the actual arithmetic operations.\n\n### Abstraction Barriers\n\nAn abstraction barrier violation occurs whenever a part of the program that can use a higher level function instead uses a function in a lower level. For example, a function that computes the square of a rational number is best implemented in terms of `mul_rational`, which does not assume anything about the implementation of a rational number.\n\n```python\n>>> def square_rational(x):\n return mul_rational(x, x)\n```\n\nReferring directly to numerators and denominators would violate one abstraction barrier.\n\n```python\n>>> def square_rational_violating_once(x):\n return rational(numer(x) * numer(x), denom(x) * denom(x))\n```\n\nAssuming that rationals are represented as two-element lists would violate two abstraction barriers.\n\n```python\n>>> def square_rational_violating_twice(x):\n return [x[0] * x[0], x[1] * x[1]]\n```\n\nAbstraction barriers make programs easier to maintain and to modify. The fewer functions that depend on a particular representation, the fewer changes are required when one wants to change that representation. All of these implementations of `square_rational` have the correct behavior, but only the first is robust to future changes. The `square_rational` function would not require updating even if we altered the representation of rational numbers. By contrast, `square_rational_violating_once` would need to be changed whenever the selector or constructor signatures changed, and `square_rational_violating_twice` would require updating whenever the implementation of rational numbers changed.\n\n### The Properties of Data\n\nAbstraction barriers shape the way in which we think about data. A valid representation of a rational number is not restricted to any particular implementation (such as a two-element list); it is a value returned by `rational` that can be passed to `numer`, and `denom`. In addition, the appropriate relationship must hold among the constructor and selectors. That is, if we construct a rational number `x` from integers `n` and `d`, then it should be the case that `numer(x)/denom(x)` is equal to `n/d`.\n\nThis point of view can be applied broadly, including to the pair values that we used to implement rational numbers. We never actually said much about what a pair was, only that the language supplied the means to create and manipulate lists with two elements. The behavior we require to implement a pair is that it glues two values together. Stated as a behavior condition,\n\n- If a pair `p` was constructed from values `x` and `y`, then `select(p, 0)` returns `x`, and `select(p, 1)` returns `y`.\n\nWe don't actually need the `list` type to create pairs. Instead, we can implement two functions `pair` and `select` that fulfill this description just as well as a two-element list.\n\n```python\n>>> def pair(x, y):\n \"\"\"Return a function that represents a pair.\"\"\"\n def get(index):\n if index == 0:\n return x\n elif index == 1:\n return y\n return get\n>>> def select(p, i):\n \"\"\"Return the element at index i of pair p.\"\"\"\n return p(i)\n```\n\nWith this implementation, we can create and manipulate pairs.\n\n```python\n>>> p = pair(20, 14)\n>>> select(p, 0)\n20\n>>> select(p, 1)\n14\n```\n## Ch.2.3 Sequences\n\nSequences are not instances of a particular built-in type or abstract data representation, but instead a collection of behaviors that are shared among several different types of data.\n\n### Lists\n\n```python\n>>> digits = [1, 8, 2, 8]\n>>> len(digits)\n4\n>>> digits[3]\n8\n>>> [2, 7] + digits * 2\n[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]\n# Any values can be included in a list, including another list.\n>>> pairs = [[10, 20], [30, 40]]\n>>> pairs[1]\n[30, 40]\n>>> pairs[1][0]\n30\n```\n\n### Sequence Iteration\n\nThe Python `for` statement can simplify the while loop which can traversal the whole list by iterating over the element values directly without introducing the name `index` at all.\n\n```python\n>>> def count(s, value):\n \"\"\"Count the number of occurrences of value in sequence s.\"\"\"\n total = 0\n for elem in s:\n if elem == value:\n total = total + 1\n return total\n>>> count(digits, 8)\n2\n```\n\nA `for` statement consists of a single clause with the form:\n\n```python\nfor in :\n \n```\n\nA `for` statement is executed by the following procedure:\n\n1. Evaluate the header ``, which must yield an iterable value.\n2. For each element value in that iterable value, in order:\n 1. Bind `` to that value in the current frame.\n 2. Execute the ``.\n\n> This execution procedure refers to *iterable values*. Lists are a type of sequence, and sequences are iterable values. Their elements are considered in their sequential order. Python includes other iterable types, but we will focus on sequences for now\n\n#### Sequence unpacking \n\nA common pattern in programs is to have a sequence of elements that are themselves sequences, but all of a fixed length. A `for` statement may include multiple names in its header to \"unpack\" each element sequence into its respective elements.\n\n```python\n>>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]\n```\n\nand wish to find the number of these pairs that have the same first and second element.\n\n```python\n>>> same_count = 0\n```\n\nThe following `for` statement with two names in its header will bind each name `x` and `y` to the first and second elements in each pair, respectively.\n\n```python\n>>> for x, y in pairs:\n if x == y:\n same_count = same_count + 1\n>>> same_count\n2\n```\n\n#### Ranges\n\nA `range` is **another built-in type of sequence** in Python, which represents a range of integers. Ranges are created with `range`, which takes two integer arguments: the first number and one beyond the last number in the desired range.\n\n```python\n>>> range(1, 10) # Includes 1, but not 10\nrange(1, 10)\n>>> type(range(1, 10))\n\n```\n\nCalling the `list` constructor on a range evaluates to a list with the same elements as the range, so that the elements can be easily inspected.\n\n```python\n>>> list(range(5, 8))\n[5, 6, 7]\n```\n\nIf only one argument is given, it is interpreted as one beyond the last value for a range that starts at 0.\n\n```python\n>>> list(range(4))\n[0, 1, 2, 3]\n```\n\nRanges commonly appear as the expression in a `for` header to specify the number of times that the suite should be executed: A common convention is to use a single underscore character for the name in the `for` header if the name is unused in the suite:\n\n```python\n>>> for _ in range(3):\n print('Go Bears!')\n```\n\n### Sequence Processing\n\n#### List Comprehensions\n\nMany sequence processing operations can be expressed by evaluating a fixed expression for each element in a sequence and collecting the resulting values in a result sequence. In Python, a list comprehension is an expression that performs such a computation.\n\n````python\n>>> odds = [1, 3, 5, 7, 9]\n>>> [x+1 for x in odds]\n[2, 4, 6, 8, 10]\n````\n\nAnother common sequence processing operation is to select a subset of values that satisfy some condition.\n\n```python\n>>> [x for x in odds if 25 % x == 0]\n[1, 5]\n```\n\nThe general form of a list comprehension is:\n\n```python\n[ for in if ]\n```\n\n#### Aggregation\n\nA third common pattern in sequence processing is to aggregate all values in a sequence into a single value. The built-in functions `sum`, `min`, and `max` are all examples of aggregation functions.\n\n> By combining the patterns of evaluating an expression for each element, selecting a subset of elements, and aggregating elements, we can solve problems using a sequence processing approach.\n>\n> A perfect number is a positive integer that is equal to the sum of its divisors. The divisors of `n` are positive integers less than `n` that divide evenly into `n`. Listing the divisors of `n` can be expressed with a list comprehension.\n>\n> ```python\n> >>> def divisors(n):\n> return [1] + [x for x in range(2, n) if n % x == 0]\n> >>> divisors(4)\n> [1, 2]\n> >>> divisors(12)\n> [1, 2, 3, 4, 6]\n> ```\n>\n> Using `divisors`, we can compute all perfect numbers from 1 to 1000 with another list comprehension. (1 is typically considered to be a perfect number as well, but it does not qualify under our definition of `divisors`.)\n>\n> ```python\n> >>> [n for n in range(1, 1000) if sum(divisors(n)) == n]\n> [6, 28, 496]\n> ```\n\n#### Higher-Order Functions\n\nMany forms of aggregation can be expressed as repeatedly applying a two-argument function to the `reduced` value so far and each element in turn.\n\n```python\n>>> def reduce(reduce_fn, s, initial):\n reduced = initial\n for x in s:\n reduced = reduce_fn(reduced, x)\n return reduced\n```\n\nFor example, `reduce` can be used to multiply together all elements of a sequence. Using `mul` as the `reduce_fn` and 1 as the `initial` value, `reduce` can be used to multiply together a sequence of numbers.\n\n#### Conventional Names\n\nIn Python, the built-in `map` and `filter` are generalizations of these functions that do not return lists. These functions are discussed in Chapter 4. The definitions above are equivalent to applying the `list` constructor to the result of built-in `map` and `filter` calls.\n\n```python\n>>> apply_to_all = lambda map_fn, s: list(map(map_fn, s))\n>>> keep_if = lambda filter_fn, s: list(filter(filter_fn, s))\n```\n\nThe `reduce` function is built into the `functools` module of the Python standard library. In this version, the `initial` argument is optional.\n\n```python\n>>> from functools import reduce\n>>> from operator import mul\n>>> def product(s):\n return reduce(mul, s)\n>>> product([1, 2, 3, 4, 5])\n120\n```\n\n### Sequence Abstraction\n\n> We have introduced two native data types that satisfy the sequence abstraction: lists and ranges. Both satisfy the conditions with which we began this section: length and element selection. Python includes two more behaviors of sequence types that extend the sequence abstraction.\n\n#### Membership\n\nPython has two operators `in` and `not in` that evaluate to `True` or `False` depending on whether an element appears in a sequence\n\n#### Slicing\n\nA *slice* of a sequence is any contiguous span of the original sequence, designated by a pair of integers. As with the `range` constructor, the first integer indicates the starting index of the slice and the second indicates one beyond the ending index.\n\nIn Python, sequence slicing is expressed similarly to element selection, using square brackets. A colon separates the starting and ending indices. Any bound that is omitted is assumed to be an extreme value: 0 for the starting index, and the length of the sequence for the ending index.\n\n### Strings\n\nThe native data type for text in Python is called a string, and corresponds to the constructor `str`.\n\n- String literals can express arbitrary text, surrounded by either single or double quotation marks.\n - We have seen strings already in our code, as docstrings, in calls to `print`, and as error messages in `assert` statements.\n\n- Strings satisfy the two basic conditions of a sequence that we introduced at the beginning of this section: they have a length and they support element selection.\n- The elements of a string are themselves strings that have only a single character. A character is any single letter of the alphabet, punctuation mark, or other symbol. Unlike many other programming languages, Python does not have a separate character type; any text is a string, and strings that represent single characters have a length of 1.\n- Like lists, strings can also be combined via addition and multiplication.\n\n#### Membership\n\nThe membership operator `in` applies to strings, but has an entirely different behavior than when it is applied to sequences. It matches substrings rather than elements.\n\n```python\n>>> 'here' in \"Where's Waldo?\"\nTrue\n```\n\n#### Multiline Literals\n\nStrings aren't limited to a single line. Triple quotes delimit string literals that span multiple lines. We have used this triple quoting extensively already for docstrings.\n\n```python\n>>> \"\"\"The Zen of Python\nclaims, Readability counts.\nRead more: import this.\"\"\"\n'The Zen of Python\\nclaims, \"Readability counts.\"\\nRead more: import this.'\n```\n\nIn the printed result above, the `\\n` (pronounced \"*backslash en*\") is a single element that represents a new line. Although it appears as two characters (backslash and \"n\"), it is considered a single character for the purposes of length and element selection.\n\n#### String Coercion\n\n A string can be created from any object in Python by calling the `str` constructor function with an object value as its argument. This feature of strings is useful for constructing descriptive strings from objects of various types.\n\n```python\n>>> str(2) + ' is an element of ' + str(digits)\n'2 is an element of [1, 8, 2, 8]'\n```\n\n### Trees\n\n> Our ability to use lists as the elements of other lists provides a new means of combination in our programming language. This ability is called a *closure property* of a data type. In general, a method for combining data values has a closure property if the result of combination can itself be combined using the same method. Closure is the key to power in any means of combination because it permits us to create hierarchical structures — structures made up of parts, which themselves are made up of parts, and so on.\n\nNesting lists within lists can introduce complexity. The *tree* is a fundamental data abstraction that imposes regularity on how hierarchical values are structured and manipulated.\n\nA tree has a root label and a sequence of branches. Each branch of a tree is a tree. A tree with no branches is called a leaf. Any tree contained within a tree is called a sub-tree of that tree (such as a branch of a branch). The root of each sub-tree of a tree is called a node in that tree.\n\nThe data abstraction for a tree consists of the constructor `tree` and the selectors `label` and `branches`. We begin with a simplified version.\n\n```python\n>>> def tree(root_label, branches=[]):\n for branch in branches:\n assert is_tree(branch), 'branches must be trees'\n return [root_label] + list(branches)\n>>> def label(tree):\n return tree[0]\n>>> def branches(tree):\n return tree[1:]\n```\n\nA tree is well-formed only if it has a root label and all branches are also trees. The `is_tree` function is applied in the `tree` constructor to verify that all branches are well-formed.\n\n```python\n>>> def is_tree(tree):\n if type(tree) != list or len(tree) < 1:\n return False\n for branch in branches(tree):\n if not is_tree(branch):\n return False\n return True\n```\n\nThe `is_leaf` function checks whether or not a tree has branches.\n\n```python\n>>> def is_leaf(tree):\n return not branches(tree)\n```\n\nTrees can be constructed by nested expressions. The following tree `t` has root label 3 and two branches.\n\n```python\n>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])\n>>> t\n[3, [1], [2, [1], [1]]]\n>>> label(t)\n3\n>>> branches(t)\n[[1], [2, [1], [1]]]\n>>> label(branches(t)[1])\n2\n>>> is_leaf(t)\nFalse\n>>> is_leaf(branches(t)[0])\nTrue\n```\n\nTree-recursive functions can be used to construct trees. For example, the nth Fibonacci tree has a root label of the nth Fibonacci number and, for `n > 1`, two branches that are also Fibonacci trees. A Fibonacci tree illustrates the tree-recursive computation of a Fibonacci number.\n\n```python\n>>> def fib_tree(n):\n if n == 0 or n == 1:\n return tree(n)\n else:\n left, right = fib_tree(n-2), fib_tree(n-1)\n fib_n = label(left) + label(right)\n return tree(fib_n, [left, right])\n>>> fib_tree(5)\n[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]\n```\n\nTree-recursive functions are also used to process trees. For example, the `count_leaves` function counts the leaves of a tree.\n\n```python\n>>> def count_leaves(tree):\n if is_leaf(tree):\n return 1\n else:\n branch_counts = [count_leaves(b) for b in branches(tree)]\n return sum(branch_counts)\n>>> count_leaves(fib_tree(5))\n8\n```\n\n#### Partition trees\n\nTrees can also be used to represent the partitions of an integer. A partition tree for `n` using parts up to size `m` is a binary (two branch) tree that represents the choices taken during computation. In a non-leaf partition tree:\n\n- the left (index 0) branch contains all ways of partitioning `n` using at least one `m`,\n- the right (index 1) branch contains partitions using parts up to `m-1`, and\n- the root label is `m`.\n\nThe labels at the leaves of a partition tree express whether the path from the root of the tree to the leaf represents a successful partition of `n`.\n\n```python\n>>> def partition_tree(n, m):\n \"\"\"Return a partition tree of n using parts of up to m.\"\"\"\n if n == 0:\n return tree(True)\n elif n < 0 or m == 0:\n return tree(False)\n else:\n left = partition_tree(n-m, m)\n right = partition_tree(n, m-1)\n return tree(m, [left, right])\n>>> partition_tree(2, 2)\n[2, [True], [1, [1, [True], [False]], [False]]]\n```\n\nPrinting the partitions from a partition tree is another tree-recursive process that traverses the tree, constructing each partition as a list. Whenever a `True` leaf is reached, the partition is printed.\n\n```python\n>>> def print_parts(tree, partition=[]):\n if is_leaf(tree):\n if label(tree):\n print(' + '.join(partition))\n else:\n left, right = branches(tree)\n m = str(label(tree))\n print_parts(left, partition + [m])\n print_parts(right, partition)\n>>> print_parts(partition_tree(6, 4))\n4 + 2\n4 + 1 + 1\n3 + 3\n3 + 2 + 1\n3 + 1 + 1 + 1\n2 + 2 + 2\n2 + 2 + 1 + 1\n2 + 1 + 1 + 1 + 1\n1 + 1 + 1 + 1 + 1 + 1\n```\n\nSlicing can be used on the branches of a tree as well. For example, we may want to place a restriction on the number of branches in a tree. A binary tree is either a leaf or a sequence of at most two binary trees. A common tree transformation called *binarization* computes a binary tree from an original tree by grouping together adjacent branches.\n\n```python\n>>> def right_binarize(tree):\n \"\"\"Construct a right-branching binary tree.\"\"\"\n if is_leaf(tree):\n return tree\n if len(tree) > 2:\n tree = [tree[0], tree[1:]]\n return [right_binarize(b) for b in tree]\n>>> right_binarize([1, 2, 3, 4, 5, 6, 7])\n[1, [2, [3, [4, [5, [6, 7]]]]]]\n```\n\n### Linked Lists\n\nSo far, we have used only native types to represent sequences. However, we can also develop sequence representations that are not built into Python. A common representation of a sequence constructed from nested pairs is called a *linked list*. The environment diagram below illustrates the linked list representation of a four-element sequence containing 1, 2, 3, and 4.\n\n![linked_list|689x114](/uploads/image/76/6d/766dff69ccbdc83829afeb0b3db8803c6ec1c072d1a97dd6118067820169a185.avif)\n\nA linked list is a pair containing the first element of the sequence (in this case 1) and the rest of the sequence (in this case a representation of 2, 3, 4). The second element is also a linked list. The rest of the inner-most linked list containing only 4 is `'empty'`, a value that represents an empty linked list.\n\nLinked lists have recursive structure: the rest of a linked list is a linked list or `'empty'`. We can define an abstract data representation to validate, construct, and select the components of linked lists.\n\n```python\n>>> empty = 'empty'\n>>> def is_link(s):\n \"\"\"s is a linked list if it is empty or a (first, rest) pair.\"\"\"\n return s == empty or (len(s) == 2 and is_link(s[1]))\n>>> def link(first, rest):\n \"\"\"Construct a linked list from its first element and the rest.\"\"\"\n assert is_link(rest), \"rest must be a linked list.\"\n return [first, rest]\n>>> def first(s):\n \"\"\"Return the first element of a linked list s.\"\"\"\n assert is_link(s), \"first only applies to linked lists.\"\n assert s != empty, \"empty linked list has no first element.\"\n return s[0]\n>>> def rest(s):\n \"\"\"Return the rest of the elements of a linked list s.\"\"\"\n assert is_link(s), \"rest only applies to linked lists.\"\n assert s != empty, \"empty linked list has no rest.\"\n return s[1]\n```\n\nAbove, `link` is a constructor and `first` and `rest` are selectors for an abstract data representation of linked lists. The behavior condition for a linked list is that, like a pair, its constructor and selectors are inverse functions.\n\nWe can use the constructor and selectors to manipulate linked lists.\n\n```python\n>>> four = link(1, link(2, link(3, link(4, empty))))\n>>> first(four)\n1\n>>> rest(four)\n[2, [3, [4, 'empty']]]\n```\n\nThe linked list can store a sequence of values in order, but we have not yet shown that it satisfies the sequence abstraction. Using the abstract data representation we have defined, we can implement the two behaviors that characterize a sequence: length and element selection.\n\n```python\n>>> def len_link(s):\n \"\"\"Return the length of linked list s.\"\"\"\n length = 0\n while s != empty:\n s, length = rest(s), length + 1\n return length\n>>> def getitem_link(s, i):\n \"\"\"Return the element at index i of linked list s.\"\"\"\n while i > 0:\n s, i = rest(s), i - 1\n return first(s)\n>>> len_link(four)\n4\n>>> getitem_link(four, 1)\n2\n```\n\n**Recursive manipulation.** Both `len_link` and `getitem_link` are iterative. They peel away each layer of nested pair until the end of the list (in `len_link`) or the desired element (in `getitem_link`) is reached. We can also implement length and element selection using recursion.\n\n```python\n>>> def len_link_recursive(s):\n \"\"\"Return the length of a linked list s.\"\"\"\n if s == empty:\n return 0\n return 1 + len_link_recursive(rest(s))\n>>> def getitem_link_recursive(s, i):\n \"\"\"Return the element at index i of linked list s.\"\"\"\n if i == 0:\n return first(s)\n return getitem_link_recursive(rest(s), i - 1)\n```\n\nRecursion is also useful for transforming and combining linked lists.\n\n```python\n>>> def extend_link(s, t):\n \"\"\"Return a list with the elements of s followed by those of t.\"\"\"\n assert is_link(s) and is_link(t)\n if s == empty:\n return t\n else:\n return link(first(s), extend_link(rest(s), t))\n>>> extend_link(four, four)\n[1, [2, [3, [4, [1, [2, [3, [4, 'empty']]]]]]]]\n>>> def apply_to_all_link(f, s):\n \"\"\"Apply f to each element of s.\"\"\"\n assert is_link(s)\n if s == empty:\n return s\n else:\n return link(f(first(s)), apply_to_all_link(f, rest(s)))\n>>> apply_to_all_link(lambda x: x*x, four)\n[1, [4, [9, [16, 'empty']]]]\n>>> def keep_if_link(f, s):\n \"\"\"Return a list with elements of s for which f(e) is true.\"\"\"\n assert is_link(s)\n if s == empty:\n return s\n else:\n kept = keep_if_link(f, rest(s))\n if f(first(s)):\n return link(first(s), kept)\n else:\n return kept\n>>> keep_if_link(lambda x: x%2 == 0, four)\n[2, [4, 'empty']]\n>>> def join_link(s, separator):\n \"\"\"Return a string of all elements in s separated by separator.\"\"\"\n if s == empty:\n return \"\"\n elif rest(s) == empty:\n return str(first(s))\n else:\n return str(first(s)) + separator + join_link(rest(s), separator)\n>>> join_link(four, \", \")\n'1, 2, 3, 4'\n```","cooked":"

\n最近在看教材，记了点笔记，感觉难度一般就没怎么更新\n另外最近在看前端三大件\n## Ch.2.1 Introduction\n

Every value in Python has a class that determines what type of value it is. Values that share a class also share behavior. For example, the integers 1 and 2 are both instances of the int class.

Python includes three native numeric types: integers (int), real numbers (float), and complex numbers (complex).

>>> type(1.5)\n<class 'float'>\n>>> type(1+1j)\n<class 'complex'>\n

Floats

In particular, int objects represent integers exactly, without any approximation or limits on their size. On the other hand, float objects can represent a wide range of fractional numbers, but not all numbers can be represented exactly, and there are minimum and maximum values. Therefore, float values should be treated as approximations to real values.

>>> 7 / 3 * 3\n7.0\n>>> 1 / 3 * 7 * 3\n6.999999999999999\n

Ch.2.2 Data Abstraction

The general technique of isolating the parts of a program that deal with how data are represented from the parts that deal with how data are manipulated is a powerful design methodology called data abstraction.

Example: Rational Numbers

A rational number is a ratio of integers, and rational numbers constitute an important sub-class of real numbers. A rational number such as 1/3 or 17/29 is typically written as:

<numerator>/<denominator>\n

where both the <numerator> and <denominator> are placeholders for integer values.

Actually dividing integers produces a float approximation, losing the exact precision of integers. However, we can create an exact representation for rational numbers by combining together the numerator and denominator.

rational(n, d) returns the rational number with numerator n and denominator d.
numer(x) returns the numerator of the rational number x.
denom(x) returns the denominator of the rational number x.

We are using here a powerful strategy for designing programs: wishful thinking. We haven't yet said how a rational number is represented, or how the functions numer, denom, and rational should be implemented. Even so, if we did define these three functions, we could then add, multiply, print, and test equality of rational numbers:

>>> def add_rationals(x, y):\n        nx, dx = numer(x), denom(x)\n        ny, dy = numer(y), denom(y)\n        return rational(nx * dy + ny * dx, dx * dy)\n>>> def mul_rationals(x, y):\n        return rational(numer(x) * numer(y), denom(x) * denom(y))\n>>> def print_rational(x):\n        print(numer(x), '/', denom(x))\n>>> def rationals_are_equal(x, y):\n        return numer(x) * denom(y) == numer(y) * denom(x)\n

Now we have the operations on rational numbers defined in terms of the selector functions numer and denom, and the constructor function rational, but we haven't yet defined these functions. What we need is some way to glue together a numerator and a denominator into a compound value.

Pairs

Unpack a list into its elements and binds each element to a different name

>>> pair = [10, 20]\n>>> x, y = pair\n>>> x\n10\n>>> y\n20\n

Two-element lists are not the only method of representing pairs in Python. Any way of bundling two values together into one can be considered a pair. Lists are a common method to do so.

We can now represent a rational number as a pair of two integers: a numerator and a denominator.

>>> from fractions import gcd\n>>> def rational(n, d):\n        g = gcd(n, d)\n        return (n//g, d//g)\n>>> def numer(x):\n        return x[0]\n>>> def denom(x):\n        return x[1]\n

Together with the arithmetic operations we defined earlier, we can manipulate rational numbers with the functions we have defined.

This improvement was accomplished by changing the constructor without changing any of the functions that implement the actual arithmetic operations.

Abstraction Barriers

An abstraction barrier violation occurs whenever a part of the program that can use a higher level function instead uses a function in a lower level. For example, a function that computes the square of a rational number is best implemented in terms of mul_rational, which does not assume anything about the implementation of a rational number.

>>> def square_rational(x):\n        return mul_rational(x, x)\n

Referring directly to numerators and denominators would violate one abstraction barrier.

>>> def square_rational_violating_once(x):\n        return rational(numer(x) * numer(x), denom(x) * denom(x))\n

Assuming that rationals are represented as two-element lists would violate two abstraction barriers.

>>> def square_rational_violating_twice(x):\n        return [x[0] * x[0], x[1] * x[1]]\n

Abstraction barriers make programs easier to maintain and to modify. The fewer functions that depend on a particular representation, the fewer changes are required when one wants to change that representation. All of these implementations of square_rational have the correct behavior, but only the first is robust to future changes. The square_rational function would not require updating even if we altered the representation of rational numbers. By contrast, square_rational_violating_once would need to be changed whenever the selector or constructor signatures changed, and square_rational_violating_twice would require updating whenever the implementation of rational numbers changed.

The Properties of Data

Abstraction barriers shape the way in which we think about data. A valid representation of a rational number is not restricted to any particular implementation (such as a two-element list); it is a value returned by rational that can be passed to numer, and denom. In addition, the appropriate relationship must hold among the constructor and selectors. That is, if we construct a rational number x from integers n and d, then it should be the case that numer(x)/denom(x) is equal to n/d.

This point of view can be applied broadly, including to the pair values that we used to implement rational numbers. We never actually said much about what a pair was, only that the language supplied the means to create and manipulate lists with two elements. The behavior we require to implement a pair is that it glues two values together. Stated as a behavior condition,

If a pair p was constructed from values x and y, then select(p, 0) returns x, and select(p, 1) returns y.

We don't actually need the list type to create pairs. Instead, we can implement two functions pair and select that fulfill this description just as well as a two-element list.

>>> def pair(x, y):\n        \"\"\"Return a function that represents a pair.\"\"\"\n        def get(index):\n            if index == 0:\n                return x\n            elif index == 1:\n                return y\n        return get\n>>> def select(p, i):\n        \"\"\"Return the element at index i of pair p.\"\"\"\n        return p(i)\n

With this implementation, we can create and manipulate pairs.

>>> p = pair(20, 14)\n>>> select(p, 0)\n20\n>>> select(p, 1)\n14\n

Ch.2.3 Sequences

Sequences are not instances of a particular built-in type or abstract data representation, but instead a collection of behaviors that are shared among several different types of data.

Lists

>>> digits = [1, 8, 2, 8]\n>>> len(digits)\n4\n>>> digits[3]\n8\n>>> [2, 7] + digits * 2\n[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]\n# Any values can be included in a list, including another list.\n>>> pairs = [[10, 20], [30, 40]]\n>>> pairs[1]\n[30, 40]\n>>> pairs[1][0]\n30\n

Sequence Iteration

The Python for statement can simplify the while loop which can traversal the whole list by iterating over the element values directly without introducing the name index at all.

>>> def count(s, value):\n        \"\"\"Count the number of occurrences of value in sequence s.\"\"\"\n        total = 0\n        for elem in s:\n            if elem == value:\n                total = total + 1\n        return total\n>>> count(digits, 8)\n2\n

A for statement consists of a single clause with the form:

for <name> in <expression>:\n    <suite>\n

A for statement is executed by the following procedure:

Evaluate the header <expression>, which must yield an iterable value.
For each element value in that iterable value, in order:\n
1. Bind <name> to that value in the current frame.
2. Execute the <suite>.
\n

\n
This execution procedure refers to iterable values. Lists are a type of sequence, and sequences are iterable values. Their elements are considered in their sequential order. Python includes other iterable types, but we will focus on sequences for now
\n

Sequence unpacking

A common pattern in programs is to have a sequence of elements that are themselves sequences, but all of a fixed length. A for statement may include multiple names in its header to \"unpack\" each element sequence into its respective elements.

>>> pairs = [[1, 2], [2, 2], [2, 3], [4, 4]]\n

and wish to find the number of these pairs that have the same first and second element.

>>> same_count = 0\n

The following for statement with two names in its header will bind each name x and y to the first and second elements in each pair, respectively.

>>> for x, y in pairs:\n        if x == y:\n            same_count = same_count + 1\n>>> same_count\n2\n

Ranges

A range is another built-in type of sequence in Python, which represents a range of integers. Ranges are created with range, which takes two integer arguments: the first number and one beyond the last number in the desired range.

>>> range(1, 10)  # Includes 1, but not 10\nrange(1, 10)\n>>> type(range(1, 10))\n<class 'range'>\n

Calling the list constructor on a range evaluates to a list with the same elements as the range, so that the elements can be easily inspected.

>>> list(range(5, 8))\n[5, 6, 7]\n

If only one argument is given, it is interpreted as one beyond the last value for a range that starts at 0.

>>> list(range(4))\n[0, 1, 2, 3]\n

Ranges commonly appear as the expression in a for header to specify the number of times that the suite should be executed: A common convention is to use a single underscore character for the name in the for header if the name is unused in the suite:

>>> for _ in range(3):\n        print('Go Bears!')\n

Sequence Processing

List Comprehensions

Many sequence processing operations can be expressed by evaluating a fixed expression for each element in a sequence and collecting the resulting values in a result sequence. In Python, a list comprehension is an expression that performs such a computation.

>>> odds = [1, 3, 5, 7, 9]\n>>> [x+1 for x in odds]\n[2, 4, 6, 8, 10]\n

Another common sequence processing operation is to select a subset of values that satisfy some condition.

>>> [x for x in odds if 25 % x == 0]\n[1, 5]\n

The general form of a list comprehension is:

[<map expression> for <name> in <sequence expression> if <filter expression>]\n

Aggregation

A third common pattern in sequence processing is to aggregate all values in a sequence into a single value. The built-in functions sum, min, and max are all examples of aggregation functions.

\n
By combining the patterns of evaluating an expression for each element, selecting a subset of elements, and aggregating elements, we can solve problems using a sequence processing approach.
\n
A perfect number is a positive integer that is equal to the sum of its divisors. The divisors of n are positive integers less than n that divide evenly into n. Listing the divisors of n can be expressed with a list comprehension.
\n
>>> def divisors(n):\n     return [1] + [x for x in range(2, n) if n % x == 0]\n>>> divisors(4)\n[1, 2]\n>>> divisors(12)\n[1, 2, 3, 4, 6]\n
\n
Using divisors, we can compute all perfect numbers from 1 to 1000 with another list comprehension. (1 is typically considered to be a perfect number as well, but it does not qualify under our definition of divisors.)
\n
>>> [n for n in range(1, 1000) if sum(divisors(n)) == n]\n[6, 28, 496]\n
\n

Higher-Order Functions

Many forms of aggregation can be expressed as repeatedly applying a two-argument function to the reduced value so far and each element in turn.

>>> def reduce(reduce_fn, s, initial):\n        reduced = initial\n        for x in s:\n            reduced = reduce_fn(reduced, x)\n        return reduced\n

For example, reduce can be used to multiply together all elements of a sequence. Using mul as the reduce_fn and 1 as the initial value, reduce can be used to multiply together a sequence of numbers.

Conventional Names

In Python, the built-in map and filter are generalizations of these functions that do not return lists. These functions are discussed in Chapter 4. The definitions above are equivalent to applying the list constructor to the result of built-in map and filter calls.

>>> apply_to_all = lambda map_fn, s: list(map(map_fn, s))\n>>> keep_if = lambda filter_fn, s: list(filter(filter_fn, s))\n

The reduce function is built into the functools module of the Python standard library. In this version, the initial argument is optional.

>>> from functools import reduce\n>>> from operator import mul\n>>> def product(s):\n        return reduce(mul, s)\n>>> product([1, 2, 3, 4, 5])\n120\n

Sequence Abstraction

\n
We have introduced two native data types that satisfy the sequence abstraction: lists and ranges. Both satisfy the conditions with which we began this section: length and element selection. Python includes two more behaviors of sequence types that extend the sequence abstraction.
\n

Membership

Python has two operators in and not in that evaluate to True or False depending on whether an element appears in a sequence

Slicing

A slice of a sequence is any contiguous span of the original sequence, designated by a pair of integers. As with the range constructor, the first integer indicates the starting index of the slice and the second indicates one beyond the ending index.

In Python, sequence slicing is expressed similarly to element selection, using square brackets. A colon separates the starting and ending indices. Any bound that is omitted is assumed to be an extreme value: 0 for the starting index, and the length of the sequence for the ending index.

Strings

The native data type for text in Python is called a string, and corresponds to the constructor str.

\n
String literals can express arbitrary text, surrounded by either single or double quotation marks.
\n
- We have seen strings already in our code, as docstrings, in calls to print, and as error messages in assert statements.
\n
\n
Strings satisfy the two basic conditions of a sequence that we introduced at the beginning of this section: they have a length and they support element selection.
\n
\n
The elements of a string are themselves strings that have only a single character. A character is any single letter of the alphabet, punctuation mark, or other symbol. Unlike many other programming languages, Python does not have a separate character type; any text is a string, and strings that represent single characters have a length of 1.
\n
\n
Like lists, strings can also be combined via addition and multiplication.
\n

Membership

The membership operator in applies to strings, but has an entirely different behavior than when it is applied to sequences. It matches substrings rather than elements.

>>> 'here' in \"Where's Waldo?\"\nTrue\n

Multiline Literals

Strings aren't limited to a single line. Triple quotes delimit string literals that span multiple lines. We have used this triple quoting extensively already for docstrings.

>>> \"\"\"The Zen of Python\nclaims, Readability counts.\nRead more: import this.\"\"\"\n'The Zen of Python\\nclaims, \"Readability counts.\"\\nRead more: import this.'\n

In the printed result above, the \\n (pronounced \"backslash en\") is a single element that represents a new line. Although it appears as two characters (backslash and \"n\"), it is considered a single character for the purposes of length and element selection.

String Coercion

A string can be created from any object in Python by calling the str constructor function with an object value as its argument. This feature of strings is useful for constructing descriptive strings from objects of various types.

>>> str(2) + ' is an element of ' + str(digits)\n'2 is an element of [1, 8, 2, 8]'\n

Trees

\n
Our ability to use lists as the elements of other lists provides a new means of combination in our programming language. This ability is called a closure property of a data type. In general, a method for combining data values has a closure property if the result of combination can itself be combined using the same method. Closure is the key to power in any means of combination because it permits us to create hierarchical structures — structures made up of parts, which themselves are made up of parts, and so on.
\n

Nesting lists within lists can introduce complexity. The tree is a fundamental data abstraction that imposes regularity on how hierarchical values are structured and manipulated.

A tree has a root label and a sequence of branches. Each branch of a tree is a tree. A tree with no branches is called a leaf. Any tree contained within a tree is called a sub-tree of that tree (such as a branch of a branch). The root of each sub-tree of a tree is called a node in that tree.

The data abstraction for a tree consists of the constructor tree and the selectors label and branches. We begin with a simplified version.

>>> def tree(root_label, branches=[]):\n        for branch in branches:\n            assert is_tree(branch), 'branches must be trees'\n        return [root_label] + list(branches)\n>>> def label(tree):\n        return tree[0]\n>>> def branches(tree):\n        return tree[1:]\n

A tree is well-formed only if it has a root label and all branches are also trees. The is_tree function is applied in the tree constructor to verify that all branches are well-formed.

>>> def is_tree(tree):\n        if type(tree) != list or len(tree) < 1:\n            return False\n        for branch in branches(tree):\n            if not is_tree(branch):\n                return False\n        return True\n

The is_leaf function checks whether or not a tree has branches.

>>> def is_leaf(tree):\n        return not branches(tree)\n

Trees can be constructed by nested expressions. The following tree t has root label 3 and two branches.

>>> t = tree(3, [tree(1), tree(2, [tree(1), tree(1)])])\n>>> t\n[3, [1], [2, [1], [1]]]\n>>> label(t)\n3\n>>> branches(t)\n[[1], [2, [1], [1]]]\n>>> label(branches(t)[1])\n2\n>>> is_leaf(t)\nFalse\n>>> is_leaf(branches(t)[0])\nTrue\n

Tree-recursive functions can be used to construct trees. For example, the nth Fibonacci tree has a root label of the nth Fibonacci number and, for n > 1, two branches that are also Fibonacci trees. A Fibonacci tree illustrates the tree-recursive computation of a Fibonacci number.

>>> def fib_tree(n):\n        if n == 0 or n == 1:\n            return tree(n)\n        else:\n            left, right = fib_tree(n-2), fib_tree(n-1)\n            fib_n = label(left) + label(right)\n            return tree(fib_n, [left, right])\n>>> fib_tree(5)\n[5, [2, [1], [1, [0], [1]]], [3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]]\n

Tree-recursive functions are also used to process trees. For example, the count_leaves function counts the leaves of a tree.

>>> def count_leaves(tree):\n      if is_leaf(tree):\n          return 1\n      else:\n          branch_counts = [count_leaves(b) for b in branches(tree)]\n          return sum(branch_counts)\n>>> count_leaves(fib_tree(5))\n8\n

Partition trees

Trees can also be used to represent the partitions of an integer. A partition tree for n using parts up to size m is a binary (two branch) tree that represents the choices taken during computation. In a non-leaf partition tree:

the left (index 0) branch contains all ways of partitioning n using at least one m,
the right (index 1) branch contains partitions using parts up to m-1, and
the root label is m.

The labels at the leaves of a partition tree express whether the path from the root of the tree to the leaf represents a successful partition of n.

>>> def partition_tree(n, m):\n        \"\"\"Return a partition tree of n using parts of up to m.\"\"\"\n        if n == 0:\n            return tree(True)\n        elif n < 0 or m == 0:\n            return tree(False)\n        else:\n            left = partition_tree(n-m, m)\n            right = partition_tree(n, m-1)\n            return tree(m, [left, right])\n>>> partition_tree(2, 2)\n[2, [True], [1, [1, [True], [False]], [False]]]\n

Printing the partitions from a partition tree is another tree-recursive process that traverses the tree, constructing each partition as a list. Whenever a True leaf is reached, the partition is printed.

>>> def print_parts(tree, partition=[]):\n        if is_leaf(tree):\n            if label(tree):\n                print(' + '.join(partition))\n        else:\n            left, right = branches(tree)\n            m = str(label(tree))\n            print_parts(left, partition + [m])\n            print_parts(right, partition)\n>>> print_parts(partition_tree(6, 4))\n4 + 2\n4 + 1 + 1\n3 + 3\n3 + 2 + 1\n3 + 1 + 1 + 1\n2 + 2 + 2\n2 + 2 + 1 + 1\n2 + 1 + 1 + 1 + 1\n1 + 1 + 1 + 1 + 1 + 1\n

Slicing can be used on the branches of a tree as well. For example, we may want to place a restriction on the number of branches in a tree. A binary tree is either a leaf or a sequence of at most two binary trees. A common tree transformation called binarization computes a binary tree from an original tree by grouping together adjacent branches.

>>> def right_binarize(tree):\n        \"\"\"Construct a right-branching binary tree.\"\"\"\n        if is_leaf(tree):\n            return tree\n        if len(tree) > 2:\n            tree = [tree[0], tree[1:]]\n        return [right_binarize(b) for b in tree]\n>>> right_binarize([1, 2, 3, 4, 5, 6, 7])\n[1, [2, [3, [4, [5, [6, 7]]]]]]\n

Linked Lists

So far, we have used only native types to represent sequences. However, we can also develop sequence representations that are not built into Python. A common representation of a sequence constructed from nested pairs is called a linked list. The environment diagram below illustrates the linked list representation of a four-element sequence containing 1, 2, 3, and 4.

$\"linked_list\"$

A linked list is a pair containing the first element of the sequence (in this case 1) and the rest of the sequence (in this case a representation of 2, 3, 4). The second element is also a linked list. The rest of the inner-most linked list containing only 4 is 'empty', a value that represents an empty linked list.

Linked lists have recursive structure: the rest of a linked list is a linked list or 'empty'. We can define an abstract data representation to validate, construct, and select the components of linked lists.

>>> empty = 'empty'\n>>> def is_link(s):\n        \"\"\"s is a linked list if it is empty or a (first, rest) pair.\"\"\"\n        return s == empty or (len(s) == 2 and is_link(s[1]))\n>>> def link(first, rest):\n        \"\"\"Construct a linked list from its first element and the rest.\"\"\"\n        assert is_link(rest), \"rest must be a linked list.\"\n        return [first, rest]\n>>> def first(s):\n        \"\"\"Return the first element of a linked list s.\"\"\"\n        assert is_link(s), \"first only applies to linked lists.\"\n        assert s != empty, \"empty linked list has no first element.\"\n        return s[0]\n>>> def rest(s):\n        \"\"\"Return the rest of the elements of a linked list s.\"\"\"\n        assert is_link(s), \"rest only applies to linked lists.\"\n        assert s != empty, \"empty linked list has no rest.\"\n        return s[1]\n

Above, link is a constructor and first and rest are selectors for an abstract data representation of linked lists. The behavior condition for a linked list is that, like a pair, its constructor and selectors are inverse functions.

We can use the constructor and selectors to manipulate linked lists.

>>> four = link(1, link(2, link(3, link(4, empty))))\n>>> first(four)\n1\n>>> rest(four)\n[2, [3, [4, 'empty']]]\n

The linked list can store a sequence of values in order, but we have not yet shown that it satisfies the sequence abstraction. Using the abstract data representation we have defined, we can implement the two behaviors that characterize a sequence: length and element selection.

>>> def len_link(s):\n        \"\"\"Return the length of linked list s.\"\"\"\n        length = 0\n        while s != empty:\n            s, length = rest(s), length + 1\n        return length\n>>> def getitem_link(s, i):\n        \"\"\"Return the element at index i of linked list s.\"\"\"\n        while i > 0:\n            s, i = rest(s), i - 1\n        return first(s)\n>>> len_link(four)\n4\n>>> getitem_link(four, 1)\n2\n

Recursive manipulation. Both len_link and getitem_link are iterative. They peel away each layer of nested pair until the end of the list (in len_link) or the desired element (in getitem_link) is reached. We can also implement length and element selection using recursion.

>>> def len_link_recursive(s):\n        \"\"\"Return the length of a linked list s.\"\"\"\n        if s == empty:\n            return 0\n        return 1 + len_link_recursive(rest(s))\n>>> def getitem_link_recursive(s, i):\n        \"\"\"Return the element at index i of linked list s.\"\"\"\n        if i == 0:\n            return first(s)\n        return getitem_link_recursive(rest(s), i - 1)\n

Recursion is also useful for transforming and combining linked lists.

>>> def extend_link(s, t):\n        \"\"\"Return a list with the elements of s followed by those of t.\"\"\"\n        assert is_link(s) and is_link(t)\n        if s == empty:\n            return t\n        else:\n            return link(first(s), extend_link(rest(s), t))\n>>> extend_link(four, four)\n[1, [2, [3, [4, [1, [2, [3, [4, 'empty']]]]]]]]\n>>> def apply_to_all_link(f, s):\n        \"\"\"Apply f to each element of s.\"\"\"\n        assert is_link(s)\n        if s == empty:\n            return s\n        else:\n            return link(f(first(s)), apply_to_all_link(f, rest(s)))\n>>> apply_to_all_link(lambda x: x*x, four)\n[1, [4, [9, [16, 'empty']]]]\n>>> def keep_if_link(f, s):\n        \"\"\"Return a list with elements of s for which f(e) is true.\"\"\"\n        assert is_link(s)\n        if s == empty:\n            return s\n        else:\n            kept = keep_if_link(f, rest(s))\n            if f(first(s)):\n                return link(first(s), kept)\n            else:\n                return kept\n>>> keep_if_link(lambda x: x%2 == 0, four)\n[2, [4, 'empty']]\n>>> def join_link(s, separator):\n        \"\"\"Return a string of all elements in s separated by separator.\"\"\"\n        if s == empty:\n            return \"\"\n        elif rest(s) == empty:\n            return str(first(s))\n        else:\n            return str(first(s)) + separator + join_link(rest(s), separator)\n>>> join_link(four, \", \")\n'1, 2, 3, 4'\n

\n","createdAt":"2023-08-07 09:41:40.864015","updatedAt":"2023-08-07 11:10:16.259041","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":4342,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":8962,"postNumber":26,"raw":"想问一下课程录像怎么看啊，我点进去就要伯克利的账号 :thinking:","cooked":"

想问一下课程录像怎么看啊，我点进去就要伯克利的账号 🤔

\n","createdAt":"2023-08-09 15:23:01.617972","updatedAt":"2023-08-09 15:23:01.617972","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":26,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1077,"username":"Ru1Z2e","name":null,"avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":8963,"postNumber":27,"raw":"Google 一下，有 Youtube Channel 滴：\r\nhttps://www.youtube.com/@cs61adepartmental39/playlists","cooked":"

Google 一下，有 Youtube Channel 滴：

https://www.youtube.com/@cs61adepartmental39/playlists

","createdAt":"2023-08-09 15:44:25.91349","updatedAt":"2023-08-09 15:44:25.91349","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":10,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1047,"username":"anonymous_coward_old","name":"Anonymous Coward Old","avatarUrl":"/uploads/image/43/32/4332638c11248b8ff07033c11de0759a55205facfbec85e14458245a91991faf.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":9113,"postNumber":28,"raw":"我看的是 20fall, 这个学期大部分资源都开源了，videos 也可以随便看","cooked":"

我看的是 20fall, 这个学期大部分资源都开源了，videos 也可以随便看

\n","createdAt":"2023-08-12 16:48:48.45503","updatedAt":"2023-08-12 16:48:48.45503","replyToPostNumber":26,"replyCount":0,"likeCount":0,"wordCount":25,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":9114,"postNumber":29,"raw":"最近：\n第二章过了一半，做完了第二个 project","cooked":"

最近：
\n第二章过了一半，做完了第二个 project

\n","createdAt":"2023-08-12 16:49:31.518998","updatedAt":"2023-08-12 16:49:31.518998","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":18,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":11793,"postNumber":30,"raw":"lz 学完了吗","cooked":"

lz 学完了吗

\n","createdAt":"2023-09-24 17:35:35.804234","updatedAt":"2023-09-24 17:35:35.804234","replyToPostNumber":null,"replyCount":1,"likeCount":0,"wordCount":5,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":1454,"username":"none","name":null,"avatarUrl":null,"admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":11795,"postNumber":31,"raw":"完了，第三章开始后面学的比较快比较赶，也没更新。","cooked":"

完了，第三章开始后面学的比较快比较赶，也没更新。

\n","createdAt":"2023-09-24 17:38:14.19699","updatedAt":"2023-09-24 17:38:14.19699","replyToPostNumber":30,"replyCount":0,"likeCount":2,"wordCount":24,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":2,"users":[{"id":1405,"username":"Caspian","name":null},{"id":7251,"username":"Qq_Qq","name":"Qq Qq"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":31,"username":"TsuinoSora","name":null,"avatarUrl":"/uploads/image/77/06/7706643ba6d3ee1ec9d0070db0ad8a22bed8651fa8eb829cf44df4d20fa24b3b.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":31,"hasUrlPostNumber":true}