[Haskell-cafe] List comparisons and permutation group code

Robert Dockins robdockins at fastmail.fm
Thu Oct 19 14:28:49 EDT 2006

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

More information about the Haskell-Cafe mailing list