[Agda] Defining the Delay monad as a HIT in cubical agda
Nicolai Kraus
nicolai.kraus at gmail.com
Tue Apr 2 15:14:38 CEST 2019
Hi Jesper,
I find this construction very interesting since it's the first "cubical
higher co-inductive type" that I've seen! Unfortunately, I don't know
how these "CHCIT's" behave in Agda.
If I had to guess, I would expect that you *cannot* distinguish now and
never, which would mean that your construction doesn't give you what you
wanted. The difference to the quotiented delay monad (or, for what it's
worth, the QIT/QIIT partiality monad) is that your construction inserts
the equations "coinductively" (usually, only the later-steps are
coinductive).
Thus, my guess is that Delay(Unit) could be contractible. One could try
to prove that every element is equal to 'now'.
Cheers,
Nicolai
On 29/03/19 18:40, Jesper Cockx wrote:
> Hi all,
>
> As an experiment with cubical agda, I was trying to define a
> quotiented version of the Delay monad as a higher inductive type. I'm
> using this definition:
>
> data Delay (A : Set ℓ) : Set ℓ
>
> record Delay′ (A : Set ℓ) : Set ℓ where
> coinductive
> field
> force : Delay A
>
> open Delay′ public
>
> data Delay A where
> now : A → Delay A
> later : Delay′ A → Delay A
> step : (x : Delay′ A) → later x ≡ x .force
>
> I managed to implement some basic functions on it but I got stuck on
> trying to prove the looping computation 'never' does not in fact
> evaluate to any value. My code is available here:
> https://github.com/jespercockx/cubical/commit/f1647a90c1b27aadd5da748f08e23630221cc3d9
> I looked at the problem together with Christian Sattler and we are not
> even sure it is actually provable. Does anyone have an idea how to
> proceed? Or has someone already experimented with coinductive types in
> cubical and encountered similar problems? (I looked at the paper
> "Partiality revisited" by Thorsten, Nisse and Nicolai but they use a
> very different definition of the partiality monad.)
>
> Cheers,
> Jesper
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20190402/b6946291/attachment.html>
More information about the Agda
mailing list