Haskell 2-3-4树 [英] Haskell 2-3-4 Tree

问题描述

我们被要求在Haskell中创建2-3-4树，就像编写数据类型，插入函数和显示函数一样.

We've been asked to create a 2-3-4 tree in Haskell, as in write the data type, the insert function, and a display function.

我发现很难获得关于这种树的信息，即使使用我熟悉的语言(Java，C ++)也是如此.

I'm finding it very difficult to get information on this kind of tree, even in a language I'm comfortable with (Java, C++).

我到目前为止所拥有的-

What I have so far -

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)

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

This compiles but I'm not sure if it's correct, but not sure how to start writing the insert into a three node or four node.

该作业还说显示功能的派生显示"还不够，它应该以通常在图中看到的格式打印出树.同样，不确定该如何进行.

The assignment also says that "deriving show" for the display function is not enough, that it should print out the tree in the format normally seen in diagrams. Again, unsure on the way to go with this.

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

Any help or direction appreciated.

推荐答案

我对2-3-4树一无所知，但对于三"节点，您将从以下内容开始:

I know nothing about 2-3-4 trees, but for the Three node, you would start with something like this:

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

cond1，cond2，expr1和expr2的确切含义取决于2-3-4树的定义.

What cond1, cond2, expr1, and expr2 are, exactly, is dependent on the definition of what a 2-3-4 tree is.

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

As for a show method, the general outline would be this:

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.如果要缩进树的嵌套部分，则也许应该创建一个单独的方法:

The implementation depends on how you want it to look, but for the non-Empty cases, you will probably invoke show on all of the components of the tree being shown. If you want to indent the nested parts of the tree, then perhaps you should create a separate method:

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)

这篇关于Haskell 2-3-4树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！