我具有以下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中编写相同的函数,因为默认情况下没有模式匹配,并且我还不想使用define a notation for it,所以我决定改写一个递归函数:
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将其转换为更具可读性的功能的任何提示?
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.