On 19/10/06, Mikael Johansson
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@gmail.com