代码之家  ›  专栏  ›  技术社区  ›  Rahul Manne

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

  •  2
  • Rahul Manne  · 技术社区  · 7 年前

    为什么要进行函数合成( ∘ $ )使实现在中可用 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
    

    我最初认为这背后的理由是 $ 能够处理 $' :: ,其中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 ∷ []) ∷ []
    
    2 回复  |  直到 7 年前
        1
  •  4
  •   András Kovács    7 年前

    ∘′ $′ 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
    
        2
  •  0
  •   Sassa NF    7 年前

    正如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 可以“铸造”到 FY

    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 ,而不是依赖函数;但我就是想不出更好的名字)