[Haskell-cafe] Re: Problems with strictness analysis?

[Bulat Ziganshin]

Hello Luke,

Thursday, November 6, 2008, 2:34:36 AM, you wrote:

> The example being discussed in this thread is a good one:

>   sum [1..10^8] + length [1..10^8]

> With Haskell's semantics, we know we can write this as:

>   let xs = [1..10^8] in sum xs + length xs

> But it causes a change in memory *complexity*, so in some sense these
> two sentences are not equal.  What is the theory in which we can
> observe this fact?  Is it possible to give a simple denotational
> semantics which captures it?

i'm not a mathematician, but why you can't explore term rewriting
system? it has some graph at initial stage and modifies it until normal
form is reached. graphs representing first and second expression are
different (first is tree while second have two two links to [1..10^8]
node) and this oes to difference between their evaluation process. on
the every step of rewriting of first graph itssize remains O(1), while
second graph during rewriting grows up to O(n) size


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com