在第181页的Beginning Haskell一书中,有一个WriterT用于包装Listmonad 的示例.下面的代码计算图表中的路径.请注意,这是一个非常简单的算法,不考虑循环).
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
在我let和告诉作者的两个和in块中,将当前顶点添加到路径中.但后来通过执行编写器,我得到了可能的路径列表.pathsWriterT'pathsWriterT
Writer如何将所有计算的路径组合到路径列表中？如何在单个计算中独立"存储"不同的路径WriterT？(原谅我的命令性语言)
Remember that a Monad in Haskell is a type m :: * -> * that supports two operations:
return :: a -> m a(>>=) :: m a -> (a -> m b) -> m bAlthough it is often useful to think about a sequence of actions in do-notation as a computation, when you're interested in what's going on under the hood, you should think about values of type m a and what happens to them when return and (>>=) are involved.
The monad in question is WriterT [Vertex] []. And this is how WriterT is defined:
newtype WriterT w m a = WriterT { runWriterT :: m (a, w) }
Substitute [Vertex] for w and [] for m. We get this:
[(a, [Vertex])]
所以它是一个类型a值列表,每个值都有一个与之关联的顶点列表.这些类型是等同模NEWTYPE包装/解包.现在我们需要了解这种类型的工作方式return和(>>=)工作方式.
return用于[]创建单例列表.所以return 'x' :: [Char]是['x'].return用于WriterT将累加器设置mempty为并将作业的其余部分委托给return内部monad.
In our case, the accumulator has type [Vertex] and mempty :: [Vertex] is []. This means that return 'x' :: WriterT [Vertex] [] Char is represented as [('x', [])] — the 'x' character with an empty list of vertices. That's pretty straightforward: the return method of our monad creates a singleton list with no vertices associated with the only value in this list.
The tricky part is, of course, the (>>=) operator (pronounced "bind", in case you didn't know). For lists it has type [a] -> (a -> [b]) -> [b]. Its semantics are that the function a -> [b] will be applied to each element in [a], and the resulting [[b]] will be concatenated.
[a, b, c] >>= f will become f a ++ f b ++ f c. A simple example to demonstrate:
[10, 20, 30] >>= \a -> [a - 5, a + 5]
Can you figure out what the resulting list will be? (Run the example in GHCi, if not).
Nothing prevents you from using (>>=) within the function supplied to another (>>=):
[10, 20, 30] >>= \a ->
[subtract 5, (+5)] >>= \f ->
[f a]
Indeed, this is how the do-notation works. The above example is equivalent to:
do
a <- [10, 20, 30]
f <- [subtract 5, (+5)]
return (f a)
So it's like building a tree of values and then flattening it into a single list. Initial tree:
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]
Step 1 (substitute f):
a <- (10)-----------------(20)-------------------(30)
| | |
| | |
v v v
[subtract 5 a, a + 5] [subtract 5 a, a + 5] [subtract 5 a, a + 5]
Step 2 (substitute a):
[subtract 5 10, 10 + 5, subtract 5 20, 20 + 5, subtract 5 30, 30 + 5]
And then, of course, it reduces to [5, 10, 15, 20, 25, 30, 35].
Now, as you can remember, WriterT adds an accumulator to each of your values. So at each step of flattening the tree, it will use mappend to merge those accumulators.
Let's get back to your example, pathWriterT'. To ease the understanding, I will modify it a little bit to remove the handling of self-loops and to make binding units explicit:
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
Consider an invocation of pathsWriterT' where
edges = [(1,2), (2,3), (2,4)]start = 1end = 4Once again, we can draw a tree, but it will be quite more complex, so let's do it line-by-line:
{- 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
Line 1. The type of edges is [Edge]. When you apply lift from MonadTrans to them, it becomes WriterT [Vertex] [] Edge. Remember that under the hood this is simply [(Edge, [Vertex])]. The implementation of lift for WriterT is straightforward: set accumulator to mempty for each value. Thus now we have lift edges equal to:
[ ((1,2), []) ,
((2,3), []) ,
((2,4), []) ]
And our tree is:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
For each of those (e_start, e_end) values, the following happens...
Line 2. The source vertex of an edge is bound to e_start and the target vertex is bound to e_end. guard expands to return () when its argument is True and to empty when it's False. For lists, return () is [()] and empty is []. For our monad, we have the same but with accumulators: return () is [((), [])] and empty is still [] (because there's no values to attach an accumulator to). Since we decided that start = 1, the results of evaluating guard are:
(1,2), [((), [])](2,3), [](2,4), []There are three results because we're working with each element. Let's add them to our tree:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
As you see, I wrote none in place of children nodes for (2,3) and (2,4). That's because guard didn't provide them with children nodes, it returned an empty list. And now we proceed...
Line 3. Now we use tell to expand the accumulator. tell returns the unit value, (), but with an accumulator attached to it. Since start equals to 1, the accumulator will be [1]. So let's adjust our tree:
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
Line 4. Now we call pathsWriterT' edges e_end end to recursively continue building the tree! Cool. Inside this recursive invocation: we have:
edges = old edgesstart = old e_end = 2end = old end = 4We're back at line 1. Our tree now looks like this:
(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), [])
And line 2 again... only this time, it will leave us with different nodes (as start has changed)!
(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
() <- ((), []) ((), [])
And line 3 again, now it will add [2] as accumulator.
(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])
At line 4 we recurse into pathsWriterT'.
edges = old edgesstart = old e_end = 3, 4end = old end = 4Notice that I wrote both 3 and 4 as values of e_end. That's because recursion happens in both branches:
(2,3) we will once again go create a child per edge.(2,4), however, notice that start == end holds, bringing the end to recursion. We create a child [((), [4])] because that's the result of tell [4] for our monad.(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), [])
At line 2, the guard won't let any new children to appear here, because there's no node to satisfy 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
() <-
Whew! Our tree is built. Now it's time to reduce it. I will decrease the depth of our tree by 1 at each reduction step, going bottom-up. At each reduction step I will replace the parent with the concatenated list of its children, and mappend the parent's accumulator to the accumulators of its children. Why this exact logic? Well, that's just how (>>=) is defined for our monad.
Notice that the leafs of our tree have type [((), [Vertex])] — that's the return type of pathsWriterT'. Remember that none stands for empty list [], so it has this type as well. And inner nodes have type (a, [Vertex]), where a is the type of the bound variable (I've drawn variable bindings to the left of the tree).
Step 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
Step 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])]
Step 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])]
Step 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])]
Step 5.
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
() <- ((), [1])
|
|\_________________________________
| | |
none none v
[((), [2,4])]
Step 6.
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
() <- ((), [])
|
|
v
[((), [1,2,4])]
Step 7.
(e_start, e_end) <- ((1,2), [])------((2,3), [])-----((2,4), [])
| | |
| | |
v none none
[((), [1,2,4])]
Step 8.
[((), [1,2,4])]
execWriterT will discard the values and leave only the accumulators, and now we're left with [[1,2,4]], which means that there's only one path from 1 to 4: [1,2,4].
Exercise: do the same (with pen and paper) but for edges = [(1,2), (1,3), (2,4), (3,4)]. You should get [[1,2,4], [1,3,4]].