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 []]]

OSX10.8.2でGHCiバージョン7.4.1を実行しています。

最初の例（正しい）でLeafを2回取得する理由はわかりませんが、2番目の例（正しくない）ではサブツリーリストが空のノードです。

4

1 に答える 1

3

簡単な解決策は、を構築するかどうかを決定する前に、が空であるかどうかを確認することですotherTrees。LeafNode

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)])
()

ご覧のとおり、2番目の引数のリストは空ではないため、関数の最初のケースと一致しないため、私の例のようにチェックを追加するか、次のことを確認する必要があります。残りの接続を除外します。

于 2012-10-26T03:28:48.507 に答える