Re: Understanding tail recursion and trees Classic List Threaded 8 messages Open this post in threaded view
|

Re: Understanding tail recursion and trees

 Hi, Thanks to Miguel for pointing out my silly error. So at least my understanding of tail recursion is correct :) So then the question becomes: what *is* the best way to write this function? One version I can think of is > ecount :: [Tree] -> Integer -> Integer > ecount []                  acc = acc > ecount (Leaf _       : ts) acc = ecount ts \$! (acc + 1) > ecount (Branch t1 t2 : ts) acc = ecount (t1 : t2 : ts) acc which essentially maintains an explicit stack and runs on all trees. Are there better ways to do this? Thanks again and sorry for my mistake, Edsko _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: Re: Understanding tail recursion and trees

 On Thu, May 1, 2008 at 9:32 AM, Edsko de Vries <[hidden email]> wrote: >  So then the question becomes: what *is* the best way to write this function? I guess it would be simpler to have the counter on the data type and a smart branch constructor: > data Tree = Leaf Integer | Branch Integer Tree Tree > > count :: Tree -> Integer > count (Leaf _)       = 1 > count (Branch c _ _) = c > > branch :: Tree -> Tree -> Tree > branch left right = Branch (count left + count right) left right > > gentreeL :: Integer -> Tree > gentreeL 0 = Leaf 0 > gentreeL n = branch (gentreeL (n-1)) (Leaf 0) etc. -- Felipe. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

Re: Re: Understanding tail recursion and trees

Open this post in threaded view
|

Re: Re: Understanding tail recursion and trees

Open this post in threaded view
|

Re: Re: Understanding tail recursion and trees

Open this post in threaded view
|