Сравнить деревья по высоте >= или > . Haskell

Question

Не получается сравнить деревья по высоте со знаками больше(>) и больше или равно(>=). Вот мой код. Просто зависает при команде tree1 >= tree2

    data Tree a = Node a [Tree a] deriving (Eq,Show)
       instance (Ord a) => Ord (Tree a) where
           Node a list1 >= Node b list2 = (list1 > list2) || (list1 == list2)
           (Node a list1) > (Node b list2) = (list1 > list2)

t0 = Node 15 []
t1 = Node 15 []
t2 = Node 120 [t0]
tree1 = Node 130 [t1,t2]

tt0 = Node 155 []
tt1 = Node 112 [t2]
tt2 = Node 128 [t0]
tree2 = Node 110 [tt1,tt2,tt0]

Answer 1

Реализация представителя класса типов Ord должна включать определения либо оператора <=, либо функции compare. У вас определены только >= и >, этого недостаточно.

ghci> :i Ord
type Ord :: * -> Constraint
class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  (>) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  max :: a -> a -> a
  min :: a -> a -> a
  {-# MINIMAL compare | (<=) #-}
        -- Defined in ‘GHC.Classes’

Также вы используете deriving Eq для реализации стандартного сравнения алгебраических типов данных. Т.е. оператор == у вас сравнивает деревья не только по высоте, но и по содержимому. Реализуйте Eq самостоятельно.

instance Eq (Tree a) where
  {- ... -}

После этого сможете убрать ограничение Ord a из реализации Ord (Tree a), оно лишнее для этой задачи

instance Ord (Tree a) where
  {- ... -}

В самом алгоритме у вас ошибка: вы сравниваете список поддеревьев стандартным для списка способом, т.е. больший или меньший список определяется по первому несовпадению элементов

ghci> [1, 2, 3] > [0, 100000, 200000]
True

Для сравнения высот поддеревьев такой подход не сработает.

БЛОГ НА HUSL

Сравнить деревья по высоте >= или > . Haskell

Ответы (1 шт):