haskell - 要求函数必须是 Haskell 中的撤回？

Question

我正在设想一个单子(monad)图的实现。我会尽力解释它是如何在这里构建的。

Graph 类型应该与以下同构:

data Graph e v = Graph{ vertices :: [v], edges :: [(e, (v, v))] }

其中 e 是边类型，v 是顶点类型，我们包括一个顶点列表和一个边列表以及它们连接的顶点。

我设想的是这种类型的 monad 实例，如下所示:

instance Monad (Graph e) where
  return v = Graph v [] -- | Empty graph with one vertex
  m >>= f  = {- see below -}

我对如何实现 >>= 有一个想法，它基本上获取每个顶点，将其映射到一个新图，然后重新连接相应地构建每个图的顶点原图连通。

例如，考虑一个函数 f，它接受一个顶点并从中生成两个顶点 (K_2) 上的完整图。然后，如果我们将 K_2 自身绑定(bind)到 f，我们将得到如下内容:

A----B
|    |
C    D

其中图 A----B 是原始图，而图 A----C 和 B----D 分别从 A 和 B 生成。最后，A 和 B 需要连接，因为它们在原始图中是连接的。请注意，A 和 B 不必完全相同，但它们需要直接映射到新图中的某些内容。为了简单起见，我省略了一些信息(图形的边缘是什么，等等)，但我注意到的要点是，要使其实际用作 Monad 实例，A需要直接映射到f A中的一个顶点，B也是如此。通常，原始图中的每个顶点都需要直接映射到由 f 生成的图中的图。

如果我没理解错的话，这意味着 f must be a retraction for some other morphism g .如果是，我们可以通过将其结果图中的每个变形顶点连接到其他变形顶点来清楚地加入该图，从而生成我们想要的类型的新图。

大多数情况下这只是我的一个想法，但我真的很想知道在 Haskell 中是否有任何方法要求 f 是一个撤回？有没有一种方法可以在语言的范围内说明这一点，以便为图形提供 Monad 的适当实例，或者要做到这一点，我必须说“这实际上只是一个 monad，如果你绑定(bind)的功能是撤回？”我怀疑是后者，但我只是想检查一下。

或者，我可能理解错了!请随时纠正我或给我一些您自己的想法。

Answer 1

如评论所说，您可以使用尖头图:

module PointedGraph where
import Control.Arrow (second)

data PointedGraph e v = PointedGraph { hops :: [(e, PointedGraph e v)], center :: v }
  deriving (Eq, Show)

instance Monad (PointedGraph e) where
  return = PointedGraph []
  PointedGraph hs c >>= f = PointedGraph (hs' ++ map (second (>>= f)) hs) c'
    where PointedGraph hs' c' = f c

connect :: PointedGraph e v -> e -> PointedGraph e v -> PointedGraph e v
connect g e g' = g { hops = (e,g') : hops g }

k2, ex :: PointedGraph String Int

k2 = connect (return 0) "original" (return 2)

ex = do
  n <- k2
  connect (return n) "derived" (return $ n + 1)

所以这使得:

k2: 0 -original-> 2

ex: 0 -original-> 2
    |             |
    derived       derived
    |             |
    v             v
    1             3

请注意，我们没有检查顶点标签的唯一性(这需要一个 Eq 约束或类似的)所以我们可以很容易地得到类似的东西

k2 >>= const k2:

    0 -original-> 0
    |             |
    original      original
    |             |
    v             v
    2             2