在Coq中重写列表压缩

Question

我有以下Haskell函数，该函数输出所有可能的方法来拆分列表：

split :: [a] -> [([a], [a])]
split []     = [([], [])]
split (c:cs) = ([], c : cs) : [(c : s1, s2) | (s1, s2) <- split cs]

一些示例输入：

*Main> split [1]
[([],[1]),([1],[])]
*Main> split [1,2]
[([],[1,2]),([1],[2]),([1,2],[])]
*Main> split [1,2,3]
[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

考虑到默认情况下没有模式匹配，并且我不想为其定义符号，因此我尝试在Coq中编写相同的函数，所以我决定改写一个递归函数：

Require Import Coq.Lists.List.
Import ListNotations.

Fixpoint split {X : Type} (l : list X) : list (list X * list X) :=
  match l with
    | [] => [([], [])]
    | c::cs =>
      let fix split' c cs :=
          match cs with
            | [] => []
            | s1::s2 => (c++[s1], s2) :: split' (c++[s1]) s2
          end
      in
      ([], c :: cs) :: ([c], cs) :: split' [c] cs
  end.

产生相同的结果：

     = [([], [1]); ([1], [])]
     : list (list nat * list nat)
     = [([], [1; 2]); ([1], [2]); ([1; 2], [])]
     : list (list nat * list nat)
     = [([], [1; 2; 3]); ([1], [2; 3]); ([1; 2], [3]); ([1; 2; 3], [])]
     : list (list nat * list nat)

但是，它太冗长了，关于如何使用Coq中的HOF将其转换为更具可读性的函数的任何提示？

Answer 1

Haskell版本中的理解是map（或更普遍地flat_map）使用的语法糖。

Fixpoint split {X : Type} (l : list X) : list (list X * list X) :=
  match l with
  | [] => [([], [])]
  | c::cs =>
      ([], c :: cs) :: map (fun '(s1, s2) => (c :: s1, s2)) (split cs)
  end.