如何产生一个无限的二叉树？

Question

我被要求为以下二进制树实现一个功能：

data BinaryTree a = Nil | BNode a (BinaryTree a) (BinaryTree a) 

我需要实现的功能应该产生一个完整的，对称的，无限的二进制树a，并且具有以下特征：

infTree :: a -> BinaryTree a

我该如何实施？

Answer 1

您可以创建一个循环引用，其中两个子节点均为父节点。

infTree :: a -> BinaryTree a
infTree x = tree
  where
    tree = BNode x tree tree

这与repeat函数的实现方式相同：

repeat :: a -> [a]
repeat x = xs where xs = x : xs