如题，一种 lisp 列表的增强版，支持 $O(\log n)$ 级别的随机访问和修改，并且无缝可持久化。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 #lang racket/base (define (length-geq? l n) (let loop ([cur l] [len 0]) (cond [(>= len n) #t] [(null? cur) #f] [else (loop (cdr cur) (add1 len))]))) (struct alist (roots) #:transparent) (struct single-tree (root size) #:transparent) (struct tree-node (val l r) #:transparent) (define (alist-cons head l) (let ([rt (alist-roots l)]) (if (length-geq? rt 2) (let ([a (car rt)] [b (cadr rt)] [rest (cddr rt)]) (if (= (single-tree-size a) (single-tree-size b)) (alist (cons (single-tree (tree-node head (single-tree-root a) (single-tree-root b)) (add1 (* 2 (single-tree-size b)))) rest)) (alist (cons (single-tree (tree-node head #f #f) 1) rt)))) (alist (cons (single-tree (tree-node head #f #f) 1) rt))))) (define (alist-car l) (let ([head (car (alist-roots l))]) (tree-node-val (single-tree-root head)))) (define (alist-cdr l) (let ([head (car (alist-roots l))] [rest (cdr (alist-roots l))]) (if (= (single-tree-size head) 1) (alist rest) (let* ([root (single-tree-root head)] [lson (tree-node-l root)] [rson (tree-node-r root)] [size (arithmetic-shift (single-tree-size head) -1)]) (alist (cons (single-tree lson size) (cons (single-tree rson size) rest))))))) (define (get-binary x) (define width (integer-length x)) (define res (make-vector width #f)) (let loop ([i (sub1 width)]) (when (>= i 0) (when (not (zero? (bitwise-and 1 (arithmetic-shift x (- i))))) (vector-set! res i #t)) (loop (sub1 i)))) res) (define (access-in-single-tree p idx) (define width (integer-length idx)) (define bin (get-binary idx)) (let loop ([i (- width 2)] [cur p]) (if (>= i 0) (if (vector-ref bin i) (loop (sub1 i) (tree-node-r cur)) (loop (sub1 i) (tree-node-l cur))) (tree-node-val cur)))) (define (random-access l pos) (set! pos (add1 pos)) ;; 0-base => 1-base (let ([roots (alist-roots l)]) (let loop ([cur roots] [i pos]) (let ([rt (car cur)]) (if (> i (single-tree-size rt)) (loop (cdr cur) (- i (single-tree-size rt))) (access-in-single-tree (single-tree-root rt) i)))))) (define (set-in-single-tree p idx v) (define width (integer-length idx)) (define bin (get-binary idx)) (let loop ([i (- width 2)] [cur p]) (let ([org (tree-node-val cur)] [lson (tree-node-l cur)] [rson (tree-node-r cur)]) (if (< i 0) (tree-node v lson rson) (if (vector-ref bin i) (tree-node org lson (loop (sub1 i) rson)) (tree-node org (loop (sub1 i) lson) rson)))))) (define (random-set l pos v) (set! pos (add1 pos)) (define res (let ([roots (alist-roots l)]) (let loop ([cur roots] [i pos]) (let ([rt (car cur)]) (if (> i (single-tree-size rt)) (cons rt (loop (cdr cur) (- i (single-tree-size rt)))) (cons (single-tree (set-in-single-tree (single-tree-root rt) i v) (single-tree-size rt)) (cdr cur))))))) (alist res)) ;; tests (define a (alist '())) (set! a (alist-cons 3 a)) (set! a (alist-cons 5 a)) (displayln (random-access a 0)) (set! a (alist-cons 7 a)) (set! a (alist-cons 9 a)) (displayln (random-access a 2)) (set! a (random-set a 2 'a)) (displayln (random-access a 2)) (displayln (random-access (alist-cdr a) 1)) 概述 一种基于完美二叉树以及斜二进制分解的结构。lisp 列表的上位替代，支持 $O(1)$ 的 car/cdr/cons，$O(\log n)$ 的随机访问修改。完全可持久化，支持不可变性和结构共享。 ...

