[Haskell-cafe] Trees building

[Daniel Fischer]

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