[Agda] Coinductive families
Andreas Abel
andreas.abel at ifi.lmu.de
Thu Oct 7 23:19:01 CEST 2010
Ok, this works, but anyway, I think inductive records are doomed.
Eta-expansion does not terminate for inductive record like List so I
guess there will be soon a check to rule them out.
On Oct 6, 2010, at 10:41 PM, Nicolas Pouillard wrote:
> 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
>
Andreas Abel <>< Du bist der geliebte Mensch.
Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY
andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/
More information about the Agda
mailing list