Re[Haskell-cafe] cursive referencing

Ryan Ingram ryani.spam at gmail.com
Sat Jan 31 05:46:07 EST 2009


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-belka at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list