你如何在haskell中为这棵树实现monoid接口？

Question

请原谅术语,我的思绪还在弯曲.

那个树:

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

我有几个问题:

1. 如果Ftree不可能Empty,它将不再是一个,Monoid因为没有身份价值.

2. 你会如何实现mappend这棵树？你能不能随意嫁接两棵树吗？

3. 对于二叉搜索树,您是否必须内省两棵树中的一些元素以确保结果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类型类的实例,但不满足任何必需的属性.

无益的答案

你想要什么Monoid？只是在没有进一步信息的情况下要求一个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法律适用(我没有检查您的定义).在这一点上,回想一下用附加法写的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实例.它可能是也可能不是您正在寻找的那个.