haskell - 从边列表构造树: missing Leaf nodes

Question

我编写了下面的代码来构造一棵树，该树具有给定的顶点以及顶点之间的连接列表。

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)] 给出me 节点 1 [节点 2 [节点 3 []，节点 4 []]，节点 5 [节点 6 []，节点 7 []]]

我正在 OS X 10.8.2 上运行 GHCi 版本 7.4.1。

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

Answer 1

一个快速解决方法是在决定是否构建 Leaf 还是 Node 之前检查 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)])
()

如您所见，第二个参数中的列表不为空，这就是为什么它与函数的第一个情况不匹配的原因，因此您要么需要像我的示例中那样添加一些额外的检查，要么进行确保过滤掉其余的连接。