Добрый день, пытаюсь написать моноид 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
Проблема не в 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 за комментарии.)
Если m ~ Tree b
, то foldMap
имеет тот же тип, что и fmap
, но я не думаю, что правильно говорить, что одно сводится к другому. Я ожидаю, что это будет означать, что это одна и та же функция, но foldMap
может изменить структуру дерева, а fmap
— нет.
@amalloy На самом деле даже типы не совпадают. Вы получаете foldMap :: (a -> Tree b) -> Tree a -> Tree b
, но fmap :: (a -> b) -> Tree a -> Tree b
.
@DanielWagner Ах, конечно.
Спасибо! это очень сложно для новичка