1

我有一个典型的二叉搜索树数据类型：

data Tree a
  = Empty
  | Branch a (Tree a) (Tree a) deriving Show

和变态

foldt :: b -> (a -> b -> b -> b) -> Tree a -> b
foldt empty _ Empty = empty
foldt empty branch (Branch a l r) = branch a (foldt empty branch l) (foldt empty branch r)

我尝试使用定义一个插入函数foldt并得到了一些有趣的结果：

insert :: (Ord a) => a -> Tree a -> Tree a
insert x = foldt (single x) insertb
  where insertb a left right
          | x == a = Branch x left right
          | x < a = Branch a (insert x left) right
          | x > a = Branch a left (insert x right)

ghci> mytree = insert 2 (Branch 3 Empty Empty)  
ghci> mytree
Branch 3 (Branch 2 (Branch 2 Empty Empty) (Branch 2 Empty Empty)) (Branch 2 Empty Empty)
ghci>

当然，传统的插入方法的行为符合预期：

insert' :: (Ord a) => a -> Tree a -> Tree a
insert' x Empty = single x
insert' x (Branch a left right)
  | x == a = Branch x left right
  | x < a = Branch a (insert' x left) right
  | x > a = Branch a left (insert' x right)

ghci> mytree2 = insert' 2 (Branch 3 Empty Empty)
ghci> mytree2
Branch 3 (Branch 2 Empty Empty) Empty
ghci>

有没有办法定义insert，foldt或者我在这里吠错了树（ha）？

4

2 回答 2

4

让我们定义一个函数

insertMaybe :: Ord a => Tree a -> Maybe a -> Tree a

这个函数需要一棵树，也可能是一个元素。在这种Just情况下，元素被插入。在这种Nothing情况下，树原样返回。那么我们可以定义

insert a t = insertMaybe t (Just a)

现在：

insertMaybe :: Ord a => Tree a -> Maybe a -> Tree a
insertMaybe = foldt leaf branch
  where
    leaf (Just new) = ?
    leaf Nothing = ?

    branch a l r Nothing = ?
    branch a l r (Just new)
      | ... = ?
      ...

或者：

data Ins a = Ins
  { inserted :: Tree a
  , notInserted :: Tree a }

insert a t = inserted (insertAndNot a t)

-- Return the tree with the 
-- element inserted, and also unchanged.
insertAndNot :: Ord a => a -> Tree a -> Ins a
insertAndNot new = foldt leaf branch
  where
    leaf = Ins ? ?
    branch a ~(Ins li lni) ~(Ins ri rni)
      | ... = Ins ? ?
      ...

异质性

上述解决方案有一个主要的效率问题：它们完全重建树结构只是为了插入一个元素。正如 amalloy 所建议的，我们可以通过将foldt(a catamorphism)替换为 (a paramorphism) 来解决这个问题parat。parat使函数可以branch访问递归修改的子树和未修改的子树。

parat :: b -> (a -> (Tree a, b) -> (Tree a, b) -> b) -> Tree a -> b
parat leaf _branch Empty = leaf
parat leaf branch (Branch a l r) =
  branch a
         (l, parat leaf branch l)
         (r, parat leaf branch r)

方便的是，insert使用parat. 你能看出怎么做吗？这最终成为我建议使用的“替代”方式的有效版本foldt。

于 2021-04-15T22:03:17.417 回答
3

感谢 dfeuer 和 amalloy 提供的关于超同态的技巧，TIL！

给定 Tree 数据类型的超态：

parat :: b -> (a -> (Tree a, b) -> (Tree a, b) -> b) -> Tree a -> b
parat empty _ Empty = empty
parat empty branch (Branch a l r) =
  branch a
         (l, parat leaf branch l)
         (r, parat leaf branch r)

我们可以写一个插入函数：

insert :: Ord a => a -> Tree a -> Tree a
insert x = parat (single x) branch
  where branch a (l, l') (r, r')
          | x == a = Branch x l r
          | x < a = Branch a l' r
          | x > a = Branch a l r'

ghci> mytree = insert 2 (Branch 3 Empty Empty)
ghci> mytree
Branch 3 (Branch 2 Empty Empty) Empty
ghci>

测试一棵更大的树...

import Data.Function

mytree :: Tree Integer
mytree = (Branch 3 Empty Empty) & insert 2 & insert 4 & insert 6 & insert 5 & insert 10

inorder :: Tree a -> [a]
inorder = foldt [] (\a l r -> l ++ [a] ++ r)

ghci> mytree
Branch 3 (Branch 2 Empty Empty) (Branch 4 Empty (Branch 6 (Branch 5 Empty Empty) (Branch 10 Empty Empty)))
ghci> inorder mytree
[2,3,4,5,6,10]
ghci>
于 2021-04-16T01:28:29.237 回答