[Haskell-cafe] List comparisons and permutation group code

[David House]

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:

(We're comparing let xs = 1:3:2:[4..100000] in xs == [1..length xs])
<thunk> == <thunk>
1:<thunk> == 1:<thunk> (Evaluate first element to reveal a cons cell)
1:3:<thunk> == 1:2:<thunk> (Evaluate second element)
False

Why doesn't this happen? This is how I imagine the computation
unfolding, drawing upon the definitions of == and &&:

(1): []     == []     = True
(2): (x:xs) == (y:ys) = x == y && xs == ys
(3): _xs    == _ys    = False

(1): True  && x		=  x
(2): False && _		=  False

xs == ys
x:xs == y:ys (Evaluate cons cell)
x == y && xs == ys (Equation (2) of ==)
1 == 1 && xs == y (Evaluate head of lists)
True && xs == ys
xs == ys (Equation (1) of &&)
x:xs == y:ys (Evaluate next cons cell)
x == y && xs == ys
3 == 2 && xs == ys (Evaluate next elements)
False && xs == ys
False (Equation (2) of &&)

As an aside, here's output from Hugs that shows the difference quite noticably:

Hugs.Base> let xs = 1:3:2:[4..100000] in xs == [1..length xs]
False
(3400043 reductions, 4396061 cells, 5 garbage collections)
Hugs.Base> let xs = 1:3:2:[4..100000] in all (uncurry (==)) (zip [1..] xs)
False
(70 reductions, 148 cells)

-- 
-David House, dmhouse at gmail.com