[Haskell-cafe] List comparisons and permutation group code
David House
dmhouse at gmail.com
Thu Oct 19 12:51:17 EDT 2006
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
More information about the Haskell-Cafe
mailing list