假设您要对有向图实现非常通用的操作,并尽可能少地假设结构。
不可能完全不做任何假设,因此我仍然假设我将图形表示为某种邻接表,但是其精神是要对操纵物的性质尽可能地保持不透明。
假定您具有以下两个操作:一个操作用于列出图形中的所有节点,并且一个操作用于列出某个顶点的所有输出边缘。
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
?]
[更笼统地说,我如何说可以将列表转换为向量而无需具体说明?我只是假设它们意味着“类似列表”。这些列表之类的东西以某种方式本身就是函子,因此我希望将某些函子转换为其他函子。我是否在寻找类别理论的自然转变?如何在Haskell中执行此操作?
使用的语言扩展名和使用的导入项:
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Lib () where
import Prelude
import Control.Monad
假设您要对有向图实施非常一般的操作,并尽可能少地假设结构。不可能完全不做任何假设,因此我仍然...
如果要对存储节点和边的单子进行非常笼统的介绍,那么您将无能为力。通常,两个Monad相互do not compose:如果将节点“存储”为IO String
,将边“存储为String -> Maybe String
”,则返回类型应该是什么?