前言 · 一点吐槽 为什么诸位都如此热衷于 vscode 啊？ 我随便一翻都能看到 inf 篇介绍 vscode 配置的文章，真是够了。 不如来玩点神秘的：Emacs。 什么是 Emacs？ Emacs 是一款由 GNU 开源软件基金会完全自主研发的开源文本编辑器。在这款编辑器中，你将在一个叫做“buffer”的环境中冒险，与 elisp 邂逅，并探明“Emacs pinky”的真相…… 不开玩笑了。Emacs 是知名的老牌文本编辑器，与 vi/vim 齐名，长期处于编辑器鄙视链的顶端。它的主要优势是无与伦比的可定制性——它是 Lisp Machine 思想的继承者，整个编辑器内核连同各种功能都由一种叫做 elisp 的语言写成，并且自带一个 elisp 解释器。这意味着用户可以像修改游戏 Mod 一样，自由地修改编辑器的任何代码，或者增加自己的函数，把它打造成任何你想要的样子。 它的可定制性是图灵完备的：理论上，你可以用它来做任何事情，包括但不限于浏览网页，管理日程，与朋友吹水，又或者……原神，启动！ 如何获取？ 最简单的方法是访问 GNU Emacs 项目官网或者其 GitHub 仓库然后下载。你也可以用你的包管理器，比如 Windows 的 winget 或 scoop，macOS 的 brew，或者 Linux 的 apt、pacman 等等。在包管理器里搜 emacs 通常就能找到。 装好后先别急着打开，因为这时的 Emacs 没有任何配置，外观简陋，功能匮乏，保证劝退。我们需要给它注入灵魂。 如何配置？（新手的捷径） 好问题。你肯定听说过 Emacs 的配置极其困难，但作为一个刚入门的新手（就像我），想快速上手其实非常简单。 要义在于：不要自己从头配！ 靠自己一行行攒配置所消耗的时间精力是巨大的，很可能在你配出一个好用的编辑器之前，就已经失去兴趣了。 我们可以直接站在巨人的肩膀上，搜寻一些别人做好的 Emacs 发行版。比如经典的 Doom Emacs、Spacemacs、Centaur Emacs 或者 Prelude。 ...

1 2 3 4 5 6 7 8 关于 <我的问题> 这个问题，请不要给出一个平衡各方的中立答案。 请你提出**三种不同且有明确立场的观点**。对于每一种观点，请你评估： - 观点名称：给这个观点起个名字。 - 核心论点：简要阐述其主要逻辑。 - 被接受程度：评估这个观点在当前专家和公众讨论中的普遍程度（高/中/低）。 - 信心指数：你（作为LLM）认为这个观点在未来成为现实的可能性有多大（1-10分）。

光剑后日谈 #2. 在 Scheme/Racket 的世界里，我们常说“一切代码皆为 S-expression”。一个函数调用是 (函数名 参数1 参数2)，一个列表是 (元素1 元素2 元素3)，它们都遵循着括号包裹、前缀表示的统一形式。 但细心的你可能会问，'(a b c) 或者 #'(+ 1 stx) 呢？开头的那个 ' 或 #' 字符，怎么看也不像是列表的一部分。它们是如何融入这套 S-expression 体系的？ 答案很简单：它们是一种语法糖。我们都知道 'exp 等价于 (quote exp)，#'exp 等价于 (syntax exp)。这个单引号 ' 仿佛是一个别名，在 Racket 读取我们的代码时，就悄无声息地将它转换成了标准的形式。这种在“读取阶段”就生效的转换规则，被称为读取器宏（Reader Macro）。 读取器宏背后，是整个 Lisp 家族语言引以为傲的宏系统。宏是一种强大的元编程工具，它本质上是一个在编译期（或称为“展开时”）执行的函数。这个特殊的函数，它的输入是代码（以语法对象的形式），输出也是代码。它允许我们对代码进行任意复杂的、图灵完备的变换，从而彻底扩展语言本身的语法。 那么，亲手编写一个宏，究竟是怎样的体验呢？ 宏之初体验：编写你的第一个宏 when 让我们从一个简单的需求开始。在编程中，我们经常遇到一个场景：“当某个条件成立时，执行一系列操作”。用 Racket 的 if 可以这样写： 1 2 3 4 5 (if (< user-level 5) (begin (display "权限不足！") (log-warning "Attempted access by low-level user.")) #f) 每次都写 (begin ...) 有点繁琐（更何况 Racket 强制 if 有两个分支，那个不需要的分支混淆了语义）。如果我们能创造一个新语法 when，让代码变成下面这样，岂不是更清晰？ ...

