列表理解与列表列表

Question

我在理解以下代码时遇到了问题：

treePositions :: Tree a -> [[Int]]
treePositions (Node _ ts) =
    [] : [ (i : is ) | i <- [0..(length ts - 1)],
    is <- treePositions (index ts i) ]

此函数将计算到给定树中某个位置的任何有效路径，其中每个节点的边缘都被标记为0..lastOutgoingEdge。如果理解正确，索引函数将在树的节点列表中的索引I处返回节点。

index :: [a] -> Int -> a
index :: [a] -> Int -> a
index [] i = error "invalid index"
index (x:xs) 0 = x
index (x:xs) i = ith xs (i-1) 

现在，对于给定的树木：

t1 = Node "a" [
        Node "b" [
            Node "c"[],
            Node "d"[]
        ]
     ]
t2 = Node "z" [] 

该职能将返回：

treePositions t1 == [ [], [0], [0,0], [0,1] ] 
treePositions t2 == [ [] ]

我不明白的是这部分：

[] : [ (i : is ) | i <- [0..(length ts - 1)],is <- treePositions (index ts i) ]

我的想法：

如果我有x|x <- [0..10], x < 2。这将翻译为“取[0..10]中的每一个x，而x < 2适用于它。那么，如果我在[0..(length ts - 1)]中取每一个i，这又如何返回条件的列表？”

Answer 1

在您的例子中，逗号后面的部分不是条件，而是第二个生成器。简化后的表示法如下：

> [ (a, b) | a <- [1..3], b <- [1..2] ]
> [(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)]

上面的例子说明如下：

1. 通过列表[1..3]，对于它的每一个元素，
2. 通过列表[1..2]，对于它的每一个元素，
3. 生产一个元组

此外，发电机还可以依赖先前发电机的元件，例如：

> [ (a, b) | a <- [1..3], b <- [1..a] ]
> [(1,1),(2,1),(2,2),(3,1),(3,2),(3,3)]

所以在你的情况下：

[ (i : is ) | i <- [0..(length ts - 1)],is <- treePositions (index ts i) ]

逻辑是这样的：

1. 每一次i在0..(length ts - 1)，
2. 在treePositions (index ts i)上翻阅每一个treePositions (index ts i)，
3. 并产生i : is作为结果