[Haskell-cafe] List comparisons and permutation group code
nicolas.frisby at gmail.com
Thu Oct 19 15:40:00 EDT 2006
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.
More verbosely: isIdentity works lazily because it effectively
determines if the list xs has the same prefix as the infinite list
[1..]. It is not actually an equivalence check. But isIdentity' is an
equivalence check and it must construct the finite list [1..(length
xs)]. As has been discussed, the length demands the spine of the
entire xs list, thereby incurring the delay you originally noticed.
On 10/19/06, Robert Dockins <robdockins at fastmail.fm> wrote:
> On Oct 19, 2006, at 12:51 PM, David House wrote:
> > On 19/10/06, Mikael Johansson <mikael at johanssons.org> 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 other words, the computation should go
> > something like this:
> I wondered this too for a minute. I'm pretty sure that the answer is
> that the 'length' function is the culprit, not (==).
> Calling 'length' forces the spine of 'xs', which accounts for the
> extra computation.
> Just say 'no' to length (when you want laziness).
> > --
> > -David House, dmhouse at gmail.com
> Rob Dockins
> Speak softly and drive a Sherman tank.
> Laugh hard; it's a long way to the bank.
> -- TMBG
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe