[Agda] productivity of fibonacci stream
Noam Zeilberger
noam.zeilberger at gmail.com
Tue Mar 14 19:59:37 CET 2017
Hello Agda List,
This might be a FAQ, but I was wondering why the canonical
implementation of the stream of Fibonacci numbers using copatterns
does not pass Agda's termination checker? By "canonical
implementation" (cf. section 2.3 of
http://www2.tcs.ifi.lmu.de/~abel/popl13.pdf), I mean the following:
====
open import Agda.Builtin.Nat public
record Stream (A : Set) : Set where
coinductive
field
hd : A
tl : Stream A
open Stream
zipWith : {A B C : Set} → (A → B → C) → Stream A → Stream B → Stream C
hd (zipWith f xs ys) = f (hd xs) (hd ys)
tl (zipWith f xs ys) = zipWith f (tl xs) (tl ys)
fib : Stream Nat
hd fib = 0
hd (tl fib) = 1
tl (tl fib) = zipWith _+_ fib (tl fib)
====
which yields the following warning:
====
Termination checking failed for the following functions:
fib
Problematic calls:
fib
(at .../Fib.agda:19,27-30)
tl fib
(at .../Fib.agda:19,35-38)
====
Any hints as to why Agda is complaining?
Noam
More information about the Agda
mailing list