标签: induction

所以我最近一直在阅读有关coinduction的内容,现在我想知道:Haskell列出了归纳还是共同？我也听说Haskell没有区分这两者,但如果是这样的话,他们怎么这样做呢？

列表是归纳定义的data [a] = [] | a : [a],但可以共同使用,ones = a:ones.我们可以创建无限列表.然而,我们可以创建有限列表.他们是哪一个？

相关的是Idris,其中类型List a严格地是归纳类型,因此仅是有限列表.它的定义类似于Haskell中的方式.然而,Stream a是一种共同类型,建模无限列表.它被定义为(或者更确切地说,定义相当于)codata Stream a = a :: (Stream a).创建无限List或有限Stream是不可能的.但是,当我写出定义时

codata HList : Type -> Type where
    Nil : HList a
    Cons : a -> HList a -> HList a

我得到了我对Haskell列表的期望,即我可以创建有限和无限结构.

所以让我把它们归结为几个核心问题:

1. Haskell不区分归纳和共感类型吗？如果是这样,那是什么形式化？如果没有,那么哪个是[a]？

2. HList是coinductive吗？如果是这样,coinductive类型如何包含有限值？

3. 如果我们定义data HList' a = L (List a) | R (Stream a)怎么办？会考虑什么和/或仅对它有用HList？

我正在努力学习如何正确地证明程序的正确性.我从头开始,在第一步/主题介绍中挂断了.

在本文关于全函数规划的文章中,给出了斐波那契函数的两个定义.传统的一个:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
--fib (n+2) = fib (n+1) + fib (n+2) --The definition as given in the paper 
                                    --It seems incorrect to me. Typo?

和我以前从未见过的尾递归版本:

fib' n = f n 0 1
f 0 a b = a
f n a b = f (n-1) b (a+b)

该论文随后声称,通过归纳证明两个函数对所有正整数n都返回相同的结果是"直截了当"的.这是我第一次想到分析这样的程序.认为你可以证明两个程序是等价的,这是非常有趣的,所以我立即尝试通过归纳自己来做这个证明.要么我的数学技能都生锈了,要么任务实际上并不那么简单.

我证明了n = 1

fib' 1 = f 1 0 1
       = f 0 1 1 …

> {-# LANGUAGE DeriveFunctor, Rank2Types, ExistentialQuantification #-}

任何归纳类型都是这样定义的

> newtype Ind f = Ind {flipinduct :: forall r. (f r -> r) -> r}
> induction = flip flipinduct

induction有类型(f a -> a) -> Ind f -> a.这种称为共同诱导的概念是双重的.

> data CoInd f = forall r. Coinduction (r -> f r) r
> coinduction = Coinduction

coinduction有类型(a -> f a) -> a -> CoInd f.注意如何induction和coinduction是双重的.作为归纳和coinductive数据类型的示例,请查看此仿函数.

> data StringF rec = Nil …

Agda中有哪些大小的类型？我试图阅读有关MiniAgda的文章,但由于以下几点未能继续:

1. 为什么数据类型超出其大小？据我所知,大小是感应树的深度.
2. 为什么数据类型在其大小上是协变的,即i <= j - > T_i <= T_j？
3. 这些>和#模式意味着什么？

我真的不明白如何通过感应在伪代码上使用证明.它似乎与在数学方程上使用它的方式不同.

我正在尝试计算数组中可被k整除的整数数.

Algorithm: divisibleByK (a, k)
Input: array a of n size, number to be divisible by k
Output: number of numbers divisible by k

int count = 0;
for i <- 0 to n do
    if (check(a[i],k) = true)
        count = count + 1
return count;


Algorithm: Check (a[i], k)
Input: specific number in array a,  number to be divisible by k
Output: boolean of true or false

if(a[i] % k == 0) then
    return true;
else    
    return false; …

我试图看看是否可以evenb n = true <-> exists k, n = double k从https://softwarefoundations.cis.upenn.edu/lf-current/Logic.html证明,而不涉及奇数.我尝试过以下内容:

Theorem evenb_double_k : forall n,
  evenb n = true -> exists k, n = double k.
Proof.
  intros n H. induction n as [|n' IHn'].
  - exists 0. reflexivity.
  - (* stuck *)

但显然感应一次只能起作用一个自然数,exists k : nat, S n' = double k显然不可证明.

n' : nat
H : evenb (S n') = true
IHn' : evenb n' = true -> exists k : nat, …

递归和归纳证明之间的关系是什么？

比方说fn(n),

递归就是fn(n)调用本身直到相遇base condition;

归纳是在base condition遇到的时候,试着证明(base case + 1)也是正确的.

似乎递归和归纳在不同的方向.从一开始n到base case,另一种是从开始base case到infinite.

有人可以详细解释这个想法吗？

以下是结构感应的定义吗？

foldr f a (xs::ys) = foldr f (foldr f a ys) xs

有人能给我一个Haskell结构感应的例子吗？

我不能让Agda的终止检查器接受使用结构感应定义的函数.

我创建了以下内容作为我认为最简单的例子来展示这个问题.以下定义size被拒绝,即使它总是在严格较小的组件上进行递归.

module Tree where

open import Data.Nat
open import Data.List

data Tree : Set where
  leaf : Tree
  branch : (ts : List Tree) ? Tree

size : Tree ? ?
size leaf = 1
size (branch ts) = suc (sum (map size ts))

这个问题有通用的解决方案吗？我是否需要Recursor为我的数据类型创建一个？如果是的话,我该怎么做？(我想如果有一个如何定义Recursorfor 的示例List A,那会给我足够的提示吗？)

你可能听说过经典的棋盘覆盖拼图.如何使用L形瓷砖覆盖缺少一个角落方格的棋盘？

正如"Python语言中的Python算法掌握基本算法"一书中所解释的那样,有一种递归方法.

我们的想法是将电路板分成4个较小的方块,然后将L形瓷砖放入较大电路板的中心,有效地创建4个较小的方块,其中一个瓷砖丢失并继续通过递归.

从概念上讲,它很容易理解,但我发现很难想到一个实现.这是一个实施解决方案 -

    def cover(board, lab=1, top=0, left=0, side=None):
        if side is None: side = len(board)

        # Side length 
        s = side // 2

        # Offsets for outer/inner squares of subboards
        offsets = ((0, -1), (side-1, 0))

        for dy_outer, dy_inner in offsets:
            for dx_outer, dx_inner in offsets:
            # If the outer corner is not set...
                if not board[top+dy_outer][left+dx_outer]:
                # ... label the inner corner: 
                    board[top+s+dy_inner][left+s+dx_inner] = lab


        # Next label: 
        lab += 1
        if s > 1:
            for …