haskell - 二叉树 Haskell

Question

所以我有这个数据结构：

 class ordering a where

    order :: a-> Int

我想创建一个搜索树，其中每个节点都是一个元素列表，由它们自己的顺序号指定（根为 1，左子树的根为 2，右子树的根为 3，依此类推..）。插入到树中的每种类型的数据都有一个与之关联的“顺序”编号，该编号仅对“树插入目的”有意义，如果等于 1，则保留在根中，如果为 2，则保留在树的左侧，等等..

这是我的尝试：

data Tree a = EmptyTree
        | Node a order a (Tree [a]) (Tree [a]) deriving (Show, Read, Eq)

我所做的对我来说很有意义，但显然是错误的，但老实说我不知道为什么......

我是 Haskell 的新手，我一直在努力学习这门语言，所以我感谢你们的任何帮助！

score 1 · Accepted Answer

让我们从实际的功能开始。显然你想要这个：

insert :: Ord key => (key,val) -> Tree key val -> Tree key val

由于您的树带有要根据键插入的值，因此这种Tree类型必须将它们都包含在内：

data Ord key => Tree key val = EmptyTree 
                             | Node key val (Tree key val) (Tree key val)

现在很容易实现该insert功能。每个类型的树Tree key val都可以携带 type 的键和 type 的key值val。为了适应一棵树中的各种具体值类型，您可以为其使用标记的联合类型：

data Myval = My_c1 | My_c2 | MyInt Int | MyInts [Int] | MyString String | ...

现在一个类型的树，例如，Tree Int Myval将携带用 Myval 构造函数标记的值，根据用户提供的Int键插入。

如果您的意思是每种数据类型都有自己的键，

ordkey :: Myval -> Int
ordkey My_c1 = 1
ordkey My_c2 = 2
ordkey (MyInt _) = 3
....

那么你不会insert直接使用，而是通过中介，

ordinsert val tree = insert (ordkey val,val) tree

这当然是一种简单、简单的方法，也许这就是你的意思。

score 1 · Accepted Answer

您定义的ordering是类型类，而不是数据结构。order是一种操作，而不是一种类型。将order操作放入Tree数据结构中是没有意义的。

您还没有向我们展示任何实际插入数据的代码，所以我不确定这应该如何工作。

2 回答 2