二叉搜索树 Haskell

Question

我在 Haskel 中有一个二叉搜索树的插入函数。我的插入函数前两行看起来像这样

insert :: (Ord a) => BST a -> a -> BST a
insert Nil x = Node x Nil Nil

我知道该功能有效，我已经在单个数字上对其进行了测试。但现在我正在尝试将插入应用于列表。我试过这段代码

let mBST = foldr insert Nil [1,2,7,9,3,5]

我收到以下错误

Occurs check: cannot construct the infinite type: a0 = BST a0
Expected type: BST (BST a0) -> BST a0 -> BST a0
Actual type: BST (BST a0) -> BST a0 -> BST (BST a0)
In the first argument of `foldr', namely `insert'
In the expression: foldr insert Nil [1, 2, 7, 9, ....]

我在 BST a -> a -> BST a 中有错误，但我不确定如何修复它。

Answer 1

foldr 的类型为 (a -> b -> b) -> b -> [a] -> b，这意味着它需要一个类型为 a -> b -> b 的函数作为它的第一个参数。在您的特定示例中，它转换为 Integer -> BST Integer -> BST Integer，这与插入的类型不同。

最简单的解决方案是翻转插入函数：

let mBST = foldr (flip insert) ...

Answer 2

原因是 foldr f init lst 传递了 f 列表的一个元素和折叠列表其余部分的结果 按此顺序 .你可以写

insert :: (Ord a) => a -> BST a -> BST a
insert x Nil = Node x Nil Nil

（这会更地道）或写成 foldr (flip insert) Nil.

您可能很快就会了解到，在这种情况下使用严格的左折而不是右折效率更高。使用您的实现，这是 foldl' insert Nil。使用我的（更惯用的）一个，这是 foldl' (flip insert) Nil.

二叉搜索树 Haskell

Binary Search Tree Haskell

haskell

functional-programming

binary-search-tree