任何可折叠的幺半群

Question

我正在尝试在 haskell 上创建一个 Monoid 的实例，一个可以应用于包含可比较元素和 returns 存储的最大值的任何 Foldable 结构的monoid。

到目前为止我有这个

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)

它在 list 上运行得很好，但在 Trees 上有一些问题。当我在无效列表中使用它时 returns

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

这就是我想要的，但是当我在没有元素的树上使用它时

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

但我想要 returns 什么都没有，只是 []。它不适用于没有子节点的节点，但它适用于有价值的节点

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

有什么建议吗？

PD：我正在使用 ghci 7.10

Answer 1

Data.Tree中的Tree类型不支持空树。询问 GHCI Node [] [] 的类型是什么，您会发现类似这样的内容：

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

你的幺半群工作正常。

任何可折叠的幺半群

Monoid on any Foldable

haskell

monoids