On 19/10/06, Mikael Johansson <[EMAIL PROTECTED]> 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, [EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
