Бинарные деревья Haskell

Question

Таким образом у меня есть эта структура данных:

class ordering a where 

    order :: a-> Int 

И я хочу, чтобы создать дерево поиска, где каждый узел представляет собой список элементов, определяется их собственным номером заказа (корень 1, корень левого поддерева равно 2, корень правого поддерева равен 3 и т. д.). Каждый тип данных, вставленный в дерево, имеет связанный с ним номер «порядка», который имеет значение только для «целей вставки дерева», и если он равен 1, он остается в корне, если он равен двум, он остается на левой стороне дерева, и так далее ..

Вот моя попытка это:

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

Что я сделал, имеет смысл для меня, но, видимо, не так, но если честно я есть не знаю, почему ...

Я новичок в Haskell, и я изо всех сил пытаюсь выучить язык, поэтому я ценю любую помощь от вас, ребята!

Answer 1

ordering, который вы определили, является классом типа, а не структурой данных. order - это операция, а не тип. Помещение операции order в структуру данных Tree бессмысленно.

Вы также не показали нам никакого кода для фактической вставки данных, поэтому я не уверен, как это должно работать.

Answer 2

Начнем с функции на самом деле. Видимо, вы хотите:

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 сможет нести ключи типа 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 

Это, конечно, простой, неискушенный способ обойти это, возможно, это то, что вы имели в виду.