[Haskell-cafe] List comparisons and permutation group code

[Cale Gibbard]

On 19/10/06, David House <dmhouse at gmail.com> 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 order to determine if [1..length xs] has an element at all, you
have to evaluate length xs, which involves forcing the entire spine of
xs, because integers can't be partially evaluated. Computing lengths
of lists is a great way to introduce strictness.