自上而下与自下而上递归数据定义？
在阅读“编程语言要点”时，我遇到了整数列表的自上而下和自下而上的定义。虽然我理解这些定义的含义。但我无法理解自上而下与自下而上方法的细节。我如何看待一个定义并判断它是自上而下还是自下而上？
自上而下 方案列表是整数列表 当且仅当
它是空列表，或者
它是一对，其 car 是整数，其 cdr 是整数列表。
自下而上 List-of-Int 集合是最小的 满足以下两个属性的一组方案列表：
() Î List-of-Int，并且
if n Î Int and l Î List-of -Int，则 (n . l) ∈ List-of-Int。
While reading "Essentials of Programming Languages" I came across top down and bottom up definitions for list of integers.While I understand what these definitions say. But I am not able to understand fine details of top down vs. bottom up approach. How do I look at a definition and say weather it is top down or bottom up?
top-down
A Scheme list is a list of integers
if and only if either
it is the empty list, or
it is a pair whose car is an integer and whose cdr is a list of integers.
bottom-up
The set List-of-Int is the smallest
set of Scheme lists satisfying the following two properties:
() ∈ List-of-Int, and
if n ∈ Int and l ∈ List-of-Int, then (n . l) ∈ List-of-Int.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这两个概念与归纳和递归的概念相关。这两个概念都是描述无限大的对象族的方法，尽管它们的方法不同。
当您自下而上定义某事物时，您就是归纳地定义它。这个想法是，您从一组固定元素和一种将这些元素组合到新元素的方法开始。在上面的自下而上定义中，最初所有整数列表集合中的唯一元素是空列表。您还有一条规则，允许您在整数列表集中获取一个列表，并通过在前面添加一个整数将其增大一步。
当您自上而下定义某些内容时，您就是递归地定义它。这个想法是，您从一些非常大的对象族开始 - 在这种情况下，每个可能的列表 - 然后只描述那些仅由整数组成的列表。通常，共归纳定义的元素是通过获取现有对象并排除不匹配的对象来定义的。例如，在整数列表的示例中，您可以通过获取您想要的任何列表来定义某物是否是整数列表，然后验证如果您不断地分解它，最终会在某些对象处触底。你知道的是整数列表（在这种情况下，只是空列表）。
这两种形式实际上是等效的，但它们有不同的用途。归纳法尝试构建整个有效对象集，然后定义与描述匹配的所有对象。递归最初不定义任何内容，但随后通过将其拆分并验证来检查您拥有的任何对象是否符合某些条件。由于两者在数学上定义的神奇方式，任何归纳定义都可以变成递归定义，反之亦然（假设您正在谈论的所有对象都是有限的）。
编辑：如果您真的想享受一次有趣的旅程，您可能需要查看共归纳和核心递归。它们是归纳和递归的数学对偶，并提供了一种完全不同的思考如何定义数据结构的方式。特别是，它们允许无限大的数据结构，而这些数据结构通常无法归纳定义。有趣的是，共归纳、核心递归、归纳和递归之间在固定点。您可以将数据结构的归纳定义视为满足某些属性的最小集合，而共归纳定义是具有该属性的最大集合。真的很酷！
These two concepts are related to the notion of induction and recursion. Both of these concepts are ways of describing infinitely large families of objects, though they differ in their approach.
When you're defining something bottom-up, you are defining it inductively. The idea is that you start out with a set of fixed elements and a way of combining those elements into new elements. In the bottom-up definition above, initially the only element in the set of all list of integers is the empty list. You also have a rule which allows you to take a list in the set of lists of integers and grow it into something one step larger by prepending an integer.
When you're defining something top-down, you are defining it recursively. The idea is that you're beginning with some very large family of objects - in this case, every possible list - and then describing just those lists that are composed solely of integers. Usually elements defined coinductively are defined by taking existing objects and ruling out objects that don't match. For example, in the example of lists of integers, you define whether something is a list of integers by taking any list that you feel like and then verifying that if you keep breaking it down and down and down you eventually bottom out at some objects that you know are lists of integers (in this case, just the empty list).
The two forms are actually equivalent to one another, but they serve different purposes. Induction tries to build up the entire set of valid objects, then defines all objects matching the description. Recursion doesn't initially define anything, but then checks whether any object you have matches some criteria by piecing it apart and verifying it. Due to the magical way in which the two are mathematically defined, any inductive definition can be turned into a recursive definition and vice-versa (assuming that all objects you're talking about are finite).
EDIT: If you're really up for a fun ride, you might want to check out the related concepts of coinduction and corecursion. These are a mathematical dual to induction and recursion and provide an entirely different way of thinking about how to define a data structure. In particular, they allow for infinitely large data structures, which can't normally be defined inductively. Interestingly, there's a connection between coinduction, corecursion, induction, and recursion in terms of fixed points. You can think of the inductive definition of a data structure as the smallest set meeting some property, while the coinductive definition is the largest set with that property. It's really cool!