在 Haskell 中，如何将一个类列表 monad 绑定到另一个类列表 monad

Question

假设您想在有向图上实现非常通用的操作，尽可能少地对结构进行假设。

不可能完全不做任何假设，所以我仍然假设我会将我的图表表示为某种邻接列表，但精神是尽量对被操纵事物的性质保持不透明.

假设您有以下两种操作：一种是列出图中所有节点的操作，另一种是列出某个顶点的所有出边的操作。

class List_Nodes graph list vertex where
    list_nodes :: graph -> list vertex
class List_Edges_From graph vertex list edge where
    list_edges_from :: graph -> vertex -> list edge

然后，为了好玩，我决定可能要遍历所有边

class List_Edges graph vertex list edge where
    list_edges :: graph -> list edge

无论图的具体实现是什么，我相信我都可以很笼统地表达，列出边可以理解为列出节点，并列出每个节点的边。所以我决定写一个尽可能通用的实例，如下所示：

instance (
    Monad node_list,
    Monad edge_list,
    List_Nodes graph node_list vertex,
    List_Edges_From graph vertex edge_list edge
    ) => List_Edges graph vertex edge_list edge where
    list_edges graph = (list_nodes graph :: node_list vertex) >>= list_edges_from graph
-- I added  :: node_list vertex  to help GHC infer the type.

但是，此代码无法按原样运行。此代码仅适用于 edge_list ~ node_list, 的附加实例要求。那是因为绑定只发生在一个 monad 中，即返回的 monad：edge_list.

但为了尽可能笼统，我不想假设我存储节点的方式必然与我在节点中存储传出边的方式相同。例如，人们可能想使用列表来存储节点，并使用向量来存储节点外的边。

问题： 如何在两个可能不同的列表（如容器）之间表达单子绑定 list_nodes graph >>= list_edges_from graph？

更一般地说，我怎么能说将列表转换为向量而不具体说明它们呢？我只是假设它们是 "list-like" 不管那意味着什么。不知何故，这些类似列表的东西本身就是函子，所以我希望将一些函子转换为其他函子。我在寻找范畴论的自然变换吗？我如何在 Haskell 中执行此操作？

使用的语言扩展和导入：

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Lib () where
import Prelude
import Control.Monad

Answer 1

如果您想对存储节点和边的 monad 非常笼统，那么您真的无能为力。两个单子通常 do not compose 彼此：如果节点 "stored" 为 IO String 且边为 String -> Maybe String，return 类型应该是什么？

我建议在类型级别少做很多这样的工作。几乎不需要类型类：相反，定义一个包含所需函数的具体类型，以及一个用于转换为该规范类型的类型类。然后，您的图形类型的各种实现可以简单地创建其图形的 "canonical view"，以您用于实现通用算法的类型表示它。这样，尽管图形本身有很多表示形式，但您只有一种规范表示形式可以执行这些算法。

图表类型可以简单到

data Graph v e = Graph { nodes :: [v]
                       , edges :: v -> [e]
                       }

class AsGraph t v e where
  asGraph :: t v e -> Graph v e

并且您可以很容易地实现 allEdges。如果你有一个带有向量边的图，它可以被转换成这种通用的图类型，以便参与像 allEdges:

这样的通用操作

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

import Data.Foldable (toList)

data Graph v e = Graph { nodes :: [v]
                       , edges :: v -> [e]
                       }

class AsGraph t v e where
  asGraph :: t v e -> Graph v e

data VectorEdges v e = VectorEdges { vs :: [v]
                                   , es :: v -> Vector e
                                   }

instance AsGraph VectorEdges v e where
  asGraph g = Graph (vs g) (toList . es g)

allEdges :: AsGraph t v e => t v e -> [e]
allEdges g = let g' = asGraph g
  in nodes g' >>= edges g'

Answer 2

在 Haskell 中似乎没有什么标准可以实现我的目的，所以我最终添加了一个 class 特定于列表转换，给我留下了实现它的空间，我认为应该是可转换列表。

class Convert_List list1 list2 element where
    convert_list :: list1 element -> list2 element

那我有空自己实现。

有这样一个 class 的好处是你可以这样写图形操作：

class List_Nodes graph list vertex where
    list_nodes :: graph -> list vertex
class List_Edges_From graph vertex list edge where
    list_edges_from :: graph -> vertex -> list edge

class List_Edges graph vertex list edge where
    list_edges :: graph -> list edge
instance (
    Monad list,
    List_Nodes graph l1 vertex,
    List_Edges_From graph vertex l2 edge,
    Convert_List l1 list vertex,
    Convert_List l2 list edge 
    ) => List_Edges graph vertex list edge where
    list_edges graph = 
        convert_list (list_nodes graph :: l1 vertex) >>= \u -> 
            convert_list (list_edges_from graph u :: l2 edge)

在这里你看到我以非常普遍的方式实现 list_edge，几乎没有做任何假设，我什至没有假设 return 列表必须与图形内部表示相同。

这也是我将每个操作拆分为自己的原因 class 的原因。尽管乍一看这似乎有悖常理，但我相信这里显示的因式分解还有更多潜力。如果我只有一个 class 包含 3 个操作，我就不能只实现 list_edges 而不对其他操作也施加约束。这只是我的意见，但我相信越来越多的这种代码设计方法具有更大的分解潜力。

在 Haskell 中，如何将一个类列表 monad 绑定到另一个类列表 monad

In Haskell, how to bind one list-like monad to another list-like monad

monads

haskell

functor