守株阁

“分数发生变化后，立即显示新的名次”还不是一个足以实现和分析的需求。相同分数是否并列，删除之后名次是否连续，查询不存在的记录应返回什么，都能改变程序的合法输出。先固定这些选择，才能讨论哈希表、数组和有序树各自承担的工作。 本系列从一个本地动态榜单开始。它没有网络请求、权限和并发更新，全部操作顺序执行。首篇只建立操作契约与朴素参照；后续结构必须回答相同的问题，才能比较成本。MIT 的算法导论讲义把问题表述为输入与允许输出之间的关系，这也是这里区分“需求”和“某一种程序”的依据。MIT 6.006 Lecture 1 同分记录怎样排序 每条记录包含整数标识 id 和整数分数 score。标识从 0 开始，由插入操作单调分配，删除后不复用。分数可为负数，同分合法。排序键统一写为 (-score, id)，按字典序升序比较，因此高分靠前，同分时较早分配的 ID 靠前。 ID 分数 排序键 名次 0 80 (-80, 0) 2 1 95 (-95, 1) 1 2 80 (-80, 2) 3 把 ID 2 更新为 100，顺序就成为 2, 1, 0。再把 ID ...

两件商品单价 12.50 元，另一件单价 3.20 元，九折后的应付金额是 25.38 元。计算这个数只需要一个循环。程序扩大后，报价还会受日期、规则版本、外部查询和订单状态影响；字段可能非法，文件可能读取失败，任务可能取消。函数式编程的学习路线从这些具体差异出发：计算怎样保持可预测，输入和状态怎样进入类型，计算之间怎样组合，实际执行由谁管理。 认识纯函数、一等函数、部分应用、柯里化和 memoize，已经掌握了函数式编程的重要基础。这些知识主要解释函数怎样作为值使用，以及调用怎样组织。后续还需要不可变数据与别名、求值策略、代数数据类型、错误模型、组合定律和效果生命周期。Monad 位于组合这一段，不能用“还差 Monad 一个术语”衡量整条路线的完成度。 系列共有 40 篇主线和 8 篇选修。主线前半用 Java 21 建立可运行的例子，第 14 篇补足后续需要的 Scala 3 语法，再研究类型构造器与效果组合。选修讨论 λ 演算、参数性、Optics、程序解释和语言生态，按需求进入，不是理解 Optional 的前置门槛。 先定义能观察的行为 教学案例只处理本地合成订单，不...

