二进制搜索树中的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.

如果要在计算中命名步骤,则必须为每个步骤命名,因为您无法修改现有绑定.