一个由不可以总司令想到的有趣概率/期望题。 题面 一套卷子上有 $n$ 道判断题。你不知道它们的答案，但是你知道存在一个常数 $p \in [0, 1]$，对任意一道题，它的答案是“正确”的概率为 $p$。 你决定采用一种策略来答题：选择一个常数 $p' \in [0, 1]$，对于任意一道题，你以 $p'$ 的概率选择“正确”。 求问： 若要使得期望做对题数最多，应该选择怎样的 $p'$？期望做对题数是多少？ 若要使得期望全对概率最大，应当选择怎样的 $p'$？期望全对概率是多大？ 解答 这是一个非常棒的问题！它涉及了期望、概率和优化策略，我们来一步步分解它。 首先，我们来明确一下变量和事件： $n$: 题目的总数。 $p$: 任意一道题的真实答案是“正确”的概率。 $1-p$: 任意一道题的真实答案是“错误”的概率。 $p'$: 你回答任意一道题为“正确”的概率。 $1-p'$: 你回答任意一道题为“错误”的概率。 你的回答策略和你不知道的真实答案是相互独立的。 1) 使得期望做对题数最多 我们要计算做对题数的期望值，并找到使这个期望值最大的 $p'$。 计算单题做对的概率 首先，我们考虑只做对一道题的概率。有两种情况可以做对一道题： 题目的真实答案是“正确”（概率为 $p$），你也回答“正确”（概率为 $p'$）。这件事情发生的概率是 $p \cdot p'$。 题目的真实答案是“错误”（概率为 $1-p$），你也回答“错误”（概率为 $1-p'$）。这件事情发生的概率是 $(1-p) \cdot (1-p')$。 由于这两种情况是互斥的，所以做对任意一道题的概率 $P(\text{单题正确})$ 是两者之和： $P(\text{单题正确}) = p p' + (1-p)(1-p')$ 计算期望做对题数 设 $X$ 为你做对的总题数。$X$ 可以看作是 $n$ 个独立的伯努利试验的和，其中每次试验“成功”（即做对题）的概率为 $P(\text{单题正确})$。 ...

从上一篇文章 https://www.luogu.com.cn/article/a0rd1bxx 的线性代数大学习中，我们知道旋转可以视为乘以一个矩阵。 那么，记 $R_\theta$ 是旋转 $\theta$ 对应的矩阵。 设旋转 $\alpha$ 的变换 $f_\alpha (P) = R_\alpha P$，以及相应的旋转 $\beta$ 角的变换 $f_\beta (P) = R_\beta P$。 显然有旋转 $\alpha + \beta$ 角等于先转 $\alpha$ 再转 $\beta$，也就是说 $f_{\alpha+\beta}(P) = f_\alpha(f_\beta(P))$ 恒成立。那么，代入函数的定义： $R_{\alpha+\beta}P = R_\alpha (R_\beta P)$ 用结合律，就有 $R_{\alpha+\beta}P = (R_\alpha R_\beta) P$ 既然对任意向量两个矩阵的变换结果相同，那么它们肯定是相同的。有 $R_{\alpha+\beta} = R_\alpha R_\beta$ 这样，由于我们知道 $R_{\alpha+\beta}$ 中包含 $\sin (\alpha+\beta)$ 和 $\cos (\alpha+\beta)$ 项，我们就可以用矩阵乘法算出来 $R_{\alpha+\beta}$，然后从中取出相应的项。 计算过程如下： $R_{\alpha+\beta} = R_\alpha R_\beta = \begin{pmatrix} \cos\alpha & -\sin\alpha \\ \sin\alpha & \cos\alpha \end{pmatrix} \begin{pmatrix} \cos\beta & -\sin\beta \\ \sin\beta & \cos\beta \end{pmatrix}$ ...

瓜豆原理 一个图形经过任意旋转、缩放、平移、对称之后，与原图形保持相似，且相似比等于缩放比。 非常强大而泛用的定理。可以用来解决一整类初中的几何题。 这篇文章的目的是证明它，从地基开始重构这整套工具箱。所以默认读者已经会了这些东西，主要进行推式子。 定义 1：线性变换与仿射变换 线性变换 我们常常听说，“某某变换（比如缩放，旋转）是线性变换”。那么什么是“线性变换”？ 我们称一个对 $n$ 维点的变换是线性变换，当且仅当存在一组 $\R^n \to \R$ 的线性变换 $\{g_i\}(1\le i \le n)$ 使得： $$f((x_1, x_2, \cdots x_n)) = (g_1((x_1, x_2, \cdots x_n)), g_2((x_1, x_2, \cdots x_n)), \cdots g_n((x_1, x_2, \cdots x_n)))$$这里的“$\R^n\to \R$ 的线性变换”指满足以下两条性质的变换： 可加性。对于变换 $f$，当且仅当 $\forall x\in \R^n, y\in \R^n\; f(x + y) = f(x)+f(y)$ 时它满足这条性质。 齐性。对于变换 $f$，当且仅当 $\forall x\in \R^n, c\in \R\; f(cx) = cf(x)$ 时它满足这条性质。 容易发现，这样的变换一定是形如 $f((x_1, \cdots x_n)) = \sum_{i = 1}^n a_ix_i$ 的变换，其中 $a_i$ 是常数。 ...

一个自动的 24 点求解器。输入四个数字就会自动输出所有解。 目前还有一点局限性：它会输出许多本质相同的解，比如 a 和 -(-a)。所以下一步可以实现表达式正则化和去重。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 #lang racket (define a (make-vector 4)) (let read-a ([i 0]) (when (< i 4) (vector-set! a i (read)) (when (not (number? (vector-ref a i))) (error "Invalid input!")) (read-a (+ i 1))) (vector-sort! a <)) (struct node (val op1 op2 e1 e2) #:transparent #:mutable) (define (print-ans p) (if (eq? (node-e1 p) (void)) (display (node-val p)) (begin (display #\() ; (display #\() (when (eq? (node-op1 p) '-) (display (node-op1 p))) (print-ans (node-e1 p)) (display (node-op2 p)) ; (display #\() (print-ans (node-e2 p)) ; (display #\)) (display #\))))) (define operators (list (cons '+ +) (cons '- -) (cons '* *) (cons '/ /))) (define (solve l r) (if (= l r) (list (node (vector-ref a l) (void) (void) (void) (void))) (let ([res '()]) (let loop ([i l]) (when (< i r) (let ([p1 (solve l i)] [p2 (solve (+ i 1) r)]) (for* ([op1 operators] [op2 operators] [e1 p1] [e2 p2]) (unless (or (and (= (node-val e2) 0) (eq? (car op2) '/)) (eq? (car op1) '*) (eq? (car op1) '/)) (let ([val ((cdr op2) ((cdr op1) (node-val e1)) (node-val e2))]) (set! res (cons (node val (car op1) (car op2) e1 e2) res)))))) (loop (+ i 1)))) res))) (define ans (void)) ; Helper function to reverse a subarray of vector `v` from `start` to `end` inclusive. (define (reverse-subarray v start end) (let loop ([i start] [j end]) (when (< i j) ; Swap elements at index i and j (let ([temp (vector-ref v i)]) (vector-set! v i (vector-ref v j)) (vector-set! v j temp)) (loop (+ i 1) (- j 1))))) ; Implements the C++ std::next_permutation algorithm. ; Mutates global vector 'a' in place to the next lexicographical permutation. ; Returns #t if a next permutation was found, #f if it wrapped around to the first permutation. (define (next-permutation a) (let ([n (vector-length a)]) ; Step 1: Find pivot point 'i' (find first element a[i] < a[i+1] from right) (let loop-find-pivot ([i (- n 2)]) (cond ; Case 1: No pivot found (vector is in reverse order) [(< i 0) ; Reverse the whole vector to get the first permutation. (reverse-subarray a 0 (- n 1)) ; (displayln "!!!!!!!\n") #f] ; Return #f to indicate we wrapped around. ; Case 2: Found pivot point 'i' [(< (vector-ref a i) (vector-ref a (+ i 1))) ; (displayln i) ; Step 2: Find swap element 'j' (find first element a[j] > a[i] from right) (let loop-find-swap ([j (- n 1)]) (if (> (vector-ref a j) (vector-ref a i)) ; Step 3: Swap elements at i and j (let ([temp (vector-ref a i)]) (vector-set! a i (vector-ref a j)) (vector-set! a j temp)) (loop-find-swap (- j 1)))) ; Step 4: Reverse suffix starting from i + 1 (reverse-subarray a (+ i 1) (- n 1)) #t] ; Return #t to indicate a next permutation was found. ; Case 3: Continue searching for pivot point 'i' to the left [else (loop-find-pivot (- i 1))])))) (define (print-a) (let loop ([i 0]) (when (< i 4) (display (vector-ref a i)) (display #\space) (loop (+ i 1)))) (newline)) (let loop ([i 0]) (when (< i 24) ; (print-a) (set! ans (solve 0 3)) (for ([p ans]) (when (= (node-val p) 24) (print-ans p) (newline) #; (exit))) (when (next-permutation a) (loop (+ i 1)))))

光剑的后日谈 #1. 在文艺复兴之后，FP 也要大胜利！ 在这篇文章的讨论区中，我进行了引流。为了报答作者，我写了这篇文章。 上面那篇文章中使用了一种伪代码语法来表示 lambda calculus。不过这种语法并不能直接运行。怎么办呢？让我们来构建一个源到源编译器！ 要写一种语言的编译器，显然我们需要知道它的语法和词法。这是第一步。另外还有语义，但是它是 lambda 的一种表示法，所以语义已经被 lambda 定义了，无需考虑。 首先是词法。这种语言会出现哪些 tokens？ 分类一下。lambda 的核心是函数抽象和函数应用。函数抽象用到哪些 tokens？ func 关键字。 冒号。 return 关键字。 参数列表和括号。 函数应用？ 括号 另外还有一个扩展语法，绑定创建。 等号（赋值运算符） 然后我们需要定义它的语法。这篇文章使用的是单参数的原始 lambda，方便了我们的实现。 1 2 3 4 5 6 identifier ::= symbol abstract-exp ::= func : (identifier) { return val-exp } apply-exp ::= val-exp(val-exp) bind-exp ::= identifier = val-exp val-exp ::= identifier | abstract-exp | apply-exp lc-exp ::= val-exp | bind-exp 看来挺简单的。 ...

光剑系列的第六作！ （放一个 Gemini 生成的欧比旺的图来解释一下光剑是什么） 前五作： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 第三篇：协程、生成器与 call/cc 的控制流 第四篇：动态作用域、词法作用域与表达式求值的环境模型 第五篇：基于环境模型的解释器 我们上篇文章写了解释器。在评论区里面可以看到一个非常神秘的东西：https://www.zhihu.com/question/30262900/answer/1943149381147660845 1 2 3 4 5 6 7 8 9 10 11 12 ; 嵌套的括号不是 scheme 标准语法。表示定义柯里化的函数，和嵌套 lambda 等价。racket 支持这一扩展语法。 (define (Z env) (car env)) (define ((S vp) env) (vp (cdr env))) (define ((Lam e) env) (lambda (x) (e (cons x env)))) (define ((App e1 e2) env) ((e1 env) (e2 env))) ; (define global-env '()) 顺便，还有人问我为什么不再布置一道习题，那么这就是习题！ ...