[Agda] Termination checking failure

Ivan Tomac tomac at pobox.com
Mon Nov 23 00:12:52 CET 2009


Nils Anders Danielsson wrote:
>
> The following code works:
>
>  map : ∀ {A B} → (A → B) → Stream A → Stream B
>  map f (cons x xs) = cons (f x) (♯ map f (♭ xs))
>
>  sequence : ∀ {A} → Stream (Id A) → Id (Stream A)
>  sequence = id ∘ map unId
>
Yes, that does work for that particular case. I should have been a bit 
more clear though. The code here is simplified version of the problem I 
ran into before where the above wouldn't work. What happens in a more 
general case for example with an applicative functor instead of Id:

sequence : ∀ {F a} → RawApplicative F → Stream (F a) → F (Stream a)
sequence A (cons f fs) =
    cons <$> f ⊛ ((λ as → ♯ as) <$> sequence A (♭ fs))
    where
    open RawApplicative A
>> And why is the termination checker failing in first place?
>
> Because the corecursive call is not guarded by constructors.
>
>> I would appreciate any pointers to papers, articles or books.
>
> You may want to have a look at "Mixing Induction and Coinduction":
>
>  http://www.cs.nott.ac.uk/~nad/publications/danielsson-altenkirch-mixing.html 
>
>
Thanks for the link. I'll have a read through it.


More information about the Agda mailing list