[Haskell-cafe] List comparisons and permutation group code

[Brandon Moore]

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