1) yes, but that's sumAA's fault, not the data structure; sumAA isn't tail recursive so it has to build a much bigger stack:
x + (y + (z + (...))) whereas it could run in constant space if it did this instead: (...((x + y) + z) + ...) Usually this transformation is done by passing an accumulator holding the "result so far" at each iteration. 2) That was the point of using Debug.Trace in my example. Notice that "eval_aa" and "eval_bb" only get printed once; they get output during the construction of the AA and BB objects during evaluation. Since you only see them once, you know that there isn't any further creation of data; it's really just a circular data structure with pointers back and forth. -- ryan On Fri, Jan 30, 2009 at 1:48 PM, Belka <lambda-be...@yandex.ru> wrote: > > Great thanks, Ryan and Yevgeny! > > 1. For "sumAA 10 $ f 1 2" and for "sumAA 1000 $ f 1 2" - does the used > memory amounts differ? > 2. Does it create in memory only 2 data objects, or creates 10s and 1000s > and garbage collects unneeded? > > ------ > > Also consider > fix (\p -> (AA somedata1 $ snd p, BB somedata2 $ fst p)) > and my mod (added "some_very_expensive_f") > fix (\p -> (AA (some_very_expensive_f somedata1) $ snd p, BB > (some_very_expensive_f somedata2) $ fst p)) > > 2. Does the sumAA evaluates this "some_very_expensive_f" every iteration of > recursion, or is it evaluated only once? > > Belka > > ---------------------------- >>Your definition with "fix" isn't lazy enough, so it goes into an >>infinite loop. You need to match lazily on the pair; here's a better >>body for "fix": >> >>fix (\p -> (AA somedata1 $ snd p, BB somedata2 $ fst p)) >> >>To prove that the structure really turns out cyclic, you can use > Debug.Trace: >> >>import Debug.Trace (trace) >>import Data.Function (fix) >> >>data AA = AA Int BB deriving Show >>data BB = BB Int AA deriving Show >> >>f = \data1 data2 -> fst $ fix $ \p -> >> (trace "eval_aa" $ AA data1 $ snd p, >> trace "eval_bb" $ BB data2 $ fst p) >> >>sumAA 0 _ = 0 >>sumAA n (AA v bb) = trace "sumAA" (v + sumBB (n-1) bb) >>sumBB 0 _ = 0 >>sumBB n (BB v aa) = trace "sumBB" (v + sumAA (n-1) aa) >> >>main = print $ sumAA 10 $ f 1 2 >> >>*Main> main >>eval_aa >>sumAA >>eval_bb >>sumBB >>sumAA >>sumBB >>sumAA >>sumBB >>sumAA >>sumBB >>sumAA >>sumBB >>15 > -- > View this message in context: > http://www.nabble.com/Recursive-referencing-tp21722002p21756221.html > Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
