[Agda] Coinductive families
Nicolas Pouillard
nicolas.pouillard at gmail.com
Wed Oct 6 22:41:18 CEST 2010
On Wed, 6 Oct 2010 11:03:08 +0200, Andreas Abel <andreas.abel at ifi.lmu.de> wrote:
>
> On Oct 5, 2010, at 5:29 PM, Nils Anders Danielsson wrote:
>
> > On 2010-10-05 14:14, Andreas Abel wrote:
> >> Currently records are hybrids, because we have record patterns. If
> >> all
> >> record patterns could be translated away, we could understand
> >> records in
> >> terms of &. But currently we allow record patterns that cannot be
> >> translated away, such as where record patterns are mixed with data
> >> constructor patterns.
> >
> > I'm fairly certain that we can translate away these patterns, but
> > there
> > is no immediate need to do so, because the translation would be
> > observationally indistinguishable from what we generate now (modulo
> > any
> > bugs).
>
>
> How would you translate away the patterns in Thorsten's example?
>
> record List (A : Set) : Set where
> constructor list
> field
> isCons : Bool
> hd : T isCons → A
> tl : T isCons → List A
>
> append : ∀ {A} → List A → List A → List A
> append (list true h t) bs = list true h (λ _ → append (t _) bs)
> append (list false _ _) bs = bs
[...]
> Anyway, for now the termination checker rejects all versions of append
> given here, shout if you disagree!
One may consider this as cheating but by boxing the recursive occurence
of (List A) one can please the termination checker:
data Box (A : Set) : Set where
box : A → Box A
record List (A : Set) : Set where
constructor list
field
isCons : Bool
hd : T isCons → A
tl : T isCons → Box (List A)
open List
append : ∀ {A} → List A → List A → List A
append l bs with isCons l | hd l | tl l
... | false | _ | _ = bs
... | true | h | t with t _
... | box t' = list true h (λ _ → box (append t' bs))
By replacing Box by ∞ one get CoList.
Best regards,
--
Nicolas Pouillard
http://nicolaspouillard.fr
More information about the Agda
mailing list