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@gmail.com