Telekinesis
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Telekinesis
在纯函数式语言里,修改深层嵌套结构的一个元素(如三维数组 f 的 f[1][2][0]),只能把整条路径逐层拆开、重建、再拼回去。比如 Haskell 里把 f !! 1 !! 2 !! 0 改成 7:
f' = take 1 f ++ [ take 2 (f !! 1) ++ [ 7 : drop 1 (f !! 1 !! 2) ] ++ drop 3 (f !! 1) ] ++ drop 2 f -- painful!
嵌套越深越冗长,且每层结构重建方式不同,中途换结构就得重写。你希望拥有"隔空取物"的能力:不动手拆开任何一层,只"指出"目标位置,就拿到整个结构修改后的版本。任务就是设计并实现这个能力
调用链
比如说你要“修改”一个三位数组,
三种语言形式一致(Rust 版因 start 是内建属性名改叫 begin):
| 语言 | 用法 |
|---|---|
| Lean 4 | modifyto 7 $ index (index (start f) (1 : Fin 4)) (2 : Fin 3) |
| Haskell | modifyto 7 $ index (index (start f) 1) 2 |
| Rust | begin(&f).index(1).index(2).modifyto(7) |
start x/begin(&x):以整体结构x为起点创建一条"路径"(Rust 使用不可变借用&x,表示不可修改)。index p i/p.index(i):向下一层深入,索引i的类型必须与该层结构匹配。modifyto a p/p.modifyto(a):把路径指向的位置替换为a,返回整个最外层结构的新副本。
要求
- 任意深度:无论嵌套多少层,都用同一条调用链,不能按深度写特例。
- 任意层结构:每层可以是不同结构,如
Vec<Vec<(i32,Vec<i32>)>>。索引类型由该层类型类的实现方式决定:比如,Vec/列表/Vector α n用usize/Int/Fin n,二元组用Bool(false取左、true取右)。具体可以看代码给的模板,TypeClass/Trait 会提供一个索引的方式,所有你要索引的数据结构都 instance/impl 这个给的TypeClass/Trait 。 - 静态类型安全:索引或修改值类型错误必须编译失败。
- 不依赖具体结构:只能通过类型类/trait 接口与结构交互,评测器会自带你从未见过的结构及其 instance。
- 只修改指定位置,其余元素不变。
下发文件
| Lean 4 | Haskell | Rust | |
|---|---|---|---|
| 下发模板 | lean4/Telekinesis.lean |
haskell/Telekinesis.hs |
rust/Telekinesis.rs |
| 样例 | lean4/PublicTests.lean |
haskell/PublicTests.hs |
rust/PublicTests.rs |
提交时只需提交下发模板的完整实现:在模板文件中补齐 start/begin、index、modifyto 及所需辅助定义;类型类/trait 声明已随模板给出,实例由样例与评测侧提供,无需自己编写。
各语言实现要点
| Lean 4 | Haskell | Rust | |
|---|---|---|---|
| 已提供的类型类 | GetElem' / SetElem' |
GetElem / SetElem |
|
| 需要实现 | start、index、modifyto |
同左 | begin、index、modifyto |
| 限制 | 禁元编程/unsafe/axiom/sorry/partial,禁 import |
禁 TemplateHaskell、实例作弊 pragma、unsafeCoerce、undefined、import |
禁 unsafe/宏/include!/panic! 等 |
测试与评测
- 本地自测:是把下发模板和样例拼起来编译(haskell/rust 还要通过执行)。
- 评测:会使用比样例更强的一组测试点,方式与自测一致(拼接编译/执行)。
注:
- 如果出题人发现有人通过 hack 的方式过题,可能会修改测试数据。
- 下发文件点击右面的 file 下载,如果无法下载,请在这里下载,里面可能有一些可能造成不适的 ai 生成文档,请忽略