我知道什么是单子。我认为我正确地掌握了余单子的概念。(或者说,一个余单子的定义很简单;困难的部分在于理解它的实用性...)
我的问题是:某物件能够既是单子 又是 余单子吗?
我预见到两种可能的答案:
- 是的,这很常见且广泛有用。
- 不,它们执行着如此不同的任务,以至于没有理由希望某物体同时拥有两者的特质。
那么究竟是哪一种呢?
我知道什么是单子。我认为我正确地掌握了余单子的概念。(或者说,一个余单子的定义很简单;困难的部分在于理解它的实用性...)
我的问题是:某物件能够既是单子 又是 余单子吗?
我预见到两种可能的答案:
那么究竟是哪一种呢?
自由余函子可以得到一些数据结构,它们既可以作为单子使用,也可以作为余单子使用:
data Cofree f a = a :< f (Cofree f a)
每个基于 Alternative 函子的自由余单子都可以产生一个单子 -- 可以在这里看到实例:
http://hackage.haskell.org/packages/archive/free/3.4.1/doc/html/Control-Comonad-Cofree.html
instance Alternative f => Monad (Cofree f) where
return x = x :< empty
(a :< m) >>= k = case k a of
b :< n -> b :< (n <|> fmap (>>= k) m)
例如,这使我们可以将非空列表作为Monad和Comonad(以及非空的f-分支树等)。
Identity
不是替代方案,但是Cofree Identity
生成无限流,事实上我们可以给该流提供一个不同的monad实例:
http://hackage.haskell.org/packages/archive/streams/3.1/doc/html/Data-Stream-Infinite.html
data Stream a = a :> Stream a
instance Comonad Stream where
duplicate = tails
extend f w = f w :> extend f (tail w)
extract = head
instance Monad Stream where
return = repeat
m >>= f = unfold (\(bs :> bss) -> (head bs, tail <$> bss)) (fmap f m)
(请注意以上函数不是在列表中定义的,而是在streams
包中定义的)。
同样,阅读器箭头并非替代品,但Cofree ((->) r)
产生了一个Moore机,而Moore机也是单子和余单子:
http://hackage.haskell.org/packages/archive/machines/0.2.3.1/doc/html/Data-Machine-Moore.html
data Moore a b = Moore b (a -> Moore a b)
instance Monad (Moore a) where
return a = r where r = Moore a (const r)
Moore a k >>= f = case f a of
Moore b _ -> Moore b (k >=> f)
_ >> m = m
instance Comonad (Moore a) where
extract (Moore b _) = b
extend f w@(Moore _ g) = Moore (f w) (extend f . g)
那么这些例子背后的直觉是什么呢?我们可以免费获得共函子操作。我们获得的单子操作都是对角化的形式。使用"alternative",我们可以将事物 <|>
在一起来"压缩"结构,并在我们用完结构时创造出"空"的事物。这让我们可以处理有限情况。如果缺乏"alternative",我们需要有不确定数量的结构,这样无论我们进行多少次"join"操作(我们可以将其视为拼接或替换),总会有更多的空间来放置拼接的元素(就像希尔伯特酒店一样:http://www.encyclopediaofmath.org/index.php/Hilbert_infinite_hotel)。
相关地,每一个共函子都引出了一个相关的单子(尽管我认为这更像是一个好奇心):
http://hackage.haskell.org/packages/archive/kan-extensions/3.1.1/doc/html/Control-Monad-Co.html
newtype Identity a = Identity {runIdenity :: a} deriving Functor
instance Monad Identity where
return = Identity
join = runIdentity
instance CoMonad Identity where
coreturn = runIdentity
cojoin = Identity
阅读器和写入器是一对完全的对偶,如下所示
class CoMonoid m where
comempty :: (m,a) -> a
comappend :: m -> (m,m)
--every haskell type is a CoMonoid
--that is because CCCs are boring!
instance Monoid a => Monad ((,) a) where
return x = (mempty,x)
join (a,(b,x)) = (a <> b, x)
instance CoMonoid a => CoMonad ((,) a) where
coreturn = comempty
cojoin = associate . first comappend
instance CoMonoid a => Monad ((->) a) where
return = flip (curry comempty)
join f = uncurry f . comappend
instance Monoid a => CoMonad ((->) a) where
coreturn f = f mempty
cojoin f a b = f (a <> b)
flip curry comempty
)和ii)我自己对它们的理解非常少。这本身就值得点赞。 - Tom W有许多有趣的结构既是Monad
又是Comonad
。
已经有几个人在这里指出了Identity
函子,但还有一些非平凡的例子。
Writer Monad
在扮演Comonad
时类似于Reader
。
instance Monoid e => Monad ((,) e)
instance Comonad ((,) e)
Reader
Monad
具有类似于 Writer
的角色,作为一个 Comonad
。
instance Monad ((->) e)
instance Monoid e => Comonad ((->)e)
非空列表也构成单子和余单子,实际上是包含自由余单子的更大构造的特殊情况。 Identity
情况也可以看作是这种情况的一个特例。
还有各种基于Kan扩展的类似于 Yoneda
和 Codensity
的构造,用于转换单子和余单子,尽管在操作效率方面它们更偏向于其中之一。
我还有一个适配器,可以将任意余单子转换为单子变换器。不幸的是,在Haskell中相反的转换是不可能的。
在线性代数中有一个双代数(bialgebra)的概念。理想情况下,如果我们有一个既构成 Monad
又构成 Comonad
的东西,并且希望同时使用这些操作而无需逐个进行推理,那么我们希望 return
和 join
是余单子的余代数,因此 extract
和 duplicate
就是 Monad
代数。如果满足这些条件,那么你实际上可以推理关于同时具有 Monad f
和 Comonad f
约束,并混合来自每个约束的组合器而无需逐个推理的代码。
kan-extensions
中吗? - J. Abrahamson这取决于你认为“单子(monad)”是什么。如果你问“是否可能一个类型同时是Monad
和Comonad
的实例?”,那么答案是肯定的。这里有一个简单的例子。
newtype Id a = Id a
instance Monad Identity where
return = Id
(Id a) >>= f = f a
instance Comonad Identity where
extract (Id a) = a
extend f ida = Id (f ida)
(X, return, bind)
组成的,其中 X
是一个类型,return
和 bind
遵循你所期望的类型和规则。类似地,一个余子(Comonad)就是 (X, extend, extract)
。我刚才演示了可能有相同的X
,但由于extend
和return
或extract
和bind
的不同类型,它们不可能是相同的函数。因此,一个数学上的单子永远不可能是一个余子。在Hammer的建议基础上,编写一个函数 [x] -> [[x]]
看起来非常简单。例如:
map (\ x -> [x])
看起来列表可以形成一个共同函子。哦,等等。这处理了cojoin
,但是coreturn :: [x] -> x
怎么办?显然,这就是为什么只有非空列表形成共同函子的原因。
这给我们带来了一个类型为([x] -> x) -> [x] -> [x]
的cobind函数。有趣的是,Hoogle并不知道这样的函数。然而,我们已经有了concatMap :: (x -> [x]) -> [x] -> [x]
。我还没有看到cobind函数的立即用途,但我可以想象存在这样的用途。
我仍然在努力理解共同函子以及它可能有用的地方。到目前为止,得到的答案让我有些思考......
cojoin
不符合共单子律。特别地,coreturn.cojoin
应该是恒等式。我谈到的共单子具有cojoin=init.tails
和coreturn=head
。 - hammar
Reader
和Writer
都可以作为共函子,不过它们的功能是不同的,并且需要一个Monoid
约束条件来交换。 - C. A. McCann