Dafny通用操作库问询：是否含partition及序列分区实现查询

1. 序列分区功能的现成实现 #

你需要的基于谓词的序列分区功能，确实已有现成的实现思路和代码示例。比如可以通过递归方式实现满足你后置条件的分区函数，示例代码如下：

function Partition<T>(s: seq<T>, p: T -> bool): (is_p: seq<T>, not_p: seq<T>)
  ensures forall x :: x in s <==> x in is_p || x in not_p
  ensures forall i, j :: 0 <= i < j < |s| ==> 
    (if p(s[i]) then 
      s[i] in is_p && (exists k < |is_p| :: is_p[k] == s[i]) && 
      (forall l < k :: is_p[l] == s[m] for some m < i)
     else 
      s[i] in not_p && (exists k < |not_p| :: not_p[k] == s[i]) && 
      (forall l < k :: not_p[l] == s[m] for some m < i))
{
  if s == [] then
    ([], [])
  else
    let (rest_p, rest_not_p) := Partition(s[1..], p) in
    if p(s[0]) then
      ([s[0]] + rest_p, rest_not_p)
    else
      (rest_p, [s[0]] + rest_not_p)
}

这段代码通过递归遍历序列，将满足谓词p的元素归入is_p，不满足的归入not_p，既保证了元素的原有顺序，也覆盖了输入序列的所有元素，完全符合你提出的后置条件。

2. 实用Dafny代码库 #

社区中确实存在维护中的实用Dafny代码库，比如官方扩展的标准库组件，还有社区贡献的工具集合，这些库通常包含序列操作、基础数据结构、常用算法等功能，你需要的分区函数很可能已经包含在内。

3. 搜索Dafny代码片段的方法 #

• GitHub代码搜索：这是很多开发者常用的方式，直接搜索关键词比如Dafny partition sequence或Dafny predicate partition，可以找到大量开源项目中的实现示例。
• Dafny社区资源：可以查看Dafny官方讨论区、社区论坛中的代码分享帖，很多用户会在这些地方发布常用功能的实现。
• 教程与示例仓库：不少Dafny学习教程会附带示例代码仓库，里面也可能包含序列分区这类基础操作的实现。

内容的提问来源于stack exchange，提问作者Carl