如何检查生成无限列表的函数的实现？

Question

Write a function that takes the function f and the number n and returns the list [f n, f (n + 1), f (n + 2), f (n + 3), f (n + 4) ... ].

这是我的解决方案：

func f n = f n : func f (n+1)

但我不确定它是否正确。如何检查我的实施情况？

Answer 1

你可以给出一个共归纳证明。共归纳推理类似于归纳推理，但它允许 "infinite" 结构。这是对数据流和无限列表等事物进行推理的自然选择。

你想要 func 拥有的 属性 类似于

∀ f : Int -> a, ∀ n : Int, ∀ i : Int, (i >= 0 ⟹ (func f n) !! i == f (n + i))

通过共同归纳法证明某事类似于归纳法：您将其假设为对所有子结构的共同归纳假设，然后对上层结构进行证明。由于func只有一个定义，所以只有这样的举证义务

这意味着，如果你能证明

∀ f : Int -> a, ∀ n : Int, ∀ i : Int, (i ≥ 0 ⟹ (func f n) !! i == f (n + i))
⟹
∀ f : Int -> a, ∀ n : Int, ∀ i : Int, (i ≥ 0 ⟹ (f n : (func f (n + 1))) !! i == f (n + i))

那你就证明你的函数定义是正确的。

因为你实际上可以证明上面的说法，你的函数定义是正确的。