sauravbhattacharya001/Ocaml-sample-code

## 关于 本仓库包含独立的 OCaml 程序，每个程序都专注于特定的语言特性或算法。每个文件都可以独立编译和运行——非常适合通过阅读和修改真实代码来学习 OCaml。 **176 个程序**涵盖：递归、模式匹配、代数数据类型、GADT、Option 类型、高阶函数、多态、尾递归、累加器、元组解构、输入验证、哈希表、记忆化、闭包、管道操作符、命令式特性、模块 (Map, Set, Queue)、记录、图算法、持久化数据结构、优先队列、解析器组合子、单子组合、运算符优先级解析、字典树、前缀搜索、字符串操作、Thompson NFA 构造、epsilon 闭包、正则表达式解析、基于集合的模拟、惰性求值、无限序列、自平衡 BST、排序算法、不相交集、并查集、函数式哈希映射、分离链接、自动调整大小、概率数据结构、布隆过滤器、双重哈希、跳表、随机化算法、绳索、平衡二叉树、文本编辑数据结构、线性代数、矩阵运算、函子、模块签名、高斯消元法、符号微分、代数化简、链式法则、偏导数、符号积分、u-代换、数值方法、概率单子、蒙特卡洛模拟、贝叶斯推断、逻辑编程、统一化、代数效应、Free 单子、自动微分、反向传播、函数式响应式编程、网络流算法、字节码虚拟机、项重写系统、拉链、基于属性的测试、手指树、持久化向量、抽象解释、有限自动机、约束满足、Datalog 引擎、双端队列、Diff 算法、Earley 解析、GADT、游戏 AI、垃圾回收模拟、计算几何、属性图数据库、哈夫曼编码、HyperLogLog 基数估计、区间树、Lambda 演算、模型检测、光学 (透镜/棱镜)、PEG 解析器、关系代数、SAT 求解器、字符串匹配、后缀数组、定理证明、类型推断、Comonad、随机访问列表、哈希数组映射字典树、单子转换器、光线追踪、定界续延、Lindenmayer 系统、海龟绘图、神经网络、信号处理 (FFT、卷积、频谱分析)、行为树、自主智能体任务规划。 ## 程序 | 文件 | 描述 | 概念 | |------|-------------|----------| | [`abstract_interp.ml`](abstract_interp.ml) | 用于区间域分析的抽象解释器 | 格理论、变宽/变窄、抽象转移函数、不动点计算 | | [`actor.ml`](actor.ml) | Actor 模型 — Erlang 风格的消息传递并发 | 邮箱、选择性接收、监督树、进程隔离、消息路由、容错 | | [`autodiff.ml`](autodiff.ml) | 自动微分 — 前向和反向模式 | 对偶数、计算图、基于 Tape 的反向传播、梯度/雅可比/海森矩阵、Adam/动量优化器、神经网络构建块 | | [`automata.ml`](automata.ml) | 有限自动机工具包 — DFA/NFA 构造与最小化 | 子集构造法、Hopcroft 最小化算法、积构造、NFA→DFA 转换 | | [`bdd.ml`](bdd.ml) | 二叉决策图 — ROBDD 构造、Apply 算法、SAT/TAUT 检查 | 哈希共享、Shannon 展开、余因子、量化、ITE、DOT 导出、交互式 REPL | | [`behavior_tree.ml`](behavior_tree.ml) | 行为树引擎 — 面向自主智能体的分层任务规划 | 序列/选择/并行节点、装饰器 (反转器、重复器、冷却)、黑板记忆、Tick 执行、轨迹可视化、3 个领域 (机器人巡逻、NPC、恒温器)、交互式 REPL | | [`bloom_filter.ml`](bloom_filter.ml) | 布隆过滤器 — 概率集成员检测 | 双重哈希、可调的误判率、并集、最优大小、饱和度统计 | | [`bst.ml`](bst.ml) | 二叉搜索树 (插入、删除、遍历、最小/最大值、大小、深度) | 代数数据类型、多态、累加器 | | [`btree.ml`](btree.ml) | B 树 — 具有可配置度的自平衡搜索树 | 多路分支、节点分裂、中序遍历、搜索、批量插入 | | [`bytecode_vm.ml`](bytecode_vm.ml) | 带有编译器和反汇编器的基于栈的字节码虚拟机 | 操作码、栈机器、调用帧、闭包、Upvalue、表达式编译、原生函数、执行追踪 | | [`calculus.ml`](calculus.ml) | 符号微分 — 导数、化简、求值 | 代数数据类型、模式匹配、递归转换、链式法则、梯度 | | [`cartesian_tree.ml`](cartesian_tree.ml) | 笛卡尔树 — 具有堆 + BST 属性的二叉树 | O(n) 基于栈的构造、范围最小查询 (朴素 & O(1) 稀疏表)、欧拉环游、验证、美观打印 | | [`crypto.ml`](crypto.ml) | 经典密码 — ROT13、凯撒密码、维吉尼亚密码、XOR、栅栏密码、Atbash | 字符串操作、模运算、频率分析、对称加密 | | [`comonad.ml`](comonad.ml) | Comonad — 用于上下文相关计算的单子的对偶 | Identity/Env/Traced/Store/Stream comonad、Zipper1D/Zipper2D、元胞自动机 (Wolfram 规则)、生命游戏、电子表格求值、移动平均、comonad 定律 | | [`code_archaeology.ml`](code_archaeology.ml) | 自主代码考古引擎 — 发现文件之间的隐藏关系 | DNA 签名提取、Jaccard 相似度、概念聚类 (并查集)、进化链、缺失链接检测、标记频率分析、交互式 REPL | | [`code_lineage.ml`](code_lineage.ml) | 自主代码谱系追踪器 — 实现谱系引擎 | 60+ 特征标记、Jaccard 距离的进化距离、UPGMA 系统发育树构建、趋同进化检测、谱系链发现、物种形成事件检测、灭绝风险分析、健康评分 0-100、交互式 HTML 仪表盘 (48 项测试) | | [`code_experiment.ml`](code_experiment.ml) | 自主代码实验引擎 — 假设驱动的算法实验 | 排序/搜索/哈希实验、统计基准测试、缩放分析 (O(1) 到 O(n²) 检测)、异常检测、Robin Hood 哈希、三数取中快速排序、插值搜索、可复现的 RNG、具有可配置实验/大小/试验次数的 CLI | | [`code_profiler.ml`](code_profiler.ml) | 自主代码复杂度分析器 — 分析 OCaml 源文件 | 启发式复杂度评分、圈复杂度、嵌套深度、模式密度、重构建议、聚类检测、ASCII 直方图 | | [`constraint.ml`](constraint.ml) | 约束满足问题求解器 — 数独、N 皇后、图着色 | 回溯、弧一致性 (AC-3)、约束传播、MRV/LCV 启发式、前向检查 | | [`crdt.ml`](crdt.ml) | CRDT — 实现最终一致性的无冲突复制数据类型 | G-Counter、PN-Counter、G-Set、OR-Set、LWW-Register、MV-Register、向量时钟、合并半格 | | [`csp.ml`](csp.ml) | 约束满足问题求解器 — 数独、N 皇后、图着色 | 回溯、弧一致性 (AC-3)、约束传播、MRV/LCV 启发式、前向检查 | | [`csv.ml`](csv.ml) | CSV 解析器与数据分析器 — 带有类型推断的 RFC 4180 解析 | 字符串解析、类型推断、基于 fold 的聚合、group-by、过滤、排序、美观打印 | | [`datalog.ml`](datalog.ml) | Datalog 查询引擎 — 带有分层否定的自底向上求值 | 半朴素求值、统一化、不动点计算、分层否定、聚合 | | [`delimited_cont.ml`](delimited_cont.ml) | 定界续延 — 用于可组合控制流的 shift/reset | CPS 转换、shift/reset、amb 操作符、协程、协作式线程、作为续延的异常处理 | | [`deque.ml`](deque.ml) | 纯函数式双端队列 (Okasaki 的 Banker's Deque) | 两端均摊 O(1)、持久化数据结构、滑动窗口算法 | | [`diff.ml`](diff.ml) | Myers diff 算法 — git diff 所使用的同一算法 | 编辑图、最短编辑脚本、LCS 提取、统一 diff 格式化 | | [`dijkstra.ml`](dijkstra.ml) | 加权图 — Dijkstra、Floyd-Warshall、Prim MST | 加权邻接表、优先队列、最短路径、最小生成树 | | [`earley.ml`](earley.ml) | 用于上下文无关文法的 Earley 解析器 | Earley 项、预测/扫描/完成操作、解析森林、歧义处理 | | [`euler_tour_tree.ml`](euler_tour_tree.ml) | 欧拉环游树 — 基于欧拉环游序列的动态森林连通性 | 由 Treap 支持的隐式序列、link/cut、连通性查询、子树聚合、重新定根 | | [`effects.ml`](effects.ml) | 代数效应与处理程序 | Free 单子、定界续延、CPS 转换、通过余积的效应组合、State/Exception/Nondeterminism/Writer/Reader/Coroutine 效应、N 皇后 | | [`factor.ml`](factor.ml) | 通过优化的试除法进行质因数分解 | 递归、相互递归、输入验证 | | [`fenwick_tree.ml`](fenwick_tree.ml) | 树状数组 (Binary Indexed Tree) — 前缀和与点更新 | 命令式数组、位操作、函子、O(log n) 查询、顺序统计 | | [`fibonacci.ml`](fibonacci.ml) | 斐波那契：朴素 vs 记忆化 vs 迭代 | 哈希表、闭包、命令式特性、基准测试 | | [`finger_tree.ml`](finger_tree.ml) | 手指树 — 通用的函数式数据结构 (Hinze & Paterson, 2006) | 单子参数化测量、2-3 节点、O(1) 摊还双端队列操作、O(log n) 连接/拆分、序列、优先队列、有序序列 | | [`frp.ml`](frp.ml) | 函数式响应式编程 — 信号、行为、事件、流 | 随时间变化的行为、事件组合子、基于推送的信号、响应式单元格、状态机、动画缓动、关键帧、弹簧物理 | | [`free_monad.ml`](free_monad.ml) | Free 单子 — 将程序描述与解释分离 | Free/Freer 单子、自然变换、效应解释、余积效应、可组合 DSL | | [`fsm.ml`](fsm.ml) | 有限状态机 — DFA/NFA 构造与字符串接受 | 变体类型、模式匹配、集合/映射、不动点、形式语言理论 | | [`gadts.ml`](gadts.ml) | 广代数数据类型 (GADT) | 类型安全的表达式求值器、长度索引向量、类型化异构列表、类型级编程 | | [`game_ai.ml`](game_ai.ml) | 带有 Alpha-Beta 剪枝的极小极大游戏 AI — 井字棋和四子棋 | 模块签名、函子、迭代加深、转置表、极小极大 | | [`gc_simulator.ml`](gc_simulator.ml) | 垃圾回收器模拟器 — 4 种经典 GC 算法 | 标记-清除、Cheney 复制法、引用计数 (循环检测)、分代 GC | | [`genetic.ml`](genetic.ml) | 遗传算法框架 — 进化优化 | 锦标赛/轮盘赌选择、单点/两点交叉、变异、精英主义、TSP/背包/函数优化 | | [`geometry.ml`](geometry.ml) | 计算几何 — 凸包、最近点对、相交 | 叉/点积、Graham 扫描、射线投射、分治法、多边形操作 | | [`gossip.ml`](gossip.ml) | Gossip 协议模拟器 — 流行病式信息传播 | 推/拉/推-拉策略、收敛追踪、网络分区、反熵、自主协议顾问、多种拓扑、交互式 REPL | | [`graph.ml`](graph.ml) | 图算法 (BFS、DFS、拓扑排序、环检测) | 模块 (Map, Set, Queue)、记录、命令式队列、变体 | | [`graph_db.ml`](graph_db.ml) | 带有受 Cypher 启发的模式匹配的属性图查询引擎 | 属性图、标记节点、类型化关系、回溯搜索、投影 | | [`hamt.ml`](hamt.ml) | 哈希数组映射字典树 — 持久化哈希映射 (Bagwell 2001) | 32 路位图压缩分支、结构共享、O(log32 n) 操作、冲突处理、集合操作、暂存构建器、统计 | | [`hashmap.ml`](hashmap.ml) | 函数式哈希映射 — 持久化不可变哈希表 | 分离链接、自动扩容、fold/map/filter、merge/union、分区 | | [`heap.ml`](heap.ml) | 优先队列 — 左式最小堆 (插入、合并、排序、前k个) | 持久化数据结构、秩注解、自定义比较器 | | [`hello.ml`](hello.ml) | 变量、类型、管道和模式匹配 | Let 绑定、类型推断、`Printf`、管道操作符 | | [`huffman.ml`](huffman.ml) | 哈夫曼编码 — 无损数据压缩 | 优先队列、递归树遍历、频率分析、可变长度前缀码 | | [`hyperloglog.ml`](hyperloglog.ml) | HyperLogLog — 概率基数估计器 | 基于寄存器的草图、调和平均估计、偏差校正、merge/union、通过包含-排除原理的交集、Jaccard 相似度、序列化 | | [`integration.ml`](integration.ml) | 符号积分引擎 — 不定积分、定积分、数值方法 | 基于模式的规则、线性、u-代换、分部积分 (LIATE)、辛普森法则、通过微分进行验证 | | [`interval_tree.ml`](interval_tree.ml) | 区间树 — 增强的 AVL 树用于高效的重叠查询 | AVL 平衡、子树增强、O(log n) 重叠/穿刺查询 | | [`order_statistics_tree.ml`](order_statistics_tree.ml) | 顺序统计树 — 增强的加权平衡 BST | O(log n) rank、select、count_range、range_query、中位数、百分位数、自动再平衡 | | [`json.ml`](json.ml) | JSON 解析器 — 带有查询和转换的完整 RFC 8259 解析器 | 递归下降、相互递归、Unicode 转义、美观打印、点表示法查询 | | [`lambda.ml`](lambda.ml) | 无类型 Lambda 演算解释器 | Alpha 等价、避免变量捕获的替换、De Bruijn 索引、Beta 归约策略 | | [`learning_path.ml`](learning_path.ml) | 学习路径顾问 — 自主知识评估与个性化学习路径 | 概念依赖图、拓扑排序、自适应测验、技能推断、差距分析、掌握度追踪、交互式 REPL | | [`list_last_elem.ml`](list_last_elem.ml) | 安全地查找列表的最后一个元素 | Option 类型、模式匹配 | | [`lru_cache.ml`](lru_cache.ml) | LRU 缓存 — 有界的最近最少使用缓存 | 带有自动驱逐的 Put/get、命中/未命中统计、peek、调整大小、过滤、fold | | [`lsystem.ml`](lsystem.ml) | L-System — Lindenmayer 系统与海龟绘图 | D0L/随机/参数化 L-System、海龟解释、SVG 输出、科赫雪花、谢尔宾斯基三角、龙曲线、希尔伯特曲线、植物/蕨类、彭罗斯平铺 | | [`matrix.ml`](matrix.ml) | 矩阵 — 带有函子和模块的线性代数 | 函子、模块签名、高斯消元法、行列式、逆矩阵、矩阵幂、范数 | | [`mergesort.ml`](mergesort.ml) | 带有自定义比较器的归并排序 | 高阶函数、尾递归、元组解构 | | [`merkle_tree.ml`](merkle_tree.ml) | Merkle 树 — 用于数据完整性的密码学哈希树 | 二叉哈希树、包含证明、O(log n) 验证、篡改检测、树差异比对 | | [`minikanren.ml`](minikanren.ml) | miniKanren 逻辑编程引擎 | 统一化、替换、逻辑变量、流、关系编程、Peano 算术、约束求解 | | [`monad_transformers.ml`](monad_transformers.ml) | 单子转换器 — 可组合的单子栈 | OptionT、ExceptT、ReaderT、WriterT、StateT、ContT、ListT、RWST、lift、转换器堆叠、单子定律、callcc | | [`model_checker.ml`](model_checker.ml) | 用于有限状态迁移系统的 CTL 模型检测器 | 时序逻辑 (CTL)、标记算法、不动点计算、状态探索 | | [`network_flow.ml`](network_flow.ml) | 网络流算法 — Edmonds-Karp 最大流、最小割、二分图匹配、MCMF | 残留图、BFS 增广路径、流量分解、Bellman-Ford SPFA、二分图规约、多源/汇 | | [`neural_network.ml`](neural_network.ml) | 带有反向传播的前馈神经网络 — 从零开始的 MLP | 可配置层、sigmoid/tanh/relu/leaky_relu/softmax、Xavier/He 初始化、MSE/交叉熵损失、动量、梯度裁剪、学习率调度、批量/随机训练 | | [`optics.ml`](optics.ml) | 光学 — 透镜、棱镜和遍历，用于可组合的数据访问 | 透镜 (get/set)、棱镜 (preview/build)、遍历 (fold/over)、组合 | | [`parser.ml`](parser.ml) | 解析器组合子 — 从小块构建解析器 (算术、列表、键值对) | 高阶函数、闭包、单子 bind/map、递归下降、运算符优先级 | | [`peg.ml`](peg.ml) | 带有 Packrat 记忆化的解析表达文法引擎 | PEG (Ford, 2004)、Packrat 解析、线性时间保证、有序选择 | | [`persistent_vector.ml`](persistent_vector.ml) | 持久化向量 — Clojure 风格的具有结构共享的不可变数组 | 32 路分支字典树、O(log32 n) get/set、均摊 O(1) push_back、尾部缓冲区优化、暂存批量构建器、map/fold/filter/sub/append/rev | | [`probability.ml`](probability.ml) | 概率单子与蒙特卡洛模拟 | 单子组合、采样分布、统计、蒙特卡洛积分、马尔可夫链、贝叶斯推断 | | [`queue.ml`](queue.ml) | 纯函数式队列 (Okasaki 的 Banker's Queue) | 均摊 O(1) 入队/出队、双列表技术、持久性 | | [`quickcheck.ml`](quickcheck.ml) | QuickCheck — 基于属性的测试框架 | 随机生成器、单子组合子、Shrinking、反例最小化、属性规约 | | [`property_discovery.ml`](property_discovery.ml) | 自主属性发现引擎 — 代数不变量查找器 | 假设生成、20+ 属性类别、置信度评分、组合分析、渐进深化、关系推断 | | [`random_access_list.ml`](random_access_list.ml) | 随机访问列表 — Okasaki 的斜二进制随机访问列表 | O(1) cons/head/tail、O(log n) lookup/update、完全二叉树、斜二进制数、持久化数据结构 | | [`radix_tree.ml`](radix_tree.ml) | 基数树 (Patricia Trie) — 用于高效字符串存储的压缩前缀树 | 边压缩、前缀搜索、insert/remove/member、all_words 枚举、空间高效的字符串集合 | | [`raft.ml`](raft.ml) | Raft 共识算法 — 分布式共识模拟 | 领导者选举、日志复制、提交法定人数、网络分区、AppendEntries/RequestVote RPC | | [`raytracer.ml`](raytracer.ml) | 光线追踪 — 带有 Phong 着色的函数式光线追踪引擎 | Vec3/Ray/Camera、球体与平面相交、Blinn-Phong 光照、阴影、反射、抗锯齿、PPM 输出 | | [`rbtree.ml`](rbtree.ml) | 红黑树 — Okasaki 风格的自平衡 BST | 持久化数据结构、平衡不变量、集合操作、高阶函数 | | [`regex.ml`](regex.ml) | 正则表达式引擎 — 基于 NFA 的模式匹配 | 代数数据类型、递归下降解析、Thompson NFA、epsilon 闭包 | | [`relational.ml`](relational.ml) | Mini 关系代数引擎 — 对类型化表进行类 SQL 操作 | 模式验证、select/project/join/union、聚合、group-by、查询组合 | | [`rope.ml`](rope.ml) | 绳索 — 用于高效字符串操作的平衡二叉树 | O(log n) concat/split/insert/delete、文本编辑、平衡、行操作 | | [`sat_solver.ml`](sat_solver.ml) | 使用 DPLL 算法的 SAT 求解器 | 回溯、单元传播、纯文字消除、CNF 可满足性 | | [`segment_tree.ml`](segment_tree.ml) | 线段树 — 高效的范围查询与点更新 | 函子、单子抽象、sum/min/max 查询、O(log n) 更新 | | [`signal_processing.ml`](signal_processing.ml) | 信号处理 — FFT、卷积、频谱分析、加窗 | Cooley-Tukey 基数 2 FFT/IFFT、幅度/功率/相位谱、频谱质心、峰值检测、Hamming/Hann/Blackman/平顶窗、线性/循环卷积、互相关、自相关、信号发生器 (正弦/方波/锯齿/三角/Chirp/噪声)、过零率、RMS、移动平均、EMA | | [`skip_list.ml`](skip_list.ml) | 跳表 — 概率排序数据结构 | 随机层数、O(log n) 搜索/插入/删除、范围查询、floor/ceil | | [`splay_tree.ml`](splay_tree.ml) | 伸展树 — 自调整二叉搜索树 | 摊还 O(log n)、自顶向下伸展、split/merge、范围查询、秩、时间局部性 | | [`sorting.ml`](sorting.ml) | 排序算法 — 6 种带有基准测试工具的排序 | 插入、选择、快速排序 (三数取中)、堆排序、自然归并排序、计数排序 | | [`stream.ml`](stream.ml) | 惰性流 — 具有按需求值的无限/惰性序列 | 惰性求值、闭包、unfold/iterate/cycle、无限序列、记忆化 | | [`stm.ml`](stm.ml) | 软件事务内存 — 可组合的并发状态管理 | TVar、乐观并发、冲突检测retry/orElse、单子组合、有界通道、原子传输 | | [`string_match.ml`](string_match.ml) | 字符串匹配算法 — KMP、Boyer-Moore、Rabin-Karp、Aho-Corasick、Z 算法 | 失效函数、滚动哈希、多模式匹配、O(n+m) 匹配 | | [`suffix_array.ml`](suffix_array.ml) | 带有 LCP 数组的后缀数组 — 全文搜索与子串查询 | 后缀排序、Kasai LCP、O(m log n) 搜索、最长重复子串 | | [`suffix_automaton.ml`](suffix_automaton.ml) | 后缀自动机 (SAM) — 识别字符串所有后缀的最小 DFA | O(n) 构造、子串检查、不同子串计数、最长公共子串、出现计数、最短缺失字符串 | | [`term_rewriting.ml`](term_rewriting.ml) | 项重写系统 — 统一化、模式匹配、归约策略、Knuth-Bendix 完备化 | 一阶项、Robinson 统一化、LPO 排序、临界对、合流性检查、Peano/Boolean/群 TRS | | [`theorem_prover.ml`](theorem_prover.ml) | 通过自然演绎的命题定理证明器 | 矢列式证明搜索、回溯、推理规则、不可变上下文 | | [`trie.ml`](trie.ml) | 字典树 (前缀树) — 字符串存储、前缀搜索、自动补全 | Map 模块函子、递归记录、持久性、字符串操作 | | [`type_infer.ml`](type_infer.ml) | Hindley-Milner 类型推断引擎 (算法 W) | 统一化、类型变量、let 多态、约束生成、替换 | | [`union_find.ml`](union_find.ml) | 并查集 (不相交集) — 持久化函数式实现 | 按秩合并、路径压缩、Kruskal MST、分量分析 | | [`zipper.ml`](zipper.ml) | 拉链 — 用于导航和编辑不可变结构的函数式游标 | 单洞上下文、列表/树/文件系统拉链、Huet 拉链、玫瑰树、纯函数式编辑 | | [`euler_tour_tree.ml`](euler_tour_tree.ml) | 欧拉环游树 — 基于欧拉环游序列的动态森林连通性 | 由 Treap 支持的隐式序列、link/cut 操作、连通性查询、子树聚合、重新定根 | | [`incremental.ml`](incremental.ml) | 增量计算 — 自调整计算框架 | 依赖图、变更传播、Var/map/map2/bind/array_fold、观察者、截断函数、冻结、电子表格示例 | | [`hyperloglog.ml`](hyperloglog.ml) | HyperLogLog — 概率基数估计器 | 基于寄存器的草图、调和平均估计、偏差校正、merge/union、通过包含-排除原理的交集、Jaccard 相似度、序列化 | | [`aa_tree.ml`](aa_tree.ml) | AA 树 — 简化的红黑树 (Arne Andersson, 1993) | 基于层级的平衡、skew/split 操作、持久化 BST、简化的不变量 | | [`abstract_machine.ml`](abstract_machine.ml) | 抽象机模拟器 — SECD、CEK 和 Krivine 机器 | Lambda 演算求值、环境/栈可视化、逐步执行、多种归约策略、交互式 REPL | | [`adaptive_radix_tree.ml`](adaptive_radix_tree.ml) | 自适应基数树 (ART) — 具有自适应节点大小的缓存友好型基数树 | Node4/Node16/Node48/Node256、路径压缩、缓存效率、自适应节点增长 | | [`ant_colony.ml`](ant_colony.ml) | 蚁群优化 — 用于 TSP 的蚁群系统与最大最小蚁群系统 | 信息素轨迹、挥发、概率路径选择、MMAS 边界、收敛分析 | | [`argumentation.ml`](argumentation.ml) | Dung 的抽象论证框架 | 基础/首选/稳定/完全/可接受/理想语义、攻击关系、形式推理 | | [`astar.ml`](astar.ml) | A* 寻路算法 — 带有启发式的最优图搜索 | 优先队列、可采纳启发式、路径重构、基于网格的搜索 | | [`auction.ml`](auction.ml) | 多智能体拍卖模拟器 — 英式、荷式、密封一价、Vickrey | 自主竞价策略、自适应乘数、机制设计、博弈论 | | [`bandit.ml`](bandit.ml) | 多臂老虎机求解器 — 探索与利用策略 | Epsilon-Greedy、UCB1、Softmax、Thompson Sampling、EXP3、梯度 Bandit、遗憾分析、策略比较、非平稳检测、交互式 REPL | | [`bayesian_net.ml`](bayesian_net.ml) | 贝叶斯网络推断引擎 | 条件概率表、变量消除、置信传播、d-分离 | | [`bdi_agent.ml`](bdi_agent.ml) | BDI 智能体模拟器 — 信念-愿望-意图架构 | 自主智能体、计划库、意图执行、信念修正、手段-目的推理 | | [`benchmark.ml`](benchmark.ml) | OCaml 函数的基准测试框架 | 计时、统计分析、比较、预热、GC 控制 | | [`binomial_heap.ml`](binomial_heap.ml) | 二项堆 — 纯函数式可合并优先队列 | 二进制算术类比、进位传播、森林表示、O(log n) 合并 | | [`blackboard.ml`](blackboard.ml) | 黑板架构 — 协作式 AI 问题解决 | 知识源、机会调度、共享工作空间、增量细化 | | [`bplus_tree.ml`](bplus_tree.ml) | B+ 树 — 数据库风格的磁盘优化搜索树 | 叶子链表的顺序访问、范围查询、批量加载、内部/叶子节点分离 | | [`cellular_automata.ml`](cellular_automata.ml) | 元胞自动机 — 生命游戏、基本 (规则 110)、兰顿蚂蚁、线世界 | 网格模拟、规则表、邻域函数、ASCII 可视化 | | [`code_mentor.ml`](code_mentor.ml) | 自主代码导师 — 学习者熟练度评估引擎 | 8 个技能维度、差距分析、个性化练习、掌握度追踪 | | [`code_transform.ml`](code_transform.ml) | 自主代码转换流水线 — 多趟程序转换器 | AST 级别转换、优化遍、死代码消除、流水线组合 | | [`compression.ml`](compression.ml) | LZ77 压缩与解压 | 滑动窗口、最长匹配、反向引用、无损编码 | | [`consistent_hashing.ml`](consistent_hashing.ml) | 一致性哈希环 — 分布式系统键分布 | 虚拟节点、添加/移除时的最小重新映射、环拓扑、负载均衡 | | [`contract_net.ml`](contract_net.ml) | 合同网协议 — FIPA 多智能体任务分配 | 征求建议、投标、中标选择、任务分解、承包商评估 | | [`count_min_sketch.ml`](count_min_sketch.ml) | Count-Min Sketch — 概率频率估计 | 多重哈希函数、计数器表、频繁项、内积、流处理 | | [`cuckoo_filter.ml`](cuckoo_filter.ml) | 布谷鸟过滤器 — 支持删除的空间高效概率集 | 指纹识别、布谷鸟哈希、桶重定位、假阳性调整 | | [`dancing_links.ml`](dancing_links.ml) | 舞蹈链 (DLX) — Knuth 的算法 X 用于精确覆盖问题 | 双向循环链表、列覆盖/取消覆盖、数独/五格骨牌求解 | | [`dependency_auditor.ml`](dependency_auditor.ml) | 自主模块依赖审计器 | 模块图发现、循环检测、耦合度量、分层违规 | | [`dining_philosophers.ml`](dining_philosophers.ml) | 哲学家就餐 — 经典的并发问题与解决方案 | 死锁预防、资源层次、仲裁者、Chandy-Misra、饥饿分析 | | [`fibonacci_heap.ml`](fibonacci_heap.ml) | 斐波那契堆 — 摊还高效的优先队列 | 可变循环列表、级联剪切、O(1) 摊还 decrease-key、延迟合并 | | [`formal_verification.ml`](formal_verification.ml) | 自主形式化验证引擎 | 不变量检查、属性规约、状态空间探索、反例生成 | | [`forth.ml`](forth.ml) | Forth 解释器 — 基于栈的连接语言 | 字典、栈机器、字定义、立即字、控制流 | | [`hmm.ml`](hmm.ml) | 隐马尔可夫模型 — Viterbi、Forward-Backward、Baum-Welch | 状态估计、发射概率、期望最大化、序列标注、交互式 REPL | | [`http_server.ml`](http_server.ml) | 最小的 HTTP/1.1 服务器 | 请求解析、响应格式化、路由、Socket I/O | | [`influence_maximization.ml`](influence_maximization.ml) | 影响力最大化 — 社交网络的贪婪种子选择 | 独立级联模型、蒙特卡洛模拟、子模优化 | | [`kd_tree.ml`](kd_tree.ml) | k-d 树 — 用于多维数据的空间分区 | 交替分割维度、最近邻搜索、范围查询、空间索引 | | [`leader_election.ml`](leader_election.ml) | 分布式领导者选举模拟器 | 基于环的算法、LCR/HS 协议、消息复杂度、网络拓扑 | | [`leftist_heap.ml`](leftist_heap.ml) | 左式堆 — 偏向权重的可合并优先队列 | 秩属性、O(log n) 合并、持久化操作、优先级调度 | | [`link_cut_tree.ml`](link_cut_tree.ml) | Link-Cut Tree — 带有路径查询的动态树 | Sleator-Tarjan 基于 Splay 的森林、均摊 O(log n) link/cut/path、LCA 查询 | | [`logic_circuit.ml`](logic_circuit.ml) | 逻辑电路模拟器 | AND/OR/NOT/XOR 门、组合电路、传播延迟、真值表生成 | | [`maze.ml`](maze.ml) | 迷宫生成与求解 | DFS/Kruskal 生成、BFS/A* 求解、ASCII 渲染、随机种子控制 | | [`mdp.ml`](mdp.ml) | 马尔可夫决策过程求解器 | 值迭代、策略迭代、奖励塑造、折扣因子、最优策略 | | [`memoize.ml`](memoize.ml) | 记忆化组合子 — 用于递归函数的泛型缓存 | 哈希表缓存、不动点组合子、自动记忆化、缓存统计 | | [`mini_sql.ml`](mini_sql.ml) | Mini SQL 查询引擎 — 内存中的关系数据库 | SQL 解析、CREATE/INSERT/SELECT/UPDATE/DELETE、WHERE/JOIN/GROUP BY/HAVING、聚合 | | [`music.ml`](music.ml) | 算法音乐作曲 | 音符/和弦/音阶表示、生成模式、类 MIDI 输出、乐理 | | [`negotiation.ml`](negotiation.ml) | 自动化协商协议 — 多智能体双边协商 | 让步策略、效用函数、截止日期效应、帕累托效率 | | [`pairing_heap.ml`](pairing_heap.ml) | 配对堆 — 简单的自调整最小堆 | 两趟合并、均摊效率、纯函数式、持久化操作 | | [`persistent_array.ml`](persistent_array.ml) | 持久化数组 — 纯函数式的随机访问数组 | Braun 树支持、O(log n) get/set、结构共享、函数式更新 | | [`petri_net.ml`](petri_net.ml) | Petri 网模拟器 — 并发系统建模与分析 | 库所/变迁/令牌、触发规则、可达性分析、死锁检测 | | [`planning.ml`](planning.ml) | STRIPS 风格的 AI 规划器 — 自动规划 | 前置条件/效果、前向搜索、启发式规划、计划提取 | | [`polynomial.ml`](polynomial.ml) | 多项式算术 — 综合多项式库 | 稀疏表示、加法/乘法/除法、求值、微分、GCD | | [`process_calculus.ml`](process_calculus.ml) | CCS 进程演算 — Milner 的通信系统演算 | 通道通信、并行组合、限制、互模拟、LTS 生成 | | [`program_synthesis`](program_synthesis.ml) | 自主程序合成 — 从示例中发现函数 | 类型导向的枚举、示例引导的搜索、组合合成 | | [`prolog.ml`](prolog.ml) | Mini Prolog 解释器 — OCaml 中的逻辑编程 | 统一化、回溯、Horn 子句、截断、作为失败的双重否定、内建谓词 | | [`proof_assistant.ml`](proof_assistant.ml) | 交互式证明助手 (Coq-lite) | 策略、证明目标、类型理论、交互式定理证明 | | [`quadtree.ml`](quadtree.ml) | 四叉树 — 针对 2D 点数据的空间分区 | 递归细分、范围查询、k-最近邻、空间索引 | | [`reactive_streams.ml`](reactive_streams.ml) | 响应式流处理器 — 带有事件流的 FRP | 组合子、背压、窗口化、流转换、交互式 REPL | | [`refactoring_autopilot.ml`](refactoring_autopilot.ml) | 自主重构自动驾驶 — 机会检测与自动应用 | 代码坏味道检测、转换规则、安全检查、增量应用 | | [`ring_buffer.ml`](ring_buffer.ml) | 环形缓冲区 (循环缓冲区) — 固定大小的 FIFO 队列 | 数组支持、环绕索引、O(1) 入队/出队、溢出策略 | | [`scapegoat_tree.ml`](scapegoat_tree.ml) | 替罪羊树 — 无节点级元数据的加权平衡 BST | α-权重平衡、子树重建、均摊 O(log n)、无平衡位 | | [`simplex.ml`](simplex.ml) | 线性规划求解器 — 单纯形法 | 表格操作、主元选择、Bland 规则、可行性、优化 | | [`sparse_table.ml`](sparse_table.ml) | 稀疏表 — O(1) 范围最小/最大查询 | O(n log n) 预处理、重叠友好查询、幂等操作 | | [`spreadsheet.ml`](spreadsheet.ml) | 电子表格引擎 — 带有单元格引用的公式求值 | 依赖图、拓扑求值、循环引用检测、单元格函数 | | [`succinct_bitvector.ml`](succinct_bitvector.ml) | 简洁位向量 — 空间高效的 rank/select 查询 | 块/超级块结构、O(1) rank、二分搜索 select、近最优空间 | | [`suffix_tree.ml`](suffix_tree.ml) | 后缀树 — 受 Ukkonen 启发的用于字符串分析的构造 | 隐式/显式扩展、后缀链接、O(n) 构造、模式匹配 | | [`symbolic_regression.ml`](symbolic_regression.ml) | 符号回归 — 用于公式发现的遗传编程 | 表达式树、锦标赛选择、子树交叉/变异、简约度压力、ASCII 绘图、交互式 REPL | | [`task_scheduler.ml`](task_scheduler.ml) | 任务调度器 — 实时调度算法 | 速率单调、最早截止期优先、优先级调度、可行性分析 | | [`tensor.ml`](tensor.ml) | N 维张量库 — 纯 OCaml 张量操作 | 广播、切片、重塑、矩阵乘法、逐元素操作 | | [`treap.ml`](treap.ml) | 树堆 — 结合树 + 堆属性的随机化 BST | 随机优先级、旋转、期望 O(log n)、split/merge、持久化 | | [`turing_machine.ml`](turing_machine.ml) | 图灵机模拟器 | 纸带、转移函数、停机检测、多个示例、逐步执行 | | [`two_three_tree.ml`](two_three_tree.ml) | 2-3 树 — 带有 2-节点和 3-节点的平衡搜索树 | 自底向上插入、分裂传播、保证 O(log n)、删除 | | [`type_inference_debugger.ml`](type_inference_debugger.ml) | 自主类型推断调试器 — 逐步 HM 追踪 | 约束生成可视化、统一化步骤、替换解释 | | [`typeclass.ml`](typeclass.ml) | 类型类模拟 — 通过 OCaml 模块实现 Haskell 风格的类型类 | 模块类型、函子、特设多态、字典传递、Show/Eq/Ord/Functor | | [`van_emde_boas.ml`](van_emde_boas.ml) | Van Emde Boas 树 — O(log log u) 的整数集合操作 | 全域分解、递归聚类、前驱/后继查询 | | [`wavelet_tree.ml`](wavelet_tree.ml) | 小波树 — 序列上的 rank/select/access 查询 | 字母表二分、位向量节点、O(log σ) 查询、范围分位数 | | [`weight_balanced_tree.ml`](weight_balanced_tree.ml) | 加权平衡树 (BB[α]) — 大小平衡的 BST | 权重比不变量、单/双旋转、基于 join 的操作 | | [`yfast_trie.ml`](yfast_trie.ml) | Y-Fast Trie — O(n) 空间下的 O(log log u) 前驱/后继 | X-fast trie 间接、桶 BST、基于全域的索引 | | [`zip_tree.ml`](zip_tree.ml) | Zip 树 — 使用几何秩分布的随机化 BST | Zip/unzip 操作、期望 O(log n)、简单平衡、树堆变体 | ## 入门指南 ### 前置条件 - **OCaml** ≥ 4.08 — 通过 [opam](https://opam.ocaml.org/doc/Install.html) 或您的包管理器安装 - **GNU Make** (可选，用于批量构建) ``` # macOS brew install ocaml opam # Ubuntu/Debian sudo apt install ocaml opam # Windows (推荐使用 WSL) sudo apt install ocaml opam # 验证安装 ocaml -version ``` ### 通过 opam 安装 本项目已通过其独立的仓库 overlay 发布为 opam 包： ``` # 添加软件包仓库 opam repo add ocaml-sample-code https://sauravbhattacharya001.github.io/Ocaml-sample-code/ # 安装软件包 (构建所有程序并运行测试) opam install ocaml-sample-code ``` ### 构建与运行 ``` # 克隆 repo git clone https://github.com/sauravbhattacharya001/Ocaml-sample-code.git cd Ocaml-sample-code # 构建所有程序 make # 构建并运行所有程序 make run # 清理构建产物 make clean ``` ### Docker 在容器中运行所有示例——无需安装本地 OCaml： ``` docker build -t ocaml-samples . docker run --rm ocaml-samples ``` 运行单个示例： ``` docker run --rm ocaml-samples mergesort ``` ### 运行单个文件 ``` # 编译并运行单个文件 ocamlopt -o factor factor.ml && ./factor # 或者使用交互式 REPL ocaml #use "factor.ml";; ``` ## 代码亮点 ### 质因数分解 — `factor.ml` 优化的试除法：首先提取因子 2，然后只检查奇数除数。当剩余值必定为质数时，在 √n 处提前退出。 ``` let factors n = if n < 2 then invalid_arg "factors: input must be >= 2" else let rec extract_twos n = if n mod 2 = 0 then 2 :: extract_twos (n / 2) else odd_factors 3 n and odd_factors d n = if n = 1 then [] else if d * d > n then [n] else if n mod d = 0 then d :: odd_factors d (n / d) else odd_factors (d + 2) n in extract_twos n ``` ``` factors 12 → [2; 2; 3] factors 360 → [2; 2; 2; 3; 3; 5] factors 97 → [97] ``` ### 二叉搜索树 — `bst.ml` 使用代数数据类型的完整 BST。演示了插入、删除 (使用中序后继替换)、成员检查以及使用累加器的 O(n) 中序遍历。 ``` type 'a tree = | Leaf | Node of 'a tree * 'a * 'a tree let rec insert x = function | Leaf -> Node (Leaf, x, Leaf) | Node (left, v, right) -> if x < v then Node (insert x left, v, right) else if x > v then Node (left, v, insert x right) else Node (left, v, right) (* O(n) traversal — accumulator avoids quadratic list concatenation *) let inorder tree = let rec aux acc = function | Leaf -> acc | Node (left, v, right) -> aux (v :: aux acc right) left in aux [] tree ``` ``` In-order: 1 3 4 5 6 7 8 Contains 4: true | Contains 9: false Depth: 3 | Size: 7 After deleting 3: 1 4 5 6 7 8 ``` ### 归并排序 — `mergesort.ml` 通过比较函数参数化以实现最大的灵活性。`split` 和 `merge` 都是尾递归的，无需栈溢出即可处理大量输入。 ``` let rec mergesort cmp = function | ([] | [_]) as l -> l | lst -> let (left, right) = split lst in merge cmp (mergesort cmp left) (mergesort cmp right) ``` ``` Original: [38; 27; 43; 3; 9; 82; 10] Sorted asc: [3; 9; 10; 27; 38; 43; 82] Sorted desc: [82; 43; 38; 27; 10; 9; 3] Words sorted: [apple; banana; cherry; date] ``` ### 图算法 — `graph.ml` 包含邻接表 (基于 Map)、BFS/DFS 遍历、最短路径、连通分量、环检测 (三色 DFS) 和拓扑排序 (Kahn 算法) 的完整图库。 ``` module IntMap = Map.Make(Int) type graph = { adj: int list IntMap.t; directed: bool; } let bfs g start = let visited = Hashtbl.create 16 in let queue = Queue.create () in Queue.push start queue; Hashtbl.replace visited start true; (* ... imperative BFS with O(1) queue operations *) ``` ``` BFS from 1: [1; 2; 3; 4; 5] DFS from 1: [1; 2; 4; 3; 5] Shortest path 1->5: [1; 2; 4; 5] Connected components: 2 Topological order: [1; 3; 2; 4; 5] Has cycle: true (directed graph with back edge) ``` ### 优先队列 — `heap.ml` 一个纯函数式的左式最小堆。每个操作都返回一个新堆——原始堆被保留 (持久性)。“左式”属性通过保持右侧脊柱较短来确保合并以 O(log n) 运行。 ``` type 'a heap = | Empty | Node of int * 'a * 'a heap * 'a heap (* Node (rank, value, left_child, right_child) *) (* Merge is the fundamental operation — O(log n) *) let rec merge cmp h1 h2 = match h1, h2 with | Empty, h | h, Empty -> h | Node (_, x, a1, b1), Node (_, y, _, _) -> if cmp x y <= 0 then make_node x a1 (merge cmp b1 h2) else merge cmp h2 h1 (* Everything else is built on merge *) let insert cmp x h = merge cmp (Node (1, x, Empty, Empty)) h let delete_min cmp = function | Empty -> Empty | Node (_, _, left, right) -> merge cmp left right ``` ``` Sorted: [1; 2; 3; 4; 5; 6; 7; 8] Heap sort: [3; 5; 12; 17; 28; 42; 50; 61; 84; 93] Top 3 smallest: [3; 7; 12] Persistence: original heap unchanged after insert/delete ``` ### 字典树 (前缀树) — `trie.ml` 一个用于高效字符串存储和基于前缀检索的纯函数式字典树。使用 OCaml 的 `Map.Make` 函子来实现字符索引的子节点。每个操作都返回一个新的字典树——原始树被保留 (持久性)。删除操作会修剪不再需要的节点。 ``` module CharMap = Map.Make(Char) type trie = { is_word: bool; (* does a word end here? *) children: trie CharMap.t; (* children keyed by char *) } (* Insert — walk down, create nodes as needed *) let rec insert word trie = match chars with | [] -> { node with is_word = true } | c :: rest -> let child = match CharMap.find_opt c node.children with | Some t -> t | None -> empty in { node with children = CharMap.add c (aux rest child) node.children } (* Prefix search — find subtrie then collect all words *) let words_with_prefix prefix trie = match find_subtrie prefix trie with | None -> [] | Some subtrie -> collect_all_words subtrie ``` ``` member "apple": true | member "ap": false has_prefix "app": true | has_prefix "xyz": false Auto-complete "app" -> [app; apple; application; apply] Auto-complete "car" -> [car; card; care; careful; cart] LCP of [flower; flow; flight]: "fl" All words sorted: [ball; bat; car; card; cat] ``` ### 正则表达式引擎 — `regex.ml` 使用 Thompson NFA 构造从头开始构建的完整正则表达式引擎。将正则表达式语法解析为 AST，将其编译为非确定性有限自动机，并使用 epsilon 闭包进行模拟——保证线性时间匹配，没有病态的回溯。 ``` (* Regex AST — algebraic data types *) type char_matcher = Lit of char | Dot | Class of (char * char) list * bool type regex = Empty | Char of char_matcher | Seq of regex * regex | Alt of regex * regex | Star of regex | Plus of regex | Opt of regex | Anchor_start | Anchor_end (* Thompson's NFA construction — fragments with epsilon transitions *) let rec build r = match r with | Star r1 -> let f = build r1 in let s = new_state () in let a = new_state () in add_trans s (Epsilon f.frag_start); add_trans s (Epsilon a); add_trans f.frag_accept (Epsilon f.frag_start); add_trans f.frag_accept (Epsilon a); { frag_start = s; frag_accept = a } | (* ... other cases ... *) (* NFA simulation — set-based, no backtracking *) let simulate_at nfa input start_pos = let current = ref (epsilon_closure nfa [nfa.start] input start_pos) in (* Step through input, tracking longest match *) ``` ``` matches "hello" "hello" = true matches "ab+c" "abbc" = true (* quantifiers *) matches "ab+c" "ac" = false matches "colou?r" "color" = true (* optional *) matches "colou?r" "colour" = true matches "cat|dog" "cat" = true (* alternation *) find "[0-9]+" "abc 123 def" = "123" at pos 4 find_all "[a-z]+" "hello world" = ["hello"; "world"] replace "[0-9]+" "abc 123 def 456" "#" = "abc # def #" split "[,;]\s*" "apple, banana; cherry" = ["apple"; "banana"; "cherry"] ``` ### 最后一个元素 — `list_last_elem.ml` 使用 `Option` 的经典安全列表遍历——空列表无异常，无崩溃。 ``` let rec last = function | [] -> None | [x] -> Some x | _ :: t -> last t ``` ### 解析器组合子 — `parser.ml` 从小巧、可组合的部件构建复杂的解析器。每个解析器都是一个接受输入并返回值或错误的函数——它们可以使用 `>>=` (bind)、`<|>` (选择) 和 `many` 等操作符像乐高积木一样拼接在一起。 ``` (* A parser is just a function *) type 'a parser = string -> int -> 'a result (* Combine two parsers in sequence (monadic bind) *) let bind p f = fun input pos -> match p input pos with | Error _ as e -> e | Ok (a, pos') -> (f a) input pos' (* Parse an arithmetic expression with correct precedence *) let expr = chainl1 term add_op (* + - are left-associative *) let term = chainl1 power mul_op (* * / are left-associative *) let power = chainr1 atom pow_op (* ^ is right-associative *) let atom = number <|> parens (* number or (expr) *) ``` ``` calc "2 + 3 * 4" = 14 (* precedence: 2 + (3*4) *) calc "(2 + 3) * 4" = 20 (* parentheses override *) calc "2 ^ 3 ^ 2" = 512 (* right-assoc: 2^(3^2) = 2^9 *) calc "((3+5)*2)-(10/2)" = 11 int_list "[1, 2, 3]" = [1; 2; 3] kv "name = \"Alice\"" = ("name", "Alice") ``` ## 项目结构 ``` Ocaml-sample-code/ ├── hello.ml # Variables, types, pipes, pattern matching ├── fibonacci.ml # Fibonacci: naive vs memoized vs iterative ├── bst.ml # Binary search tree ├── factor.ml # Prime factorization ├── list_last_elem.ml # Last element of a list ├── mergesort.ml # Merge sort ├── merkle_tree.ml # Merkle tree (cryptographic hash trees) ├── graph.ml # Graph algorithms (BFS, DFS, topological sort) ├── dijkstra.ml # Weighted graphs (Dijkstra, Floyd-Warshall, Prim) ├── heap.ml # Priority queue (leftist min-heap) ├── parser.ml # Parser combinators (arithmetic, lists, key-value) ├── trie.ml # Trie (prefix tree) — string storage, prefix search ├── regex.ml # Regular expression engine (Thompson's NFA) ├── stream.ml # Lazy streams (infinite sequences) ├── stm.ml # Software Transactional Memory (STM) ├── rbtree.ml # Red-Black tree (Okasaki-style BST) ├── sorting.ml # 6 sorting algorithms with benchmarks ├── union_find.ml # Union-Find (disjoint sets, Kruskal's MST) ├── hashmap.ml # Functional hash map (persistent) ├── bloom_filter.ml # Bloom filter (probabilistic set) ├── lru_cache.ml # LRU cache (bounded, persistent) ├── segment_tree.ml # Segment tree (range queries) ├── signal_processing.ml # Signal processing (FFT, convolution, spectral analysis) ├── skip_list.ml # Skip list (probabilistic sorted structure) ├── splay_tree.ml # Splay tree (self-adjusting BST) ├── rope.ml # Rope (text editing data structure) ├── btree.ml # B-Tree (multi-way search tree) ├── json.ml # JSON parser (RFC 8259) ├── matrix.ml # Matrix / linear algebra (functors) ├── csv.ml # CSV parser & data analyzer ├── fenwick_tree.ml # Fenwick tree (binary indexed tree) ├── crypto.ml # Classical ciphers (Caesar, Vigenère, etc.) ├── crdt.ml # CRDTs (Conflict-free Replicated Data Types) ├── calculus.ml # Symbolic differentiation ├── cartesian_tree.ml # Cartesian tree with RMQ support ├── integration.ml # Symbolic integration engine ├── probability.ml # Probability monad & Monte Carlo ├── minikanren.ml # miniKanren logic programming ├── effects.ml # Algebraic effects and handlers ├── autodiff.ml # Automatic differentiation (forward & reverse) ├── free_monad.ml # Free monads (effect interpretation) ├── frp.ml # Functional reactive programming ├── network_flow.ml # Network flow (max flow, min-cut, MCMF) ├── neural_network.ml # Feedforward neural network (MLP, backpropagation) ├── bytecode_vm.ml # Bytecode VM with compiler ├── term_rewriting.ml # Term rewriting (Knuth-Bendix completion) ├── zipper.ml # Zippers for immutable structures ├── quickcheck.ml # Property-based testing framework ├── property_discovery.ml # Autonomous property/invariant discovery engine ├── random_access_list.ml # Random access list (skew-binary) ├── finger_tree.ml # Finger trees (Hinze & Paterson) ├── persistent_vector.ml # Persistent vector (Clojure-style) ├── abstract_interp.ml # Abstract interpretation (interval domain) ├── actor.ml # Actor model (Erlang-style concurrency) ├── automata.ml # Finite automata toolkit (DFA/NFA) ├── comonad.ml # Comonads (context-dependent computation) ├── constraint.ml # Constraint solver (CSP with AC-3) ├── csp.ml # Constraint satisfaction (Sudoku, N-Queens) ├── datalog.ml # Datalog query engine ├── deque.ml # Purely functional deque (Banker's Deque) ├── delimited_cont.ml # Delimited continuations (shift/reset) ├── diff.ml # Myers diff algorithm (git diff) ├── earley.ml # Earley parser (any CFG) ├── fsm.ml # Finite state machines ├── gadts.ml # GADTs (type-safe evaluators) ├── game_ai.ml # Minimax game AI (Tic-Tac-Toe, Connect Four) ├── gc_simulator.ml # Garbage collector simulator (4 algorithms) ├── genetic.ml # Genetic algorithm (evolutionary optimization) ├── geometry.ml # Computational geometry (convex hull, etc.) ├── gossip.ml # Gossip protocol simulator (push/pull/push-pull) ├── graph_db.ml # Property graph query engine ├── hamt.ml # Hash Array Mapped Trie (persistent hash map) ├── huffman.ml # Huffman coding (lossless compression) ├── hyperloglog.ml # HyperLogLog (probabilistic cardinality estimation) ├── interval_tree.ml # Interval tree (augmented AVL) ├── lambda.ml # Untyped lambda calculus interpreter ├── lsystem.ml # L-Systems (Lindenmayer systems, turtle graphics) ├── model_checker.ml # CTL model checker ├── monad_transformers.ml # Monad transformers (composable stacks) ├── order_statistics_tree.ml # Order Statistics Tree (rank, select, range) ├── optics.ml # Optics (lenses, prisms, traversals) ├── peg.ml # PEG parser (packrat memoization) ├── queue.ml # Purely functional queue ├── radix_tree.ml # Radix Tree (Patricia Trie) — compressed prefix tree ├── raft.ml # Raft consensus algorithm ├── raytracer.ml # Ray tracing engine (functional) ├── relational.ml # Relational algebra engine ├── sat_solver.ml # SAT solver (DPLL algorithm) ├── string_match.ml # String matching (KMP, Boyer-Moore, etc.) ├── suffix_array.ml # Suffix array with LCP ├── suffix_automaton.ml # Suffix Automaton (SAM) ├── suffix_tree.ml # Suffix tree (Ukkonen-inspired) ├── tensor.ml # N-dimensional tensor library ├── theorem_prover.ml # Propositional theorem prover ├── treap.ml # Treap (tree + heap) ├── turing_machine.ml # Turing machine simulator ├── type_infer.ml # Hindley-Milner type inference ├── incremental.ml # Incremental computation (self-adjusting) ├── test_*.ml # Test suites ├── LEARNING_PATH.md # Progressive learning guide ├── Dockerfile # Multi-stage Docker build ├── .dockerignore # Docker build context exclusions ├── Makefile # Build automation ├── docs/ │ └── index.html # GitHub Pages documentation site ├── .github/ │ └── workflows/ │ ├── coverage.yml # Code coverage workflow │ └── pages.yml # Pages deployment workflow ├── .editorconfig # Editor formatting rules ├── .gitignore # Build artifact exclusions ├── CONTRIBUTING.md # Contribution guidelines & style guide └── LICENSE # MIT License ``` ## 文档 📖 **交互式文档站点：** [sauravbhattacharya001.github.io/Ocaml-sample-code](https://sauravbhattacharya001.github.io/Ocaml-sample-code/) 该文档站点具有语法高亮的代码示例，并显示了每个程序的预期输出。 ## 学习资源 📚 **[学习路径](LEARNING_PATH.md)** — 按照从基础到高级概念的顺序学习本仓库示例的指导路线。 刚接触 OCaml？这些资源是对本仓库示例的补充： - [**OCaml.org 教程**](https://ocaml.org/docs) — 官方指南和语言手册 - [**Real World OCaml**](https://dev.realworldocaml.org/) — 全面的免费书籍 - [**99 Problems in OCaml**](https://ocaml.org/exercises) — 按难度划分的练习题 - [**OCaml Playground**](https://ocaml.org/play) — 在浏览器中尝试 OCaml ## 测试与覆盖率 该仓库包含涵盖所有核心算法的综合测试套件 (`test_all.ml`)： ``` # 运行测试 make test # 运行带覆盖率的测试 (需要 bisect_ppx) opam install bisect_ppx ocamlfind make coverage # 生成 HTML 覆盖率报告 make coverage-html # 在浏览器中打开 _coverage/index.html ``` **经过测试的算法：** BST 操作、质因数分解、斐波那契 (朴素/记忆化/迭代)、归并排序、最小/最大堆、列表操作、图算法 (BFS、DFS、最短路径、环检测、拓扑排序、连通分量)、字典树操作 (插入、删除、成员、前缀搜索、自动补全、最长公共前缀、修剪、持久性)、解析器组合子 (原语、组合子、算术表达式求值)、正则表达式引擎 (解析、匹配、量词、交替、字符类、锚点、find/find_all/replace/split)。 覆盖率报告会在每次推送时通过 [GitHub Actions](https://github.com/sauravbhattacharya001/Ocaml-sample-code/actions/workflows/coverage.yml) 使用 [bisect_ppx](https://github.com/aantron/bisect_ppx) 自动生成。 ## 许可证 本项目基于 MIT 许可证授权——详情请参阅 [LICENSE](LICENSE) 文件。

标签：DNS解析, OCaml, Web安全扫描, 代码库, 代码示例, 函数式编程, 分布式系统, 响应大小分析, 图算法, 定理证明器, 密码学, 开源项目, 形式化验证, 手动系统调用, 教育学习, 数据分析, 数据结构, 模式匹配, 漏洞数据库, 神经网络, 算法实现, 类型系统, 编程语言, 编译器, 自动化资产收集, 解析器, 解释器, 计算机科学, 设计模式, 请求拦截, 软件开发, 高阶函数