Binary Trees Haskell

1
votes

So i have this data structure:

 class ordering a where

    order :: a-> Int

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..

Here's my attempt at this:

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...

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

2
haskelltree
possible duplicate of Specifying class constraints in value constructors - Robin Green
I think the problem is that you're mixing up the meaning of types, of data, of type classes, and of classes in OO languages (which is perfectly usual for beginner Haskellers). Read some book(s) on Haskell, that's probably going to be the most effective fix to your issue. - leftaroundabout
1) class names must be written with a capital letter. 2) Ordering is a busy name in Prelude, try to use another name for class 3) data and class are connected through instance - viorior

2 Answers

1
votes

The ordering that you have defined is a type class, not a data structure. order is an operation, not a type. Putting the order operation in the Tree data structure makes no sense.

You also haven't shown us any code to actually insert data, so I'm unsure how this is supposed to work.

1
votes

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

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

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)

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 | ...

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
....

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.