[Haskell-cafe] List comparisons and permutation group code

[Nicolas Frisby]

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.

Nick

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).
>
> [snip]
>
>
> > --
> > -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
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>