您的问题有三个答案,一个是挑剔的,一个是无用的,一个是抽象的:
挑剔的答案
instance Monoid (Ftree a) where
mempty = Empty
mappend = Branch
这是Monoid
类型类的一个实例,但不满足任何必需的属性。
无用的答案
你想要什么 Monoid?仅仅在没有更多信息的情况下要求一个幺半群实例就像在没有给出问题的情况下要求一个解决方案。有时有一个自然的幺半群实例(例如对于列表)或者只有一个(例如对于()
,忽略定义的问题)。我不认为这里的情况。
顺便说一句:如果您的树在内部节点处具有递归组合两棵树的数据,那么将会有一个有趣的幺半群实例......
抽象的答案
既然你给了一个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-notation 编写的 Monad 定律。
我们的mappend
,用 do-Notation 写成,是:
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 实例。它可能是也可能不是您正在寻找的那个。