I may have missed this in the discussion so far, but it seems we could
use a summary.
In short: isIdentity does not check for exact equivalence, only a
prefix equivalence. That's why it doesn't exhibit the same time/space
behavior as a reformulation based on full equivalence.
More verbosely: isIdentity works lazily because it effectively
determines if the list xs has the same prefix as the infinite list
[1..]. It is not actually an equivalence check. But isIdentity' is an
equivalence check and it must construct the finite list [1..(length
xs)]. As has been discussed, the length demands the spine of the
entire xs list, thereby incurring the delay you originally noticed.
Nick
On 10/19/06, Robert Dockins <[EMAIL PROTECTED]> wrote:
On Oct 19, 2006, at 12:51 PM, David House wrote:
> On 19/10/06, Mikael Johansson <[EMAIL PROTECTED]> wrote:
>> isIdentity xs = all (\(i,j) -> i==j) (zip [1..] xs)
>> isIdentity' xs = xs == [1..(length xs)]
>>
>> Then
>> isIdentity 1:3:2:[4..100000]
>> finishes in an instant, whereas
>> isIdentity' 1:3:2:[4..100000]
>> takes noticable time before completing.
>
> Why is this so? I'd have thought that the equality function for lists
> only forces evaluation of as many elements from its arguments as to
> determine the answer. In other words, the computation should go
> something like this:
I wondered this too for a minute. I'm pretty sure that the answer is
that the 'length' function is the culprit, not (==).
Calling 'length' forces the spine of 'xs', which accounts for the
extra computation.
Just say 'no' to length (when you want laziness).
[snip]
> --
> -David House, [EMAIL PROTECTED]
Rob Dockins
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
-- TMBG
_______________________________________________
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
