返回Nothing不行吗

不能编译啊，你怎么可以println(Nothing)呢

#China #book #school #life 🏫📔 最近从本校的物理老师处得赠了一本 #Algorithm 算法书《算法》 Algorithms in C++ I-IV: Fundamentals, Data Structure, Sorting, and Searching by Robert Sedgewick
https://book.douban.com/subject/1116599/

这本书甚是有价值，不仅仅在它的三观、逻辑、数学、图示、新奇、编程实现上，我就不谈它的价格相比之下实在是不高了，质量上，高德纳(Donald Knuth)的学生，算法，不是盖的。

包括这本书的作者据称都是刚开始写 C++，一个离开计算机都能编程的人，又是计算机科学研究者、算法研究者…… emmm……

我从这本书（我第一次见到用 TeX 排版得这么好看的书，前一次是看 Kanru Hua 的信号处理(signal processing)论文和期刊切片，排版带内联的，虽然我没看懂）的代码块里了解到了原来还有人和我一样不那么遵循所谓的『代码风格』……
他们说，他们努力设计出了一套简洁、可移植的 C++ 编程模板（这里不是 template<> 的意思）。
尽管我不是很喜欢数学的表达方式，我还是得承认我实在找不出一点茬子了 — 比起我从其他书里，尤其是 LLVM Cookbook — 那简直无法入眼的 C++ 代码、类 — 那哪能叫设计啊？分明就是无序杂乱的方法定义！即便能够工作，却怎么也不可能达到 Algorithms 一书示例代码的层次。

虽然我的智商不高所以能实现的东西不多，但我觉得，我的代码依然相对而言较甜，而 Algorithms 一书的代码则是带点数学薄荷的咖啡，醇香微苦，不过 — 都从不油腻、不会拖泥带水让人无从入眼。

这本书里，我学（且暂时只学到）了快速查找、合并查找（不带权重和压缩的）（因为我智商低，而且最重要的是，我有别的事还要完成……）

#include <iostream>
const size_t N = 1000;
int main() { unsigned up[N], b, c; size_t it;
  while (cin >> b >> c) {
    auto a = up[b]; // R(a, b): up[a] = up[b]
    if (up[c] == a) continue; // c R b
    for(it=0; it<N; it++)
      if (up[it] == c) up[it] = a; // R(it, c)
    cout << b << " " << c; } }

其中的 unsigned up[N]; 也可以被泛化为 std::map<unsigned, unsigned>

这是快速查找（也可以作为实现集合数据结构的一种算法），怎么快速法呢？
是解决『传递性问题』的一种算法，它的合并操作速度较慢（所以也叫慢合并），不过判断速度很快。
我们知道，对于一个 M 个输入，它都只需要 O(1) 的时间复杂度来判断是否联通，可在更新时每次都要执行 O(N·M) 次比较 (==) 运算。

这个问题就是给你一堆『对』，如果它是新的，输出它，否则就继续下一个（C++ iostream 扫描器）。
因为快速查找(quick search)/合并(merge search)有 up（父树）所以也称树状数组。

1 2
2 3
4 0
0 1 — 4-0-1-2-3

我们的输入上有一个性质(property)：forall a b c. a R b, b R c => a R c
我们管叫逻辑断言的传递性(transitive)。
1 R 2
2 R 3 => 1 R 3
4 R 0
0 R 1 => 0 R 2, 0 R 1 R 2 R 3 且 3 R 4
（因为 R(a=1, b=2, c=3) 得证 1 R 3 且 R(a=0, b=1, c=4) 得证 0 R 4）
细心的同学可能会觉得奇怪：假如我有 b - a; d - a，他们在树上不是一个树支的，可是却被认为在一起了。
其实这很正常：传递性关系是对称(symmetric) 的，也就是说 forall a b. a R b ≡ b R a
换句话说，这实际上不是一棵树，是一个树状的集合，因为集合关系 (a `是同集` b) 也具有传递性，即 『小鸡是小鸭同集、小鸭是小鹅同集，小鸡也是小鹅同集』。
至于为什么像是树，这是因为集合传递性就是树状的

问题是：这不是一个逻辑问题啊，
上面的实现被称为快速查找，你可以注意到它把离散的 a R b; b R c 传递来了，至于为什么没有 a，是因为我们的实现方式是 unsigned up[N]; 数组，如果我们用的是 strcut { unsigned *up; } 就也还是一样……
我不会算法可视化，所以没有图（不像那个，我艹还是算法可视化专业研究者，计算机图形学基础啊。

至于合并查找（我不知道两颗树的权重算法和路径压缩该怎么做）（题外话，我自己设计了一个类似 Dijkstra 的 DFS 算法当然还没实现，关于狄克斯特拉算法我也自己想了6个细节，只等着写文。）

它就是

size_t i, j;
for (i=0; up[i] != i; i = up[i]);
for (j=0; up[j] != j; j = up[j]);
if (i == j) continue; // common ancestor
else up[i] = up[j]; // merge ancestor

