如何产生无限二叉树？

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

How to produce an infinite binary tree?