Как правильно реализовать моноид для красно-черного дерева?

Добрый день, пытаюсь написать моноид RB Tree, код примерно такой:

data Tree a = Leaf | Node a Color (Tree a) (Tree a) deriving (Show)

instance (Ord a) => Monoid (Tree a) where
    mempty = Leaf
    l1 `mappend` l2 = foldl (\x y ->insert y x) l1 l2


instance Foldable Tree where
   foldr _ z Leaf = z
   foldr f z (Node d _ l r) = foldr f (f d (foldr f z r)) l
   foldl _ z Leaf = z
   foldl f z (Node d _ l r) = foldl f (f (foldl f z l) d) r

...

insert :: (Ord a) => a -> Tree a -> Tree a
insert x s = makeBlack $ ins s
  where ins Leaf  = Node x Red Leaf Leaf
        ins (Node d c l r)
          | x < d  = balance d c (ins l) r
          | x == d = Node d c l r
          | x > d  = balance d c l (ins r)
        makeBlack (Node d _ l r) = Node d Black l r

Проблема заключается в объявлении моноида:

• Could not deduce (Semigroup (Tree a)) arising from the superclasses of an instance declaration from the context: Ord a bound by the instance declaration at src/RedBlackTree.hs:19:10-35 • 
In the instance declaration for ‘Monoid (Tree a)’ | 19 | instance (Ord a) => Monoid (Tree a) where | ^^^^^^^^^^^^^^^^^^^^^^^^^^

Я понимаю, что для использования insert значения должны быть сопоставимы, но кажется, что я как-то неправильно направил (Ord a) в экземпляре

Бонусный вопрос: Я тоже реализовал fmap, но не понял отличия от foldMap

Шаблоны Angular PrimeNg
Шаблоны Angular PrimeNg
Как привнести проверку типов в наши шаблоны Angular, использующие компоненты библиотеки PrimeNg, и настроить их отображение с помощью встроенной...
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Создайте ползком, похожим на звездные войны, с помощью CSS и Javascript
Если вы веб-разработчик (или хотите им стать), то вы наверняка гик и вам нравятся "Звездные войны". А как бы вы хотели, чтобы фоном для вашего...
Документирование API с помощью Swagger на Springboot
Документирование API с помощью Swagger на Springboot
В предыдущей статье мы уже узнали, как создать Rest API с помощью Springboot и MySql .
Начала с розового дизайна
Начала с розового дизайна
Pink Design - это система дизайна Appwrite с открытым исходным кодом для создания последовательных и многократно используемых пользовательских...
Шлюз в PHP
Шлюз в PHP
API-шлюз (AG) - это сервер, который действует как единая точка входа для набора микросервисов.
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
0
0
89
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема не в Ord. Если вы внимательно посмотрите на полученное сообщение об ошибке, оно начинается с «Не удалось вывести (полугруппа (дерево a)) из суперклассов объявления экземпляра». Другими словами, чтобы иметь экземпляр Monoid (Tree a), вам сначала нужно иметь экземпляр для Semigroup (Tree a). К счастью, это легко добавить:

instance (Ord a) => Semigroup (Tree a) where
    (<>) = mappend

(Возможно, более идиоматический подход состоял бы в том, чтобы определить <> в экземпляре Semigroup, используя определение foldl, которое вы использовали для mappend, а затем в вашем экземпляре для Monoid просто пропустить определение mappend.)


Бонус: разница между fmap и foldMap очевидна из их типов. Для вашего дерева fmap будет иметь тип (a -> b) -> Tree a -> Tree b, что указывает на то, что оно отображает внутренние a значения в b значения. С другой стороны, foldMap будет иметь тип Monoid m => (a -> m) -> Tree a -> m. Вы можете вызывать foldMap с помощью m ~ Tree b, и в этом случае foldMap становится очень похожим на fmap (тип будет (a -> Tree b) -> Tree a -> Tree b, что не совсем совпадает с fmap), но вы также можете вызывать его с m ~ [b] или другим моноидом. (Спасибо @amalloy и @Daniel Wagner за комментарии.)

Спасибо! это очень сложно для новичка

student422 21.11.2022 02:59

Если m ~ Tree b, то foldMap имеет тот же тип, что и fmap, но я не думаю, что правильно говорить, что одно сводится к другому. Я ожидаю, что это будет означать, что это одна и та же функция, но foldMap может изменить структуру дерева, а fmap — нет.

amalloy 21.11.2022 03:34

@amalloy На самом деле даже типы не совпадают. Вы получаете foldMap :: (a -> Tree b) -> Tree a -> Tree b, но fmap :: (a -> b) -> Tree a -> Tree b.

Daniel Wagner 21.11.2022 04:23

@DanielWagner Ах, конечно.

amalloy 21.11.2022 04:59

Другие вопросы по теме