为什么函数组合和应用程序在 Agda 中有依赖实现？

Question

为什么函数组合（∘）和应用程序（$）在https://github.com/agda/agda-stdlib/blob/master/src/Function.agda#L74-L76中有可用的实现？为方便起见复制在这里：

_∘_ : ∀ {a b c}
        {A : Set a} {B : A → Set b} {C : {x : A} → B x → Set c} →
        (∀ {x} (y : B x) → C y) → (g : (x : A) → B x) →
        ((x : A) → C (g x))
f ∘ g = λ x → f (g x)

_∘'_ : ∀ {a b c} {A : Set a} {B : Set b} {C : Set c} →
         (B → C) → (A → B) → (A → C)
f ∘' g = λ x → f (g x)

_$_ : ∀ {a b} {A : Set a} {B : A → Set b} →
      ((x : A) → B x) → ((x : A) → B x)
f $ x = f x

_$'_ : ∀ {a b} {A : Set a} {B : Set b} →
       (A → B) → (A → B)
f $' x = f x

我最初认为这背后的基本原理是 $ 能够处理 $' 无法处理的更高阶类型。例如，考虑 A=Nat，B=List，f 是 ::，其中 B 依赖于 A。但是经过大量测试，我无法想出一个例子将表明 $' 的实施是不够的。 $ 能处理哪些 $' 不能处理的场景？（同样，∘ 处理哪些场景 ∘' 不处理？

open import Agda.Builtin.Nat public
open import Agda.Primitive public

--data List {a} (A : Set a) : Set a where
--  []  : List A
--  _∷_ : (x : A) (xs : List A) → List A

data Vec {a} (A : Set a) : Nat → Set a where
  []  : Vec A zero
  _∷_ : ∀ {n} (x : A) (xs : Vec A n) → Vec A (suc n)

tail : ∀ {a n} {A : Set a} → Vec A (suc n) → Vec A n
tail (x ∷ s) = s

_$_ : ∀ {a b} {A : Set a} {B : A → Set b} →
      ((x : A) → B x) → ((x : A) → B x)
f $ x = f x

_$'_ : ∀ {a b} {A : Set a} {B : Set b} →
       (A → B) → (A → B)
f $' x = f x

_∘_ : ∀ {a b c}
        {A : Set a} {B : A → Set b} {C : {x : A} → B x → Set c} →
        (∀ {x} (y : B x) → C y) → (g : (x : A) → B x) →
        ((x : A) → C (g x))
f ∘ g = λ x → f (g x)

_∘'_ : ∀ {a b c} {A : Set a} {B : Set b} {C : Set c} →
         (B → C) → (A → B) → (A → C)
f ∘' g = λ x → f (g x)

Vecc : ∀ {a} → Nat → (A : Set a) → (Set a)
Vecc x y = Vec y x

data Pair {a b} (A : Set a) (B : A → Set b) : Set (a ⊔ b) where
  _,_ : (x : A) → (y : B x) → Pair A B

-- Dependent Pair attempt
--fst : ∀ {a b} {A : Set a} {B : A → Set b} → Pair A B → A
--fst (a , b) = a
--
--f : Pair Nat $' Vec Nat
--f = _,_ zero $' []
--
--g : Pair (Pair Nat $' Vec Nat) $' λ x → Nat
--g = _,_ (_,_ zero $' []) $' zero

-- Some other attempt
--f : ∀ {a n} {A : Set a} → Vec A ((suc ∘' suc) n) → Vec A n
--f {a} = tail {a} ∘' tail {a}

-- Vec attempt
--f : ∀ {a} (A : Set a) → (Set a)
--f {a} = Vecc {a} (suc zero) ∘' Vecc {a} (suc zero)
--
--h = f Nat
--
--x : h
--x = (zero ∷ []) ∷ []

-- List attempt
--f : ∀ {a} (A : Set a) → (Set a)
--f {a} = List {a} ∘' List {a}
--
--g : ∀ {a} (A : Set a) → (Set a)
--g {a} = List {a} ∘ List {a}
--
--h = f Nat
--i = g Nat
--
--x : h
--x = (zero ∷ []) ∷ []

Answer 1

∘′ 和 $′ 不适用于依赖函数。您只是没有尝试使用依赖函数进行任何测试。对于 f $ x 个示例，f 必须是相关的，对于 f ∘ g，两个函数中的任何一个都必须是相关的。示例：

open import Data.Nat
open import Data.Vec
open import Function
open import Relation.Binary.PropositionalEquality

replicate' : {A : Set} → A → (n : ℕ) → Vec A n
replicate' a n = replicate a

refl' : {A : Set}(a : A) → a ≡ a
refl' a = refl

-- fail1 : Vec ℕ 10
-- fail1 = replicate' 10 $′ 10

ok1 : Vec ℕ 10
ok1 = replicate' 10 $ 10

-- fail2 : ∀ n → replicate' 10 n ≡ replicate' 10 n
-- fail2 = refl' ∘′ replicate' 10

ok2 : ∀ n → replicate' 10 n ≡ replicate' 10 n
ok2 = refl' ∘ replicate' 10

Answer 2

正如 Andras Kovacs 所提到的，一个使用依赖函数，另一个不使用。

重要的区别在于，对于非依赖函数，可以构建更强的证明。例如：

eq : {A B} -> f : (A -> B) -> x y : A -> x == y -> (f x) == (f y)
eq f x .x refl = refl

这里我们可以构造f x和f y相等。但是我们不能对依赖函数做同样的事情——因为没有办法证明 B x == B y。所以只有更弱的证明f x可以是"cast"到f y.

transport : {A} {B : A -> Set} -> f : (x : A -> B x) -> x y : A -> x == y -> f x -> f y
transport f x .x refl fx = fx

（实际上，transport通常定义为B x -> B y，不是依赖函数；但我想不出更好的名字）

为什么函数组合和应用程序在 Agda 中有依赖实现？

Why do function composition and application have a dependent implementation in Agda?

agda