[Haskell-cafe] Trees building

Krzysztof Skrzętnicki gtener at gmail.com
Tue Feb 26 12:29:50 EST 2008


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) )
>                        ([],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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080226/b453b484/attachment.htm


More information about the Haskell-Cafe mailing list