sud*_*irc 2 recursion data-structures
在阅读EOPL时,我遇到了整数列表的自上而下和自下而上的定义.虽然我理解这些定义所说的内容.但我无法理解自上而下与自下而上方法的细节.我如何看待定义并说天气是自上而下或自下而上？
自上而下 方案列表是一个整数列表,当且仅当两者都有
它是空列表,或
它是一对汽车是整数,其cdr是整数列表.
自下而上 设置List-of-Int是满足以下两个属性的最小Scheme列表集:
()∈List-of-Int,和
如果n∈Int且l∈List-of-Int,则(n.l)∈List-of-Int.
这两个概念与归纳和递归的概念有关.这两个概念都是描述无限大的对象族的方法,尽管它们的方法不同.
当你自下而上地定义一些东西时,你就是在归纳地定义它.我们的想法是,您从一组固定元素开始,并将这些元素组合成新元素.在上面的自下而上的定义中,最初所有整数列表集中唯一的元素是空列表.您还有一个规则允许您在整数列表集中取一个列表,并通过预先加一个整数将其增大到更大的值.
当您自上而下定义某些内容时,您将以递归方式定义它.这个想法是你从一些非常大的对象族开始 - 在这种情况下,每个可能的列表 - 然后只描述那些仅由整数组成的列表.通常,通过获取现有对象并排除不匹配的对象来定义共同定义的元素.例如,在整数列表的示例中,您可以通过获取您感觉到的任何列表来定义某些内容是否为整数列表,然后验证如果您不断地将其分解,那么最终会在某些对象上找到底部.你知道的是整数列表(在这种情况下,只是空列表).
这两种形式实际上彼此相同,但它们用于不同的目的.归纳尝试构建整个有效对象集,然后定义与描述匹配的所有对象.递归最初不会定义任何内容,但随后通过将其分开并验证它来检查您所拥有的任何对象是否符合某些条件.由于两者在数学上被定义的神奇方式,任何归纳定义都可以变成递归定义,反之亦然(假设你所谈论的所有对象都是有限的).
编辑:如果你真的很开心,你可能想看看coinduction和corecursion的相关概念.这些是归纳和递归的数学对偶,并提供了一种完全不同的思考如何定义数据结构的方式.特别是,它们允许无限大的数据结构,这通常不能被感应地定义.有趣的是,就固定点而言,coinduction,corecursion,归纳和递归之间存在联系.您可以将数据结构的归纳定义视为满足某些属性的最小集合,而coinductive定义是具有该属性的最大集合.这真的很酷!