Моноид на любом складном

Я пытаюсь создать экземпляр Monoid на haskell, моноид, который может быть применим к любой структуре Foldable, которая содержит сопоставимые элементы и возвращает сохраненное максимальное значение.

Пока у меня есть это

import Data.List
import Data.Functor
import Data.Monoid
import Data.Foldable
import Data.Tree

newtype Max a = Max { getMax :: Maybe a}
   deriving (Eq, Ord, Show, Read)

instance Ord a => Monoid (Max a) where
   mempty = Max Nothing
   mappend (Max x) (Max y) = Max (max x y)

Он отлично работает в списке, но есть некоторые проблемы с деревьями. Когда я использую его в пустом списке, он возвращается

ghci> foldMap (Max . Just) []
Max {getMax = Nothing}

И это то, что я хочу, но когда я использую его на деревьях без элементов

ghci> foldMap (Max . Just) (Node [] [])
Max {getMax = Just []}

Но я хочу, чтобы он не возвращал Nothing вместо Just []. Он не работает с узлами без детей, но работает с ценными.

ghci> foldMap (Max . Just) (Node 22 [Node 7 [Node 42 []], Node 18 [] ])
Max {getMax = Just 42}

Любое предложение?

ПД: Я использую ghci 7.10


person alejandro Guevara    schedule 04.05.2016    source источник
comment
Node [] [] не пустое дерево, это единственный узел без дочерних элементов.   -  person Lee    schedule 05.05.2016
comment
Вам необходимо уточнить, о каком типе дерева идет речь.   -  person leftaroundabout    schedule 05.05.2016
comment
Этот моноид также доступен в моноиде- дополнительные услуги. Небольшое предупреждение, если вы реализуете Min самостоятельно вместо использования этого пакета: mappend (Min x) (Min y) = Min (min x y) не совсем правильно!   -  person Daniel Wagner    schedule 05.05.2016


Ответы (1)


Тип Tree в Data.Tree не поддерживает пустые деревья. Спросите GHCI, что это за тип Node [] [], и вы узнаете примерно следующее:

Node [] [] :: a => Tree [a]

Ваш моноид работает нормально.

person Dietrich Epp    schedule 04.05.2016
comment
но не должны применяться так же, как списки без элементов? - person alejandro Guevara; 05.05.2016
comment
Это не дерево без элементов. Это дерево с одним элементом, и это элемент []. - person Dietrich Epp; 05.05.2016
comment
Я не думаю, что у вас будет ограничение (а также a => Tree [a] будет недействительным, потому что a не может быть ограничением в этом контексте, даже если ConstraintKinds включены) - person David Young; 05.05.2016
comment
@DavidYoung: Обратите внимание, что там нет класса. Это просто усталый мозг, думающий forall a., а вместо этого пишущий a =>. - person Dietrich Epp; 05.05.2016