Re: Re: [Haskell-cafe] List comparisons and permutation group code

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 wrote:

On Oct 19, 2006, at 12:51 PM, David House wrote:

...

On 19/10/06, Mikael Johansson 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, dmhouse@gmail.com

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