CODEWITHSUNDEEP
haskelltree
user2878641
user2878641

Reputation:

Binary Trees Haskell

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!

Upvotes: 1

Views: 1996

Answers (2)

Will Ness
Will Ness

Reputation: 71065

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.

Upvotes: 1

Robin Green
Robin Green

Reputation: 33033

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.

Upvotes: 1

Related Questions