2

我遇到了关于相互递归的这些讨论，最初是在let表达​​式的上下文中，即 alet允许绑定相互引用而不考虑顺序。（见这里。）然后我在维基百科上看到了这个讨论。这以 SML 中的数据类型的形式给出了一个示例

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

我记得，这and是相互递归关系所必需的。它导致了 Haskell 中的这个版本

data Tree a = Empty
            | Node (a, Forest a)
data Forest a = Nil
              | Cons (Tree a) (Forest a)

我对此有一个直观的把握，但是语法很混乱，例如，SMLtree有

... Node of 'a * 'a forest

这是一个元组，对吗？是的，我想我在 Haskell 翻译中看到了一个元组

... Node (a, Forest a)

直观地说，这与树节点可能具有整个Forest（一个或多个）子树的分支功能相同，对吗？但是，HaskellForest数据类型基本上将一个新元素包含在一个（元素）列表Tree的头部，而 SML 版本似乎使用了一个ForestTree*

... Cons of 'a tree * 'a forest

这意味着创建一个元组？通常，令人困惑的Tree定义，即 aTree可以在其Forest下方有 a。然后就是树的这个定义

data Tree = Leaf | Node Int Tree Tree

其中子树的问题仅限于两个子树。是使用Forest允许一个或多个子节点的唯一方法吗？直观地说，树下没有森林，而是森林的成员。一个问题是，是否可以直接使用常规列表 consing？

data Forest a = Nil | ForestCons (Tree a) [(Tree a)] deriving (Show)
4

1 回答 1

6

Node (a, Forest a)，尽管是完全合法的 Haskell，但它是单调的。定义的常规形式是

data Tree' a = Empty'
             | Node' a (Forest a)

这包含与您相同的信息Tree，但不是将Node构造函数的字段打包在一个元组中，而是将它们都作为字段提供。不同之处在于，在实际处理该类型的值时，您会编写Node' h t而不是Node' (h,t).

同样，您Forest的等价于不推荐的形式

data Forest' a = Nil'
               | Cons' (Tree a, Forest a)
于 2021-01-31T22:44:36.443 回答