[Agda] Generic Programming with Indexed Functors

[Thorsten Altenkirch]

Maybe I miss something but why don’t we represent strictly positive functors just as indexed containers, that is

Cont I O = Sigma S : O -> Set. P : (o : O) -> S o -> I -> Set

This gives rise to an indexed functor and it is closed under all desired operations including fixed points without any problems with the positivity checker. This was carried out in some detail in our papers on indexed containers http://www.cs.nott.ac.uk/~psztxa/publ/jcont.pdf [JFP15],http://www.cs.nott.ac.uk/~psztxa/publ/ICont.pdf [LICS 09], which should have been cited btw.

Thorsten

P.S. The version of the journal paper on my web page is a bit behind – please refer to the published version
http://dx.doi.org/10.1017/S095679681500009X
If you can :-)

From: Martin Stone Davis <martin.stone.davis at gmail.com<mailto:martin.stone.davis at gmail.com>>
Date: Thursday, 7 January 2016 04:03
To: agda <agda at lists.chalmers.se<mailto:agda at lists.chalmers.se>>
Subject: [Agda] Generic Programming with Indexed Functors

{-
The fixed-point definition in section 2.3 of Generic Programming with Indexed Functors<https://www.researchgate.net/publication/228944016_Generic_Programming_with_Indexed_Functors> no longer type-checks in the latest version of Agda, which complains that μ is not strictly positive:

  data μ {I O : Set} (F : (I ⊎ O) ▶ O) (r : Indexed I) (o : O) : Set where
    ⟨_⟩ : ⟦ F ⟧ (r ∣ μ F r) o → μ F r o

I haven't had any luck finding a workaround. The code below is ripped from the article and reproduces the problem I'm having. Thanks in advance for any help solving this.
-}

module IndexedFunctor where
  open import Function using (_∘_)
  open import Relation.Binary.Core using (_≡_)

  open import Data.Empty using (⊥)
  open import Data.Unit using (⊤ ; tt)

  open import Data.Product using (_×_ ; ∃)
  open import Data.Sum using (_⊎_ ; inj₁ ; inj₂)

  Indexed : Set → Set₁
  Indexed I = I → Set

  _▷_ : Set → Set → Set₁
  I ▷ O = Indexed I → Indexed O

  record _≃_ (A B : Set) : Set where
    field
      from : A → B
      to   : B → A
      iso₁ : ∀ {x} → to (from x) ≡ x
      iso₂ : ∀ {x} → from (to x) ≡ x

  _∣_ : ∀ {A B} → Indexed A → Indexed B → Indexed (A ⊎ B)
  _∣_ ia _ (inj₁ x) = ia x
  _∣_ _ ib (inj₂ x) = ib x

  mutual
    data _▶_ : Set → Set → Set₁ where
      Z      : ∀ {I O} → I ▶ O
      U      : ∀ {I O} → I ▶ O
      I      : ∀ {I O} → I → I ▶ O
      !      : ∀ {I O} → O → I ▶ O
      _⊕_    : ∀ {I O}   → I ▶ O → I ▶ O → I ▶ O
      _⊗_    : ∀ {I O}   → I ▶ O → I ▶ O → I ▶ O
      _⊚_    : ∀ {I M O} → M ▶ O → I ▶ M → I ▶ O
      _↗_↘_  : ∀ {I I' O O'} → I' ▶ O' → (I' → I) → (O → O') → I ▶ O
      Fix    : ∀ {I O} → (I ⊎ O) ▶ O → I ▶ O
      ∑      : ∀ {I O} → {C : ⊥ ▶ ⊤} → (⟦ C ⟧ (λ _ → ⊤) tt → I ▶ O) → I ▶ O
      Iso    : ∀ {I O} → (C : I ▶ O) → (D : I ▷ O) → ((r : Indexed I) → (o : O) → D r o ≃ ⟦ C ⟧ r o) → I ▶ O

    data μ {I O : Set} (F : (I ⊎ O) ▶ O) (r : Indexed I) (o : O) : Set where
      ⟨_⟩ : ⟦ F ⟧ (r ∣ μ F r) o → μ F r o

    ⟦_⟧ : ∀ {I O} → I ▶ O → I ▷ O
    ⟦ Z         ⟧ r o = ⊥
    ⟦ U         ⟧ r o = ⊤
    ⟦ I i       ⟧ r o = r i
    ⟦ F ↗ f ↘ g ⟧ r o = ⟦ F ⟧ (r ∘ f) (g o)
    ⟦ F ⊕ G     ⟧ r o = ⟦ F ⟧ r o ⊎ ⟦ G ⟧ r o
    ⟦ F ⊗ G     ⟧ r o = ⟦ F ⟧ r o × ⟦ G ⟧ r o
    ⟦ F ⊚ G     ⟧ r o = ⟦ F ⟧ (⟦ G ⟧ r) o
    ⟦ Fix F     ⟧ r o = μ F r o
    ⟦ ! o'      ⟧ r o = o ≡ o'
    ⟦ ∑ f       ⟧ r o = ∃ (λ i → ⟦ f i ⟧ r o)
    ⟦ Iso C D e ⟧ r o = D r o

--
Martin Stone Davis

Postal/Residential:
1223 Ferry St
Apt 5
Eugene, OR 97401
Talk / Text / Voicemail: (310) 699-3578<tel:3106993578>
Electronic Mail: martin.stone.davis at gmail.com<mailto:martin.stone.davis at gmail.com>
Website: martinstonedavis.com<http://martinstonedavis.com/>




This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please send it back to me, and immediately delete it. 

Please do not use, copy or disclose the information contained in this
message or in any attachment.  Any views or opinions expressed by the
author of this email do not necessarily reflect the views of the
University of Nottingham.

This message has been checked for viruses but the contents of an
attachment may still contain software viruses which could damage your
computer system, you are advised to perform your own checks. Email
communications with the University of Nottingham may be monitored as
permitted by UK legislation.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20160107/55e33cea/attachment.html