Am Dienstag, 26. Februar 2008 18:29 schrieb Krzysztof Skrzętnicki:
Hi everyone
I'm trying to write a piece of Haskell code, but for some reason I can't make it working. I'm asking for your help in finding a bug in
this code:
import Data.Tree import Data.List
expandTree :: Int -> [(Int,Int)] -> ((Tree Int),[(Int,Int)]) expandTree rootLabel [] = ((Node rootLabel []),[]) -- probably obsolete
line
expandTree rootLabel nodePairs = ((Node rootLabel forest),unused) where (marked,unmarked) = partition (\ (x,y) -> (x==rootLabel) ||
(y==rootLabel)) nodePairs
(forest,unused) = foldl (\ (forestAcc, unusedPairs) node -> let (a,b) =
expandTree node unused in ((a:forestAcc),b) ) ^^^^^^^^^^^^ That should be unusedPairs instead of unused, with that change, I get *BuildTrees> expandTree 1 [(1,2)] (Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = []}]},[]) *BuildTrees> expandTree 1 [(2,3)] (Node {rootLabel = 1, subForest = []},[(2,3)]) *BuildTrees> expandTree 1 [(1,2),(3,4)] (Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = []}]},[(3,4)])
Cheers, Daniel
([],unmarked) (map (\(o,p)-> if o == rootLabel then p else o )
marked)
It is supposed to create tree with root labeled with rootLabel, while nodePairs is a description of a tree. If a list is not exhausted, the remaining should be returned. It should work so that:
expandTree 1 [(1,2)] == ((Node 1 [(Node 2 [])]),[]) expandTree 1 [(2,3)] == ((Node 1 []),[(2,3)]) expandTree 1 [(1,2),(3,4)] == ((Node 1 [(Node 2 [])]),[(3,4)])
However, the code loops. Any clues?
Thanks in advance.
Regards Christopher Skrzętnicki