获取类型参数的标识？

Question

我有以下类型，我想成为 Monoid 的实例 typeclass.I 不知道如何在使用参数化时将参数化字段设置为 identity.Is类型以获取该类型的标识？

data Tree a=Leaf a | Node a (Tree a) (Tree a) |Empty deriving (Eq,Show)

instance Monoid Tree where
    mempty=Empty
    mappend a Empty=a
    mappend a b=Node (identity) x y

如您所见，我需要将简单字段设置为参数类型的标识。

例子

mappend::Tree Int
mappend (Leaf 1) (Leaf 2)=Node 0 (Leaf 1) (Leaf 2)

mappend::Tree []
mappend (Leaf [1,2])(Leaf [2,3])=Node [] (Leaf [1,2])(Leaf [2,3])

Answer 1

这只有在 a 本身也是 Monoid 类型时才会发生，所以我们可以这样写：

instance <b>Monoid a</b> => Monoid (Tree <b>a</b>) where
    mempty = Empty
    mappend Empty a = a
    mappend a Empty = a
    mappend a b = Node <b>mempty</b> a b

以上不适用于 Int，因为 Int 不是 Monoid。有两个非常受欢迎的候选 (ℕ, +, 0) 和 (ℕ, ×, 1)。但是，您可以使用 Sum 表示前一个幺半群。

最后一行正文中的mempty因此不是我们正在定义的mempty，而是类型的mempty a.

话虽如此，如果您这样定义 Monoid Tree，则意味着您考虑了 Node mempty (Node mempty a b) c == Node mempty a (Node mempty b c)，因为这是 幺半群法则所要求的.所以这里的deriving Eq与mappend并不完全“和谐”。 mappend 运算符（在数学中通常表示为 ⊕），应满足条件 ∀ a,b,c∈ S: a⊕(b⊕c) = (a⊕b)⊕c.

您要么应该 Eq 自己以不同的方式实现，要么您应该尝试为您的幺半群提出另一种结构。

Answer 2

这不是答案，但对于评论来说太长了。正如 Willem Van Onsem 所建议的那样，您的 Monoid 实例不合法。我怀疑您可能想要以下两件事之一：

自由岩浆

可以定义类型上的游离岩浆

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

这不是天然的幺半群，但有时假装它是一个很有用：

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

-- For recent GHC, add this instance
instance Semigroup (Magma a) where
  (<>) = Branch

这可以与折叠一起使用以深入了解该折叠的结构。要了解其工作原理，请比较将 foldMap Leaf 应用于 [1..20]、Data.Sequence.fromList [1..20] 和 Data.Set.fromList [1..20].

的结果

一个（特定的）自由 monad

考虑概括您的树以允许内部节点中的类型不同于叶子中的类型：

data Tree a b = Node a (Tree a b) (Tree a b) | Leaf b
  deriving (Show, Eq)

（这原来是仿函数 Tree a 上的自由 monad，已定义

data TreeF a b = NodeF a b b

但我们真的不需要深入了解这意味着什么。）

Tree a monad 的 monad 操作是一种 "grafting"，其中叶子被树替换。

instance Functor (Tree a) where
  fmap f (Leaf b) = Leaf (f b)
  fmap f (Node a l r) = Node a (fmap f l) (fmap f r)

instance Applicative (Tree a) where
  pure = Leaf
  (<*>) = ap
  liftA2 = liftM2

instance Monad (Tree a) where
  Leaf b >>= f = f b
  Node a l r >>= f = Node a (l >>= f) (r >>= f)

您可以将 >>= 视为支持一种垂直附加，其中树从其叶子向下生长。

获取类型参数的标识？

Getting identity for type parameter?

haskell

monoids

自由岩浆

一个（特定的）自由 monad