也就是说，找到 a R b R c R … 里的这个 a，它的 parent 绝对是它自己，它就是最大的太爷爷。
（准确的说也没啥 parent 不 parent 的，一切都是临时的，比如我们每次把 c1 的 up 都置为 a，实际上只是需要一个『最大』的集合加入。换句话说，如果 c1 是以后被另一个 up=a 的 d 关联起来的，都一样）
如果他们有同一个太爷爷（也就是说，之前 up[x] = a c1 R a 的那种）
就是 up[a] = up[b] = up[c] 的情况（有关系的，我们都应用了相等关系的传递性，和传递性伴生的对称性）

就像 Rc(refcount GC)、hashmap 一样，树状数组也是只记录部分信息的，就是传递的关系，而不实际保持「继承」关系，所以才能有优化啊（要不然你只能 xs.filter { it.first == this }.exist { it.second == x } 递归下去[因为这一个表达式应该被叫做『存直接链接』]，就不好了）（当然，也可以 dfs 或者 bfs。）


至于那个 O(...) 呢，书上也有在 Fundamentals 一节讲到，定义是：

对于所有 c、N0，若有 g(N) 使得对于所有 N0 < N，g(N) < c·f(N) 成立，则说 g(N) 是 O(f(N))。

就是说数学函数的变化率啦，数学喜欢 \lim_{n\to\infty}{\frac{a}{b}} 趋近于 0 表示 b 渐进地大于 a 什么的……

