Haskell 2-3-4 树

Question

我们被要求在 Haskell 中创建一个 2-3-4 树，如编写数据类型、插入函数和显示函数。

我发现获取有关这种树的信息非常困难，即使使用我熟悉的语言(Java、C++)也是如此。

到目前为止我所拥有的 -

data Tree t = Empty 
    | Two t (Tree t)(Tree t) 
    | Three t t (Tree t)(Tree t)(Tree t) 
    | Four t t t (Tree t)(Tree t)(Tree t)(Tree t) deriving (Eq, Ord, Show)


leaf2 a = Two a Empty Empty
leaf3 a b = Three a b Empty Empty Empty
leaf4 a b c = Four a b c Empty Empty Empty Empty

addNode::(Ord t) => t ->  Tree t -> Tree t
addNode t Empty = leaf2 t
addNode x (Two t left right)
    | x < t = Two t (addNode x left) right
    | otherwise = Two t left (addNode x right)

这可以编译，但我不确定它是否正确，但不确定如何开始将插入写入三节点或四节点。

作业还指出，显示函数的“导出显示”是不够的，它应该以图表中通常看到的格式打印出树。再次不确定如何处理这个问题。

任何帮助或指导表示赞赏。

Answer 1

我对 2-3-4 树一无所知，但对于三节点，你可以从这样的东西开始:

addNode t (Three x y left mid right)
  | cond1 = expr1
  | cond2 = expr2
  (etc)

cond1、cond2、expr1 和 expr2 到底是什么，取决于什么是 2-3-4 树。

对于 show 方法，总体轮廓如下:

instance (Show t) => Show (Tree t) where
  show Empty = ...
  show (Two x l r) = ...show x...show l...show r...
  show (Three x y l m r) = ...
  show (Four x y z l m n r) = ...

实现取决于您希望它的外观，但对于非空情况，您可能会在显示的树的所有组件上调用 show。如果您想缩进树的嵌套部分，那么也许您应该创建一个单独的方法:

instance (Show t) => Show (Tree t) where
  show = showTree 0

showTree :: Show t => Int -> Tree t -> String
showTree n = indent . go
  where indent = (replicate n ' ' ++)
        go Empty = "Empty"
        go (Two x l r) = (...show x...showTree (n+1) l...showTree (n+1) r...)
        (etc)