[Haskell-cafe] List comparisons and permutation group code
brandonm at yahoo-inc.com
Thu Oct 19 15:51:22 EDT 2006
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
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
More information about the Haskell-Cafe