O(g(n)) = {f(n):存在正常量c和n0，使得对所有n>=n0,有0
唉，没一个讲清楚的，这些数学家真的会自然语言吗？真的知道啥是定语啥是状语吗？
看不懂的话，自己用反对称套一下给自己一个主语，不然算了，毕竟数学不是给常人用的。

书上还有讲状态机、形式化文法等常见计算机科学/算法问题的，不能不说是丰富丰富再丰富。
谈到算法：数组（二分查找、选择排序、冒泡排序、合并排序）、链表、递归（尾递归）、分治算法（快速排序）、哈希表、图（无向、有向无环、广度优先搜索bfs、深度优先搜索dfs、狄克斯特拉算法）、动态编程DP、线性规划、傅里叶变换、二项式、随机化、状态机、形式化文法、二分查找树BST、跳跃链表SkipList、哈希算法、非对称密钥系统……

现在时间比较不充裕，我只能暂时先写这么多。
尽管在学校里我几乎没读这本书，我还是非常感谢赠我这本书的老师，要不然，或许我自己是找不到它的，谢谢你！
更详细的书评/笔记等我以后，会慢慢发出来、写成文集。
但愿我能够理解那些烧脑精妙的算法、但愿我能设计出我所需要所有简单的算法、但愿不论我走到多远、多高，都能够保持不卑不亢，也不会忘记曾经那个真心爱着技术的自己。

#life #dev 吃完饭后先收尾了 Doku，写 AXML 和 Java Class 的读写器。

唉，事情好多
不知道何时做得完

对日常脱稿拖稿的，Doku、Parser.kt（又要修改增加一堆）。
最近新加又有点难度的，Trace、kt4j、GeekSpec、GeekQuery、绝句Java类库（不是绝句后来才该有的程序设计语言）
有点绕的，Linked.List、Reflect helper、RangeMap、Trie、enumMap、基于scanNextOp只要一个参数的 infixChain、NestedList、JPanel Fibonacci sequence。
以后的，绝句解析器（至少依赖现在的 Parser.kt, infix parser）
绝句的实现虽然暂时不要（暂时是只计划翻译置 Java/Kotlin），不担保以后也不要 Doku 库的类文件读写器。

https://ice1000.org/2017/04-23-KotlinForEachBreakContinue.html

令做，[断]
  (0..20).全都，[续]
    若它不小10，回[断]
    说(它)

🤔 我该怎么才能让这个东西，只生成基于 for iterator & break 的代码？
令做、全都 后面跟的都是块，一般都是异常捕获实现，除非我要内联？？？
尽管标准库的东西一般都强制内联，可是内联后就能够知道要跳转到哪里了？

令做，[断]
对0到20里的，
若它不小10，…… “跳转到哪里？？？它怎么知道？”
说(它)

不管内联与否都很容易做到块内返回，但返回到块外面的优化？
是不是应该用启发式往外找一层看是不是能用 break/continue？无法匹配再利用异常传递控制权？

令做，断:do {
  对0到20里的，
    若它不小10，break 断 “跳回[令做]块里”
    说(它) } while (false);

  ……

大概只有建模好执行后才能准确的明白

#PL #PLT 为了方便大家了解一下，我在正式开始编写设计文档前会简单谈一下『绝句』程序设计语言的表达方式。
我不会提及任何设计逻辑、推导的东西，这对绝句来说应该是实现细则，只需要说「必须写明类型」、「能够智能转型」即可。

— 例子: 分二查找.jue —

“之所以叫『分二』，是因为绝句里以『二』开头也是表示数字的方法……”

“在上升序列 [自己] 中二分查找一个 [目标] 项目”
对何<项: 可比<项>>皆有
私下、尾递归的事 分二查找(自己: 行<项>、目标: 项、范围: 数域): 引数? 为
“即便函数没有『我』，绝句也把『我』视为关键字不允许赋值”
若范围.项数是一，回空。
“绝句“数”域默认和 Kotlin 一样是 a..b 全开区间；存项就是 begin <= end，用绝句说是 “始不大末”。”
“二分查找中，一般都是 begin!=end，所以不用 .存项 量（不过也不是不可以）”
量 中 = 范围的中值
判 我[中]，
是目标，回中
大目标，重写(范围=范围.换末(中前))
小目标，重写(范围=范围.换始(中后))

对何<项>皆有
扩物(我: 行<项>) 为
事 分二查找(目标: 项、范围: 数域) = 分二查找.分二查找(我、目标、我的针域)
“本该名辅助函数为二分找，这里是为展示包命名空间”

— 快查集.jue —
引 绝句.环境.读写 (输入、输出、扩文)
引记法 绝句.环境.读写.扩文 「~分」
引记法 绝句.集合.组 「带」
引记法 绝句.额联.括符 「以」
引记法 绝句.额联.括符 「读、写」
常 数 N = 一千 “不一定要加空格，如果不想写类型，用<常参>”
事 入口(变长 参行: 文 “组<文>”) 为
量 亲 = 一组<数>()
对0止N里的号，亲去取位置(号)置为号。
量 b: 数；量 c: 数
“看到的『位置』『置为』『读』都使用了绝句的 存储<T> 物”
重复当输入读b读c不空，
量 a = 亲[b]
若亲[c]是a，略过。
对亲带存储里的d亲、d亲值，若d亲是c，
d亲值置为a “d亲值 = a”
输出以' '分 写b写c

— 基本词法
认为换行是 [\n\r] 里任意一个，但数行数的时候按 (\n?!<=\r|\r\n) 来数（也就是说，支持 Mac 和 Linux 式的 LF/CRLF 换行

文件开头可以是 ^#!.*$, 这一行会被跳过
空格：[ \t\n\r\u{0x3000}] — 全角空格
可选的缩进文法（就是「为……」和「，……」文法）里会预先取缩进长度，在这种文法中空格更加受到重视。
注释：
“” 可嵌套的『引号』注释
--, — 直接行注释，以 [\n\r] 结尾
整数值：
'-'? … 'L'?
默认『数(Int)』，后缀 'L' 以默认『长数(Long)』
下划线不得连续出现
除非就是"0"，数值部分不得以 '0' 开头
当有负号时，数值部分不应为 0, 否则编译器要提示
普通记法：
[_0-9]+
100, 1_000, -1
十六进记法：
'0x' [_0-9A-Fa-f]+
0xFF, 0xFF_FF, -0xFF
汉字记法：
… '[' '节'/'短'/'长'/'浮'/'实' ']'
零, 二, 四十一, 十, 十一, 一百, 一亿
这个是实现起来麻烦点的……
二进制记法：
'0b' [_0-1]+
0b100, 0b10_11, -0b1
浮点数值：
'-'? … 'F'?
frac = '.' digits
默认『实数(Double)』，后缀 'F' 以默认『浮数(Float)』
下划线不得连续出现
普通记法：
digits frac?
0.1, 0.23, 1.00_37
Exponent记法：
digits frac? [Ee] '-'? digits
0.1e3, 0.1E23, 1.0e-23
转义：
'\' [tbnr\]
'\u' hexDigit*4
若在 "" 中支持 " 和 $
字符：
'\b', '.'
支持转义的一个字符
字符串：
char term = (anychar) ~('\'|term) / escape
常量字符串： '"' char('"')* '"'
内联字符串：'"' (char('"') ~'$'|'$' Name | '${'Expr'}')* '"'
长段文法：缩进块 <<长段 Name 为
名字：任何Kotlin里有效的标识符
'『' (anychar)+ '』'
真假：'真'/'假'
空：'空'

这里，准确的说对于绝句而言，词法是不能和语法分开谈论的。（因为它的解析过程不仅仅是上下文相关，而且还能够动态，虽然我在设计上很克制，只允许在导入块添加自定义关键字/二元/后缀运算符）
— 注意的一点是：绝句里没有一元的 +, 你可以认为这是相对 Kotlin 的一个倒退，但我觉得，我讨厌 +0==-0 这种事情、觉得零不应该分什么正负，也讨厌把一些可以默认的东西显式写出来，即便这是正确且在理论上也优雅的。

本来我想弄好 Parser.kt 再说的，可既然现在写了就继续吧……