如何在haskell中为该树实现monoid接口? [英] How do you implement monoid interface for this tree in haskell?

问题描述

请原谅我的用语，我的思想仍在弯曲.

树:

 数据Ftree a =空|叶a |分支(Ftree a)(Ftree a)派生(显示) 

我有几个问题:

1. 如果不能将 Ftree 设置为 Empty ，则由于没有身份值，它将不再是 Monoid .

p>

2. 如何用此树实现 mappend ?你能把两棵树随意地嫁接在一起吗?

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

为了记录，其他一些 Ftree 可以在这里执行:

  instance Functor Ftree其中fmap g空=空fmap g(叶子a)=叶子(g a)fmap g(分支tl tr)=分支(fmap g tl)(fmap g tr)实例Monad Ftree，其中return =叶子空>> = g =空叶a> = g = g a分支rt≥g =分支(lt = g)(rt = g) 

解决方案

您的问题有三种答案，一种是繁琐的，一种是无用的，另一种是摘要:

繁琐的答案

  instance Monoid(Ftree a)其中虚空=空mappend =分支 

这是 Monoid 类型类的实例，但不满足任何必需的属性.

无益的答案

您想要什么Monoid?只是在没有更多信息的情况下索要一个monoid实例，就像在不给出问题的情况下索要解决方案.有时会有一个自然的monoid实例(例如，用于列表)，或者只有一个(例如，对于()，而不考虑定义性问题).我认为这里不是这种情况.

^{BTW:如果您的树在内部节点上具有将两个树递归合并的数据，那么将是一个有趣的monoid实例...}

抽象答案

由于您提供了 Monad(Ftree a)实例，因此有一种通用的方法来获取 Monoid 实例:

  instance(Monoid a，Monad f)=>Monoid(f a)其中虚空=返回虚空mappend f g = f>> =(\ x->(mappend x)`fmap` g) 

让我们检查这是否是Monoid.我使用<>= mappend .我们假设 Monad 法则成立(我没有检查您的定义).此时，请回想以do-notation编写的Monad法则.

用do-Notation编写的 mappend 是:

 追加f g =做&&返回(f< g) 

所以我们现在可以验证类半定律:

左身份

  mempty g≡-mappend的定义做x小于-&返回(x< y)≡-mempty的定义做x<-返回无用&返回(x< y)≡-单子法则做&返回(空<> y)≡-基本的半规半律做&返回y≡-单子法则G 

正确的身份

 强制添加为空≡-mappend的定义做&y<-空荡荡的返回(x< y)≡-单子法则做&回报(x<>空荡荡的)≡-基本的半规半律做&返回x≡-单子法则F 

最后是重要的关联性法则

 后缀f(后缀g h)≡-mappend的定义做&y<-x′＜-g'返回(x'< y')返回(x< y)≡-单子法则做&x′＜-g'y<-return(x'< y')返回(x< y)≡-单子法则做&x′＜-g'返回(x<>(x'<> y'))≡-基本的半规半律做&x′＜-g'返回((x<> x')<> y')≡-莫纳德定律做&x′＜-gz<-return(x<> x')'返回(z<> y')≡-单子法则做&&x′＜-g返回(x<> x')'返回(z<> y')≡-mappend的定义mappend(mappend f g)h 

因此，对于每个(适当的)Monad(甚至对于每个应用函子，如Jake McArthur在#haskell上所指出的)，都有一个Monoid实例.它可能是您想要的，也可能不是.

Please excuse the terminology, my mind is still bending.

The tree:

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

I have a few questions:

1. If Ftree could not be Empty, would it no longer be a Monoid since there is no identity value.

2. How would you implement mappend with this tree? Can you just arbitrarily graft two trees together willy nilly?

3. For binary search trees, would you have to introspect some of the elements in both trees to make sure the result of mappend is still a BST?

For the record, some other stuff Ftree could do here:

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 )

解决方案

There are three answers to your question, one captious and one unhelpful and one abstract:

The captious answer

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

This is an instance of the Monoid type class, but does not satisfy any of the required properties.

The unhelpful answer

What Monoid do you want? Just asking for a monoid instance without further information is like asking for a solution without giving the problem. Sometimes there is a natural monoid instance (e.g. for lists) or there is only one (e.g. for (), disregarding questions of definedness). I don’t think either is the case here.

^{BTW: There would be an interesting monoid instance if your tree would have data at internal nodes that combines two trees recursively...}

The abstract answer

Since you gave a Monad (Ftree a) instance, there is a generic way to get a Monoid instance:

instance (Monoid a, Monad f) => Monoid (f a) where
    mempty = return mempty
    mappend f g = f >>= (\x -> (mappend x) `fmap` g)

Lets check if this is a Monoid. I use <> = mappend. We assume that the Monad laws hold (I did not check that for your definition). At this point, recall the Monad laws written in do-notation.

Our mappend, written in do-Notation, is:

mappend f g = do
  x <- f
  y <- g
  return (f <> g)

So we can verify the monoid laws now:

Left identity

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

Right identity

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

And finally the important associativity law

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

So for every (proper) Monad (and even for every applicative functor, as Jake McArthur pointed out on #haskell), there is a Monoid instance. It may or may not be the one that you are looking for.

这篇关于如何在haskell中为该树实现monoid接口?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！