haskell - 如何在 haskell 中为这棵树实现 monoid 接口(interface)？

Question

请原谅我的术语，我的思维仍然困惑。

树:

data Ftree a = Empty | Leaf a | Branch ( Ftree a ) ( Ftree a )
    deriving ( Show )

我有几个问题:

1. 如果Ftree不能为Empty，那么它是否不再是Monoid，因为没有标识值。

2. 您将如何使用这棵树实现mappend？你能随意将两棵树嫁接在一起吗？

3. 对于二叉搜索树，您是否必须内省(introspection)两个树中的某些元素以确保 mappend 的结果仍然是 BST？

郑重声明，Ftree 还可以在这里做一些其他事情:

instance Functor Ftree where
    fmap g Empty             = Empty
    fmap g ( Leaf a )        = Leaf ( g a )
    fmap g ( Branch tl tr )  = Branch ( fmap g tl ) ( fmap g tr )

instance Monad Ftree where 
    return             = Leaf
    Empty        >>= g = Empty
    Leaf a       >>= g = g a
    Branch lt rt >>= g = Branch ( lt >>= g ) ( rt >>= g )

Answer 1

您的问题有三种答案，一种是挑剔的，一种是无益的，一种是抽象的:

挑剔的回答

instance Monoid (Ftree a) where
    mempty = Empty
    mappend = Branch

这是 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法律成立(我没有检查你的定义)。此时，回想一下Monad laws written in do-notation .

我们的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 实例。它可能是也可能不是您正在寻找的那个。