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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
