二叉搜索树中的 GHCI 无限循环

Question

我在 Haskell

中实现了二叉搜索树

data BST = Nil | Node (BST) Int (BST) deriving Show

emptyTree :: BST
emptyTree = Nil

isEmptyTree :: BST -> Bool
isEmptyTree Nil = True
isEmptyTree _ = False

leftChild :: BST -> BST
leftChild Nil = Nil
leftChild (Node l k r) = l

rightChild :: BST -> BST
rightChild Nil = Nil
rightChild (Node l k r) = r

root :: BST -> Int
root Nil = error "Empty Tree"
root (Node l k r) = k

insert_r :: BST -> Int -> BST
insert_r Nil k = Node Nil k Nil
insert_r n@(Node l x r) k
    | k < x = Node (insert_r l k) x r
    | k > x = Node l x (insert_r r k)
    | otherwise = n

我正在尝试测试它向树中插入一些值。这是一个示例测试序列：

t = Nil
t = insert_r t 2
t = insert_r t 3
t = insert_r t 1

当我在 GHCi 中尝试运行时，在检查 "t" 值的那一刻，我得到了一个无限循环。但是，如果我将每次插入的结果分配给一个新变量，如下所示：

v = insert_r t 2
u = insert_r v 1

检查 "u" 的值非常有效。这与 Haskell 的惰性评估有关，还是我在 BST 实现中编码有误？

Answer 1

关于你的树的所有这些东西与这里的根本原因完全无关，即 haskell 的 = 不是赋值运算符，而是一个定义。重要的是，它允许递归，允许一个值引用自身，例如 xs = 1 : xs 产生无限的 1 列表。

因此，您不是通过三个插入逐步构建一棵树，而是定义三棵不相关的树，每棵树都是自引用的，因此是循环的。如果你简单地写 x = x.

你会遇到同样的问题

如果你想为计算中的步骤命名，你必须给每个步骤一个不同的名字，因为你不能修改现有的绑定。

二叉搜索树中的 GHCI 无限循环

GHCI infinite loop in Binary Search Tree

haskell

ghci