在Beginning Haskell第181页的书中，有一个使用WriterT包装List单子的例子。下面的代码计算图中的路径。注意，这是一个非常简单的算法，没有考虑循环)。
type Vertex = Int
type Edge = (Vertex, Vertex)
pathsWriterT :: [Edge] -> Vertex -> Vertex -> [[Vertex]]
pathsWriterT edges start end = execWriterT (pathsWriterT' edges start end)
pathsWriterT' :: [Edge] -> Vertex -> Vertex -> WriterT [Vertex] [] ()
pathsWriterT' edges start end =
let e_paths = do (e_start, e_end) <- lift edges
guard $ e_start == start
tell [start]
pathsWriterT' edges e_end end
in if start == end
then tell [start] `mplus` e_paths
else e_paths
在pathsWriterT'的let和in块中，我告诉写入器将当前顶点添加到路径中。但是后来在pathsWriterT中，通过执行，我得到了可能路径的列表。
写入器如何将所有计算路径组合到路径列表中?如何不同的路径"存储"独立在一个单一的计算表示的WriterT?(请原谅我的命令式语言)
请记住，Haskell中的Monad是m :: * -> *类型，它支持两种操作:
return :: a -> m a(>>=) :: m a -> (a -> m b) -> m b
尽管将do符号中的一系列操作视为计算通常是有用的，但当您对底层发生的事情感兴趣时，您应该考虑m a类型的值以及当涉及return和(>>=)时它们会发生什么。
这个单子是WriterT [Vertex] []。WriterT是这样定义的:
newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }
用[Vertex]代替w，用[]代替m。我们得到这个:
[(a, [Vertex])]
所以它是一个a类型的值列表，每个值都有一个与它相关联的顶点列表。这些类型等价于模newtype封装/解封装。现在我们需要了解return和(>>=)是如何为这种类型工作的。
returnfor[]创建一个单例列表。所以return 'x' :: [Char]就是['x']。returnforWriterT将累加器设置为mempty，并将剩余的任务委托给内部monad的return。
在本例中，累加器的类型为[Vertex],mempty :: [Vertex]为[]。这意味着return 'x' :: WriterT [Vertex] [] Char被表示为[('x', [])]——'x'字符带有一个空的顶点列表。这很简单:monad的return方法创建了一个单例列表，没有与列表中唯一值相关联的顶点。
(>>=)操作符(发音为"bind"，以防您不知道)。对于列表，它的类型是[a] -> (a -> [b]) -> [b]。它的语义是函数a -> [b]将应用于[a]中的每个元素，并将结果[[b]]连接起来。
[a, b, c] >>= f将变为f a ++ f b ++ f c。一个简单的示例来演示:
[10, 20, 30] >>= a -> [a - 5, a + 5]
你能算出结果列表是什么吗?(在GHCi中运行示例，如果没有)。
没有什么可以阻止您在提供给另一个(>>=)的函数中使用(>>=):
[10, 20, 30] >>= a ->
[subtract 5, (+5)] >>= f ->
[f a]
确实，这就是do-符号的工作方式。上面的例子相当于:
do
a <- [10, 20, 30]
f <- [subtract 5, (+5)]
return (f a)
所以这就像建立一个值树，然后把它扁平化成一个列表。最初的树:
a <- (10)-----------------(20)------------------(30)
| | |
| | |
v v v
f <- (subtract 5)----(+5) (subtract 5)----(+5) (subtract 5)----(+5)
| | | | | |
| | | | | |
v v v v v v
[f a] [f a] [f a] [f a] [f a] [f a]
步骤1(替代f):
a <- (10)-----------------(20)-------------------(30)
| | |
| | |
v v v
[subtract 5 a, a + 5] [subtract 5 a, a + 5] [subtract 5 a, a + 5]
step2(代入a):
[subtract 5 10, 10 + 5, subtract 5 20, 20 + 5, subtract 5 30, 30 + 5]
然后，当然，它减少到[5, 10, 15, 20, 25, 30, 35]。
现在，您可以记住，WriterT为每个值添加了一个累加器。因此，在每一步平坦树，它将使用mappend来合并这些累加器。
让我们回到你的例子，pathWriterT'。为了便于理解，我将稍微修改一下，去掉self-loop的处理，并使绑定单元显式:
pathsWriterT' :: [Edge] -> Vertex -> Vertex -> WriterT [Vertex] [] ()
pathsWriterT' edges start end
| start == end = tell [end]
| otherwise = do
(e_start, e_end) <- lift edges
() <- guard $ e_start == start
() <- tell [start]
pathsWriterT' edges e_end end
考虑调用pathsWriterT'，其中
edges=[(1,2), (2,3), (2,4)]start=1end=4
同样，我们可以画一个树，但它会更复杂，所以让我们逐行绘制:
{- Line 1 -} (e_start, e_end) <- lift edges
{- Line 2 -} () <- guard $ e_start == start
{- Line 3 -} () <- tell [start]
{- Line 4 -} pathsWriterT' edges e_end end
1号线。edges的类型为[Edge]。当您将lift从MonadTrans应用到它们时，它变成了WriterT [Vertex] [] Edge。请记住，在引擎盖下，这只是[(Edge, [Vertex])]。lift对WriterT的实现很简单:将每个值的累加器设置为mempty。因此，现在我们有lift edges等于:
[ ((1,2), []) ,
((2,3), []) ,
((2,4), []) ]
我们的树是:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
对于每一个(e_start, e_end)值，会发生以下情况…
第2行。一条边的源顶点绑定到e_start，目标顶点绑定到e_end。当参数为True时，guard扩展为return ();当参数为False时，扩展为empty。对于列表，return ()为[()],empty为[]。对于我们的monad，我们有相同的累加器:return ()是[((), [])],empty仍然是[](因为没有值可以附加累加器)。因为我们决定了start=1，所以计算guard的结果是:
- for
(1,2),[((), [])] (2,3),[](2,4),[]
有三个结果，因为我们使用每个元素。让我们把它们添加到树中:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
如您所见，我用none代替(2,3)和(2,4)的子节点。这是因为guard没有为它们提供子节点，它返回一个空列表。现在我们继续…
第3行。现在我们使用tell展开累加器。tell返回单位值()，但附加了一个累加器。由于start等于1，累加器将是[1]。让我们来调整树:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
4号线。现在我们调用pathsWriterT' edges e_end end来递归地继续构建树!酷。在这个递归调用中:
edges=旧edgesstart= olde_end=2end=旧end=4
我们回到第一行。我们的树现在看起来像这样:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
第二行…只是这一次，它会给我们留下不同的节点(因为start已经改变了)!
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
和第3行一样，现在它将添加[2]作为累加器。
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
| |
| |
v v
() <- ((), [2]) ((), [2])
在第4行，我们递归到pathsWriterT'。
edges=旧edgesstart= olde_end=3,4end=旧end=4
注意，我将3和4都写为e_end的值。这是因为递归发生在两个分支中:
- 在
(2,3)分支中，我们将再次为每条边创建一个子边。 但是，在分支
(2,4)中，注意start == end保持，递归结束。我们创建了一个子[((), [4])]，因为这是tell [4]的结果。(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
| |
| |
v v
() <- ((), [2]) ((), [2])
| |
____________________|____ v
| | | [((), [4])]
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
在第2行，守卫不允许这里出现任何新的子节点，因为没有满足e_start == 4的节点。
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
| |
| |
v v
() <- ((), [2]) ((), [2])
| |
____________________|____ v
| | | [((), [4])]
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none none none
() <-
唷!我们的树建好了。现在是时候减少它了。我将在每一步减少树的深度1，自下而上。在每个缩减步骤中，我将用它的子节点的连接列表替换父节点，并将mappend将父节点的累加器替换为它的子节点的累加器。为什么是这样的逻辑呢?这就是为monad定义(>>=)的方式。
注意我们树的叶子的类型是[((), [Vertex])]——这是pathsWriterT'的返回类型。请记住，none表示空列表[]，因此它也具有这种类型。内部节点的类型为(a, [Vertex])，其中a是绑定变量的类型(我在树的左侧绘制了变量绑定)。
步骤1.
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
| |
| |
v v
() <- ((), [2]) ((), [2])
| |
____________________|____ v
| | | [((), [4])]
none none none
步骤2。
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
| |
| |
v v
() <- ((), [2]) ((), [2])
| |
none v
[((), [4])]
步骤3。
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none v v
() <- ((), []) ((), [])
| |
| |
none v
[((), [2,4])]
步骤4 .
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
v v v
(e_start, e_end) <- ((1,2), []) ((2,3), []) ((2,4), [])
| | |
| | |
none none v
[((), [2,4])]
第5步。
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|_________________________________
| | |
none none v
[((), [2,4])]
步骤6 .
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
[((), [1,2,4])]
步骤7。
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
[((), [1,2,4])]
步骤8。
[((), [1,2,4])]
execWriterT将丢弃这些值，只留下累加器，现在我们只剩下[[1,2,4]]，这意味着从1到4只有一条路径:[1,2,4]。
练习:做同样的(用笔和纸)，但edges=[(1,2), (1,3), (2,4), (3,4)]。你应该得到[[1,2,4], [1,3,4]]。