You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

Coq中split_string函数实现与无信息丢失证明求助

Coq split_string 实现与证明问题

我在Coq中实现了split_string函数,该函数接收list ascii类型的字符串与f: ascii->bool类型的函数,会在f返回true的ASCII字符处分割字符串,并将分隔符保留为长度1的list ascii字符串。

问题1:Coq标准库是否存在该函数?

因未找到对应库函数,自行实现了如下代码:

Fixpoint split_string (f: ascii->bool) (z s: list ascii): list (list ascii) :=
match s with
| [] => [rev z]
| h::t => match f h with
  | true => ([rev z]++[[h]])++(split_string f [] t)
  | false => (split_string f (h::z) t)
  end
end.

调用时需传入空的z参数,例如:

Compute split_string isWhite [] some_string.

问题2:证明输出扁平化后与原输入相等

需要证明该函数的输出经concat扁平化后与原输入相等(无信息丢失),已提出定理:

Theorem not_more_not_less_splitWhite: forall (s: list ascii),
s = concat (split_string isWhite [] s).

使用归纳法证明时,处理非空白字符后z不再为空,无法应用归纳假设,目前证明进度如下:

Proof. intros s. induction s.
- simpl. reflexivity.
- simpl. destruct isWhite eqn:W.
   * simpl. rewrite <- IHs. reflexivity.
   * 

若标准库无对应函数,请求指导如何完成证明,或提供更优的split_string实现方案。

内容的提问来源于stack exchange,提问作者Leo G.

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.26 03:16:06