Coq 中自然数的 n 元函数组合

Question

我想定义一个函数 compose，它将 f : nat ^^ n --> nat 与 g1 ... gn : nat ^^ m --> nat 组合成

compose n m f g1 ... gn x1 ... xm

等于

f (g1 x1 ... xm) ... (gn x1 ... xm)

使用 standard library for n-ary functions，为特殊情况定义它 n = 1 并不难：

Fixpoint compose_unary (m : nat) (g : nat -> nat) :
(nat ^^ m --> nat) -> (nat ^^ m --> nat) := 
match m return ( (nat ^^ m --> nat) -> 
(nat ^^ m --> nat) ) with  
| O    => fun x => (g x)
| S m' => fun f => fun x 
       => compose_unary m' g (f x)
end.

至于一般情况，我很确定类型声明应该是

Fixpoint compose (n m : nat) 
(g : nat ^^ n --> nat) : 
(nat ^^ m --> nat) ^^ n 
--> (nat ^^ m --> nat)

但我不知道如何从这里开始。有什么建议吗？

Answer 1

这是我设法做到的，但不确定这是最简单的方法，因为我使用依赖类型和依赖模式匹配来编码家族 g1, ... , gn:

Require Import NaryFunctions Vector.

Open Scope type.

首先我需要一个函数来将函数 f: A^^n --> B 应用于 n-uplet x: A^^n:

Definition napply {A B:Type} (n :nat) (f: A ^^ n --> B) (x: A ^ n) : B :=
  nuncurry A B n f x.

那么这是您的撰写功能：

Fixpoint compose {A B C: Type} (n m: nat) (f: B ^^ m --> C) (gs: Vector.t (A ^^ n --> B) m) (xs: A ^ n) {struct gs } :  C :=
  match gs in Vector.t _ m' return (B ^^ m' --> C) -> A ^ n -> C with
    | nil _ => fun f0 _ => f0
    | cons _ hd p tl => fun fs ys => compose n p (fs (napply n hd ys)) tl ys
  end f xs
.

此函数采用函数 f : B^^m --> C 和类型 A^^n --> B 的 m 个函数的集合，并构建一个从 A ^ n 到 C 的真实函数。如有必要，您可以对其进行柯化：

Fixpoint compose_n {A B C: Type} (n m: nat) (f: B ^^ m --> C) (gs: Vector.t (A ^^ n --> B) m) : A ^^ n --> C :=
      ncurry _ _ n (compose n m f gs).

用 nat 实例化 A B C，你应该得到你想要的东西。

干杯，

V.

Coq 中自然数的 n 元函数组合

Composition of n-ary functions on natural numbers in Coq

coq

function-composition