二叉树Haskell [英] Binary Trees Haskell

问题描述

所以我有这个数据结构:

So i have this data structure:

 class ordering a where

    order :: a-> Int

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

And i want to create a search tree, where every node is a list of elements, specified by their own order number( root is 1, root of left subtree is 2, root of right subtree is 3, and so on..). Every type of data that is inserted in the tree has an "order" number associated with it that only matters for "tree insertion purposes", and if it is equal to 1, it stays in the root, if it is two, it stays on the left side of the tree, and so on..

这是我的尝试:

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

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

What i've done, makes sense to me, but apparently is wrong, but honestly i have no idea why...

我是Haskell的新手，我一直在努力学习该语言，因此，我感谢你们提供的任何帮助！

I'm new to Haskell, and i've been struggling to learn the language, so i appreciate any kind of help from you guys!

推荐答案

让我们从功能实际开始.显然，您需要这样做:

Let's start from the function actually. Apparently you want this:

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

由于您的树上有要根据键插入的值，因此该 Tree 类型必须将两个都围起来:

since your tree carries values that are to be inserted according to keys, this Tree type must enclose both of them:

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

现在很容易实现 insert 函数.类型为 tree key val 的每棵树将能够携带类型为 key 的密钥和类型为 val 的值.为了在一棵树中容纳各种具体的值类型，您可以为其使用标记的联合类型:

now it's easy to implement the insert function. Each tree of a type Tree key val will be able to carry keys of type key and values of type val. To accommodate for various concrete value types in one tree you can use a tagged union type for it:

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

现在，一棵类型为树的树(例如 Tree Int Myval )将带有用Myval构造函数标记的值，并根据用户提供的 Int 键插入该值.

now a tree of type, e.g., Tree Int Myval will carry values tagged with Myval constructors, inserted according to the user supplied Int keys.

如果您是说每种数据类型都有其自己的密钥，则

If you mean that every data type has its own key,

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

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

then you won't use insert directly, but rather through an intermediary,

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

这当然是一种简单，简单的方法，也许这就是您的意思.

This is of course a simple, unsophisticated way to go about it, maybe this is what you meant.

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