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

On 19/10/06, 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 order to determine if [1..length xs] has an element at all, you have to evaluate length xs, which involves forcing the entire spine of xs, because integers can't be partially evaluated. Computing lengths of lists is a great way to introduce strictness.