Roc 语言 List.drop_swap 详解O(1) 交换删除语义与 REPL 快照验证【免费下载链接】rocA fast, friendly, functional language.项目地址: https://gitcode.com/GitHub_Trending/ro/rocList.drop_swap是 Roc 标准库List模块中一个典型的交换删除swap-remove操作它删除指定索引处的元素但把最后一个元素移动到被删位置因此不保持剩余元素的原有顺序。本文以仓库中 REPL 快照测试 为骨架逐条解读其边界行为并深入到 Builtin.roc 的源码实现说明它为什么是 O(1)、为什么与drop_at语义不同以及 Roc 如何用快照测试固化这类语言级行为。一、drop_swap 是什么交换删除swap-remove语义在大多数编程语言的标准库中按索引删除元素有两种实现策略平移删除shift把被删元素之后的所有元素依次前移一位保持相对顺序但平均开销为 O(n)交换删除swap-remove把最后一个元素直接覆盖到被删位置再收缩长度只需 O(1)但剩余元素的顺序被破坏。List.drop_swap属于后者。在 Builtin.roc 中其声明与文档注释给出了权威定义## Removes the item at the given index by moving the last item into its ## place, so the order of the remaining items is not preserved. This is O(1), ## unlike drop_at, which shifts every later item down. ## ## Returns the list unchanged if the index is out of bounds. ## roc ## expect [1.I64, 2, 3, 4].drop_swap(1) [1, 4, 3] ## drop_swap : List(a), U64 - List(a)核心要点有三删除指定索引元素末位元素补位顺序不保证复杂度 O(1)与需要平移后续元素的drop_at见 Builtin.roc形成鲜明对比索引越界时返回原列表不做任何修改。二、从 REPL 快照逐条读懂 drop_swap 的完整行为list_drop_swap.md 是一个typerepl的 REPL 快照文件其# SOURCE段记录了 5 条交互输入# OUTPUT段给出了对应的求值结果。下面逐条解读。场景一删除中间元素» [1.I64, 2, 3, 4, 5].drop_swap(1) [1, 5, 3, 4]删除索引1处的元素2最后一个元素5被移动到索引1随后末尾被裁剪。注意结果中的元素顺序变为[1, 5, 3, 4]5顶替了原来2的位置而3、4保持原位——这正是顺序不保留的直观体现。如果使用drop_at结果会是保持顺序的[1, 3, 4, 5]。场景二删除最后一个元素» [1.I64, 2, 3].drop_swap(2) [1, 2]当被删索引恰好是最后一个元素索引2即长度 3 的末位时交换操作把末位元素与自身交换再裁剪一位等价于直接去掉末尾元素结果[1, 2]此时与drop_at行为一致。场景三越界索引返回原列表» [1.I64, 2, 3].drop_swap(9) [1, 2, 3]索引9远超列表长度3。按照文档约定drop_swap越界时原样返回列表不做任何修改也不会抛错。这与list_get、list_set等需要Try包装的访问操作不同是一个静默的无害操作。场景四对堆分配字符串列表的交换删除» heap [one long heap-allocated string that will not fit inline, two long heap-allocated string that will not fit inline, three long heap-allocated string that will not fit inline] assigned heap这里刻意构造了一个元素为长字符串的列表。Roc 对短字符串有内联inline优化小字符串直接存放在值内无需堆分配而这三个字符串过长、无法内联因此每个元素都是堆分配的用于验证drop_swap在涉及堆分配数据时同样正确工作。» heap.drop_swap(0) [three long heap-allocated string that will not fit inline, two long heap-allocated string that will not fit inline]删除索引0处的第一个字符串第三个最后一个字符串被移动到索引0结果仅剩两个元素且three...排在了最前面——交换删除的顺序破坏在此体现得更加明显。场景五原列表保持不变不可变语义» heap [one long heap-allocated string that will not fit inline, two long heap-allocated string that will not fit inline, three long heap-allocated string that will not fit inline]在调用heap.drop_swap(0)之后再次求值heap得到的是完整的三元素原列表。这说明drop_swap与其他List函数一样遵循函数式语言的不可变语义它返回一个新列表而不会原地修改调用者。这也是快照测试中特意安排这两条连续指令的原因——既展示交换删除的结果又验证原列表未被污染。三、源码级实现为什么它是 O(1)在 Builtin.roc 中drop_swap的实现只有短短几行drop_swap |list, index| { len List.len(list) if index len { List.drop_last(list_swap_unsafe(list, index, len - 1), 1) } else { list } }整个算法由三个原子步骤组成边界检查if index len先判断索引是否在界内越界直接返回原列表list对应场景三交换list_swap_unsafe(list, index, len - 1)将被删索引index与末位索引len - 1的元素互换。list_swap_unsafe在 Builtin.roc 中声明为由编译器实现、不执行边界检查的底层原语# Implemented by the compiler, does not perform bounds checks list_swap_unsafe : List(item), U64, U64 - List(item)正因为外层已经用index len保证了index与len - 1都在界内这里才能安全地使用_unsafe变体换取性能裁剪末尾List.drop_last(..., 1)删除交换后的最后一个元素。drop_last见 Builtin.roc从末尾去掉 n 个元素此处n 1正好移除被换到末尾的原目标元素。从实现可以推断整个操作不涉及任何逐元素平移固定为一次边界比较 一次原地交换 一次尾部裁剪因此无论列表多长都是常数时间操作即文档注释所强调的 O(1)。顺带一提list_swap_unsafe并不只服务于drop_swap。例如 Builtin.roc 中List.swap交换任意两个索引的元素也复用了它而有序删除drop_at由于需要维持相对顺序、逐个前移后续元素代价是 O(n)。两者适用场景不同需要保持顺序用drop_at追求常数时间且不在意顺序如实现集合、去重、批量清理用drop_swap。四、快照测试机制Roc 如何固化语言级行为list_drop_swap.md属于 Roc 仓库的REPL 快照测试体系文件采用四个固定小节组织小节作用本文件内容# META元信息ini 格式descriptionList.drop_swap removes an element by swapping it with the last one、typerepl# SOURCEREPL 输入以»提示符开头上述 5 条指令# OUTPUT期望输出指令间以---分隔5 段求值结果# PROBLEMS诊断/编译问题列表NIL无问题typerepl表明该快照会启动 REPL 逐条执行# SOURCE中的命令并把实际输出与# OUTPUT逐段比对。整个快照测试由 src/snapshot_tool/main.zig 驱动其 CLI 入口提供了几个关键选项见该文件--help文本roc snapshot [options] [snapshot_paths...]运行指定快照文件或目录--check-expected校验EXPECTED/OUTPUT段与实际输出一致--update-expected用实际输出更新期望段--trace-eval输出解释器跟踪信息仅适用于单个 REPL 快照。因此list_drop_swap.md不仅是一份文档更是一份可自动执行的回归测试任何对drop_swap实现或 REPL 求值、输出格式化的改动只要偏离上述 5 段期望输出快照校验就会失败从而把交换删除的语义细节固化为语言级契约。五、底层测试佐证零大小列表的容量行为除了 REPL 快照drop_swap还有专门的底层low-level评估测试。src/eval/test/eval_low_level_tests.zig 中的用例low_level - zero-sized list drop_swap reports zero capacity验证了极端情况.name low_level - zero-sized list drop_swap reports zero capacity, .source \\{ \\x : List({}) \\x [{}, {}, {}] \\r List.drop_swap(x, 0) \\(List.len(r), List.capacity(r)) \\} , .expected .{ .inspect_str (2, 0) },该用例使用元素类型为{}零大小类型的列表执行drop_swap(x, 0)期望结果是(2, 0)——即新列表长度为 2容量为 0。这验证了两件事对零大小元素编译器可以完全不分配存储空间容量为 0 是合法的交换删除后容量语义与drop_at、drop_first等删除族操作保持一致同文件紧邻的多个用例均断言了同样的(2, 0)行为。这从求值器层面补充确认了drop_swap与其它List删除函数在底层表示上的一致性。六、相关函数与延伸阅读drop_swap位于List删除/子集操作族中读者可在 src/build/roc/Builtin.roc 的List模块内对照阅读drop_at按索引删除但保持顺序O(n)Builtin.rocdrop_first/drop_last从头部/尾部批量删除Builtin.rocList.swap交换任意两个索引的元素同样是 O(1)其 REPL 快照见 list_swap.md、list_swap_oob.md、list_swap_same_index.mddrop_if按谓词条件删除快照见 list_drop_if.md。同一目录test/snapshots/repl/下还有list_drop_first、list_drop_last等系列快照可作为理解 RocListAPI 语义与快照测试格式的完整素材。若想亲自复现本文的全部行为可在仓库根目录构建roc可执行文件参考 BUILDING_FROM_SOURCE.md然后以 REPL 模式逐条输入本文# SOURCE段的指令观察输出是否与快照一致。【免费下载链接】rocA fast, friendly, functional language.项目地址: https://gitcode.com/GitHub_Trending/ro/roc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考