Nicolas Frisby wrote:
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.
Both versions check whether the provided list matches a prefix of [1..], it's just that the formulation with == is written to construct the prefix and then compare, while the version with zipWith (==) relies on zip taking just a prefix of the longer list. The reason the version using == is bad is because it is strict in the (spine of) the first list, because you need to compute length xs before you can begin constructing [1..length xs]. if you arrange to lazily construct the reference list, the functions should be roughly equivalent: isIdentity xs = xs == takeLengthOf xs [1..] where takeLengthOf xs ys = zipWith const ys xs for finite lists, takeLengthOf xs ys == take (length xs) ys Brandon