取消一个正在等待的任务，释放资源的记录出现了吗？在时间二十恰好发生两次更新，采样会得到哪一个值？前一个问题属于效果运行时的生命周期，后一个属于时变值的语义。两者都可能出现在响应式应用里，却不能用同一个“流”字略过差别。 本篇分成两个独立实验：ZIO 2.1.16 检查业务失败、缺陷、中断与释放；JavaScript 用有限整数时间模型检查保持、组合与采样。它们没有强行连成一个新框架。已有ZIO 的错误与任务生命周期保留配置环境和服务组织背景，FS2 的需求与资源作用域保留流需求背景；新系列入口见导读与能力自测。 错误类型不覆盖全部退出原因 ZIO[R,E,A] 描述需要 R、可能以 E 失败、成功时得到 A 的计算。E 用于可预期的失败通道，而运行时还可能记录 defect 与 interruption。把 E 写成 Nothing，只说明没有可构造的类型化失败值，不表示计算永远不会出缺陷、被中断或者不终止。 实验用 ZIO.fail("quantity") 表示可预期业务错误，用 ZIO.die(new IllegalStateException("...

把同一个动作使用两次，究竟会执行两次，还是取得同一次执行的结果？Haskell 的 IO、JavaScript 的闭包与 Promise 给出的答案不同。仅把 >>= 与 .then 放在一起比较语法，会漏掉启动时机、共享和 thenable 吸收这些实际可观察的差别。 实验用一个计数器和一组确定的事件顺序比较两门语言，不访问网络、不靠延时猜测完成。本篇补充Cats 与 IO 的执行和取消中“描述不等于执行”的讨论；本系列入口见导读与能力自测。工具链隔离在临时目录，源码只依赖 GHC 的基础库与 Node 内置断言。 do是组合语法，IO是动作类型 Haskell 的 do 不专属于 IO。实验先写一个 Maybe 计算，再显式展开绑定： 123456viaDo = do x <- Just 2 y <- Just 3 pure (x + y)viaBind = Just 2 >>= (\x -> Just 3 >>= (\y -> pure (x + y))) 两者都得到 Just 5。这里没有打开文件，也没有启...

已经有一个检查整数是否为正数的 Predicate，现在要检查字符串长度；已经有整数编码器，现在要编码一组字符串拼接后的长度。这两件事都需要在已有消费者之前适配输入。另一个不同问题是对序列每个位置计算邻域之和，它需要保留当前位置之外的上下文。把这些需求分开，Contravariant、Profunctor 与 Comonad 的方向才不会混成名词表。 本篇所有结构都用几十行 Scala 手写，并用定律和一个错误邻域实现作对照。前置类型类背景保留在Scala 的高阶类型与组合定律，完整学习路径见导读与能力自测。 消费者从新的输入到旧的输入 Predicate[A] 持有 A=>Boolean。若已有 Predicate[Int]，另有 String=>Int 的长度函数，那么新 Predicate[String] 应先求长度，再交给原检查器。它没有产生一个可以 map 的 A，而是在消费 A。 1234567case class Predicate[A](run: A => Boolean): def contramap[B](f: B => A): Pr...

读取数量、计算价格、输出结果，可以写成三层回调。把回调包成 flatMap 后，缩进少了，控制流却没有消失：谁调用下一步、下一步返回后还会发生什么、异常经过哪一层，仍然决定程序行为。尤其是资源关闭和异步异常，不能靠一个名字叫 Continuation 的容器自动保证。 本篇从同步计算开始，手写最小 CPS 组合，打印进入与退出顺序，再用泄漏、提前关闭和重复回调作为反例。它补充Cats 与 IO 的执行和取消中的运行时边界，不替代成熟效果系统的资源管理。系列入口见导读与能力自测。 返回结果与传递剩余计算 普通函数 price(qty) 返回价格。CPS 版本额外接收 k，把价格交给 k，并返回 k 的结果：priceCps(qty,k)=k(qty*10)。k 表示当前步骤完成后剩余的计算。它不是必然异步的回调，也不意味着独立线程；本例所有调用都在同一个同步调用栈上发生。 固定最终结果类型 R，可以把产生 A 的计算写成 Cont[R,A]=(A=>R)=>R。A 是当前阶段交出的值，R 是整个后续计算的最终结果。给它传一个 A=>R，才能完成执行。若 R 选成字...

一个程序先读取计数器，再加上“旧值加一”，最后重新读取。初始值为二时，结果应该是五。测试希望把计数器放在纯状态里，运行时希望把它放在原子引用里，同时又不想写两套业务流程。这是程序描述和程序解释分离的一个足够小的例子。 Free 把指令与依赖关系组成一个可解释的值；Tagless Final 把程序写成针对能力接口的多态函数。两者都能支持多个解释器，也都可能被错误使用。本篇用同一套指令和同一条流程做四格实验，再检查十万步组合与一个实际栈溢出反例。背景可衔接Scala 的高阶类型与组合定律和Cats 与 IO 的执行和取消，系列入口见导读与能力自测。 先把程序允许做的事限制下来 程序只能 Read 或 Add，不允许任意删除文件、发网络请求，也不允许取得整个可变引用。指令用带结果类型的枚举描述： 1234567enum Op[A]: case Read extends Op[Int] case Add(n: Int) extends Op[Unit]trait Counter[F[_]]: def read: F[Int] def add(n: Int): F[Unit] R...

订单里的城市名称要改，订单编号、邮编和支付状态却不能一起变化。直接写两层 copy 很容易理解；同一条更新路径出现在多个地方之后，才值得把“从订单到地址，再到城市”的定位规则提取出来。Lens 的价值在于组合这个定位规则，而它是否可靠，要由读取和写回的定律决定。 对于“付款方式可能是银行卡，也可能是现金”这种数据，城市式的必有字段模型又不够用了。Prism 表达只匹配某个分支的访问与构造。两种结构可以共存，但不能把读取失败都藏成一个默认字符串。本篇先保留直接复制作为参照，再写最小实现和反例。前置背景可读Scala 的高阶类型与组合定律，系列导航见导读与能力自测。 直接复制先定义正确结果 实验模型只有三种字段： 123456case class Address(city: String, zip: String)case class Order(id: Int, address: Address, paid: Boolean)val changed = order.copy( address = order.address.copy(city = nextCity)) 这段代码保...

一个函数只有签名 List[A] => List[A]，能不能据此断定它只会调整元素顺序？不能。它可以丢弃、复制元素，甚至总是返回空表。但如果它对所有类型统一工作、不观察元素内部结构，而且是纯且全的，那么它受到比普通业务函数强得多的限制。这些限制可以转化成测试性质，也可以帮助判断哪些优化允许移动到调用边界之外。 本篇用一个可手算的自然性等式展开参数性，再用 Scala 中的 null、运行时类型检查和效果记录拆开其假设。Scala 的高阶类型与组合定律保留类型类背景，简单类型 λ 演算保留类型判断背景。两篇都不替代这里对工程语言例外的检查。完整系列从导读与能力自测进入。 从“缺少操作”推导约束 考虑 def choose[A](a: A): A。如果没有其他 A 值，没有运行时类型分析，没有不安全转换，没有空值、异常与无限循环，并要求全函数，那么实现只能返回这个输入。它不知道 A 是数字、地址还是支付方式，不能凭空调用加法或创建一个业务值。 删除任一前提都可能扩大实现集合。throw 可以在不给出 A 的情况下满足 Scala 的返回类型；无限递归也一样。未启用 expli...

把 (λx. λy. x) y 化成 λy. y，看起来只做了一次文本替换，却已经改变了程序含义。传入的 y 原本由外部环境提供，替换后却变成了函数自己的参数。规约器必须区分名字相同与绑定关系相同，否则后面的函数组合、求值顺序乃至编译优化都没有可靠基础。 本篇承接λ 演算入门与写一个 λ 规约器。实验复用旧规约器的三类 AST、自由变量计算、绑定变量改名和避免捕获替换，增加 α 等价判定、两种完整规约策略、燃料计数和效果下的 η 反例。旧文保留原位置，新实验不覆盖旧实现。系列入口是导读与能力自测。 替换操作处理的是绑定关系 无类型 λ 项只有变量、函数抽象与应用三种形状：x、λx.M、M N。应用向左结合，f a b 表示 (f a) b；抽象的函数体尽量向右延伸。括号影响语法树，名字是否自由则由到根节点路径上的绑定决定。 自由变量集合满足 FV(x)={x}、FV(M N)=FV(M)∪FV(N)、FV(λx.M)=FV(M)-{x}。在 λx. x y 中，只有 y 自由。嵌套成 λy. λx. x y 后，整个项闭合，但不能据此认为任意子项都没有自由变量：单独取出内层函数，...