对于你的问题,有三种答案,一种是挑剔的,一种是无益的,一种是抽象的:
挑剔的答案
instance Monoid (Ftree a) where
mempty = Empty
mappend = Branch
这是一个例子Monoid
类型类,但不满足任何所需的属性。
无益的答案
你想要什么幺半群?只要求一个幺半群实例而不提供更多信息就像要求解决方案而不给出问题一样。有时存在一个自然幺半群实例(例如对于列表)或者只有一个(例如对于()
,忽略定义问题)。我认为这里的情况都不是这样。
BTW: There would be an interesting monoid instance if your tree would have data at internal nodes that combines two trees recursively...
抽象的答案
既然你给了Monad (Ftree a)
例如,有一种通用方法可以获取Monoid
实例:
instance (Monoid a, Monad f) => Monoid (f a) where
mempty = return mempty
mappend f g = f >>= (\x -> (mappend x) `fmap` g)
让我们检查一下这是否是一个 Monoid。我用<> = mappend
。我们假设Monad
法律成立(我没有检查你的定义)。此时,回想一下用 do 符号写成的 Monad 定律 http://www.haskell.org/haskellwiki/Monad_Laws.
Our mappend
,用 do 表示法写成:
mappend f g = do
x <- f
y <- g
return (f <> g)
所以我们现在可以验证幺半群定律:
左身份
mappend mempty g
≡ -- Definition of mappend
do
x <- mempty
y <- g
return (x <> y)
≡ -- Definition of mempty
do
x <- return mempty
y <- g
return (x <> y)
≡ -- Monad law
do
y <- g
return (mempty <> y)
≡ -- Underlying monoid laws
do
y <- g
return y
≡ -- Monad law
g
正确的身份
mappend f mempty
≡ -- Definition of mappend
do
x <- f
y <- mempty
return (x <> y)
≡ -- Monad law
do
x <- f
return (x <> mempty)
≡ -- Underlying monoid laws
do
x <- f
return x
≡ -- Monad law
f
最后是重要的结合律
mappend f (mappend g h)
≡ -- Definition of mappend
do
x <- f
y <- do
x' <- g
y' <- h
return (x' <> y')
return (x <> y)
≡ -- Monad law
do
x <- f
x' <- g
y' <- h
y <- return (x' <> y')
return (x <> y)
≡ -- Monad law
do
x <- f
x' <- g
y' <- h
return (x <> (x' <> y'))
≡ -- Underlying monoid law
do
x <- f
x' <- g
y' <- h
return ((x <> x') <> y')
≡ -- Monad law
do
x <- f
x' <- g
z <- return (x <> x')
y' <- h
return (z <> y')
≡ -- Monad law
do
z <- do
x <- f
x' <- g
return (x <> x')
y' <- h
return (z <> y')
≡ -- Definition of mappend
mappend (mappend f g) h
因此,对于每个(适当的)Monad(甚至对于每个应用函子,正如 Jake McArthur 在 #haskell 上指出的那样),都有一个 Monoid 实例。它可能是也可能不是您正在寻找的那个。