6

用語をご容赦ください、私の心はまだ曲がっています。

ツリー:

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

いくつかの質問を聞きたいんです：

  1. Ftreeであることができなかった場合、ID 値がないため、Emptyもはや ではありません。Monoid

  2. mappendこのツリーをどのように実装しますか? 勝手に 2 本の木を無造作に接ぎ木できますか?

  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 )
4

1 に答える 1

11

あなたの質問には 3 つの答えがあります。

気まぐれな答え

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

これはMonoid型クラスのインスタンスですが、必要なプロパティを満たしていません。

役に立たない答え

欲しいモノイドは？詳細な情報なしにモノイド インスタンスを要求するだけでは、問題を提示せずに解決策を要求するようなものです。自然なモノイド インスタンスが存在する場合 (例: リストの場合) や、1 つしかない場合 (例:()定義の問題を無視する場合) があります。ここではどちらも当てはまらないと思います。

ところで: ツリーの内部ノードに 2 つのツリーを再帰的に結合するデータがある場合、興味深いモノイド インスタンスが存在します...

抽象的な答え

インスタンスを指定したので、インスタンス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)

これがモノイドかどうか調べてみましょう。私は使用します<> = mappend。法律が成り立つと仮定しMonadます（私はあなたの定義のためにそれをチェックしませんでした）。この時点で、do-notation で書かれたモナドの法則を思い出してください。

do- Notationmappendで書かれた は次のとおりです。

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

したがって、すべての (適切な) モナド (および #haskell で Jake McArthur が指摘したように、すべてのアプリケーション ファンクターについても) には、モノイド インスタンスがあります。それはあなたが探しているものかもしれませんし、そうでないかもしれません。

于 2013-02-24T18:20:45.110 に答える