Home Articles

从边列表构造树:缺少叶节点

Asked
Viewed 1775 times
2

我编写了下面的代码来构造一个给定顶点的树,给出顶点之间的连接列表 .

type Connection = (Int,Int)
data Tree = Leaf Int | Node Int [Tree] deriving (Eq,Read,Show)

makeTree :: Int -> [Connection] -> Tree
makeTree x [] = Leaf x
makeTree indx connections =  Node indx otherTrees where
  otherTrees = [makeTree i cx | i <- directConnections, let cx = removeConnectionsTo indx connections]
  directConnections = map (\(x,y) -> if (x == indx) then y else x) $ filter (\(x,y) -> x == indx || y   == indx) connections

removeConnectionsTo :: Int -> [Connection] -> [Connection]
removeConnectionsTo indx = filter (\(x,y) ->    x /= indx && y /= indx)

出于某种原因,下面的输入给出了令人惊讶的不同结果:

makeTree 1 [(1,2),(1,3)] 给了我 Node 1 [Leaf 2,Leaf 3]

makeTree 1 [(1,2),(1,5),(2,3),(2,4),(5,6),(5,7)] 给了我 Node 1 [Node 2 [Node 3 [],Node 4 []],Node 5 [Node 6 [],Node 7 []]]

我在OS X 10.8.2上运行GHCi,版本7.4.1 .

我不明白为什么我在第一个例子中得到Leaf两次(正确)但在第二个例子中有空子树列表的节点(不正确) .

1 Answer

  • 3

    快速解决方法是在决定是否构建 LeafNode 之前检查 otherTrees 是否为空 .

    makeTree indx connections
      | null otherTrees = Leaf indx
      | otherwise       = Node indx otherTrees
      where ...
    

    要了解这里发生了什么,让我们添加一些仪器:

    import Debug.Trace
    
    makeTree :: Int -> [Connection] -> Tree
    makeTree ix cs | traceShow (ix, cs) False = undefined
    makeTree x [] = ... -- leave rest of the function as before
    

    现在将其加载到GHCi中,让我们看看递归调用是什么:

    > import Control.DeepSeq
    > (show $ makeTree 1 [(1,2),(1,5),(2,3),(2,4),(5,6),(5,7)]) `deepseq` ()
    (1,[(1,2),(1,5),(2,3),(2,4),(5,6),(5,7)])
    (2,[(2,3),(2,4),(5,6),(5,7)])
    (3,[(5,6),(5,7)])
    (4,[(5,6),(5,7)])
    (5,[(2,3),(2,4),(5,6),(5,7)])
    (6,[(2,3),(2,4)])
    (7,[(2,3),(2,4)])
    ()
    

    如您所见,第二个参数中的列表不为空,这就是为什么它与您的函数的第一个案例不匹配,因此您需要在我的示例中添加一些额外的检查,或者确保您过滤掉其余的连接 .

Related