In Haskell, performance and where binding

Question

I am just learning Haskell and wrote two programs from a tutorial site, such that

maximumnowhere :: (Ord a) => [a] -> a
maximumnowhere [] = error "empty"
maximumnowhere [x] = x
maximumnowhere (x:xs) = if x > maximumnowhere xs then x else maximumnowhere xs

and

maximumwhere :: (Ord a) => [a] -> a
maximumwhere [] = error "empty"
maximumwhere [x] = x
maximumwhere (x:xs) = if x > maximum' then x else maximum' where maximum' = maximumwhere xs

I thought these two programs are fairly equivalent, cause I thought, the where binding only replaces the variable with its content. but when I run it in ghci, the first one was way slower than the latter, especially for an array with length over 25. Probably, the where binding makes this huge performance difference, but I don't know why. Can anyone explain it for me?

Answer 1

No, they are not equivalent. let and where introduce sharing, which means that the value is only evaluated once. The compiler will in general not share the result of two identical expressions unless you tell it to, because it cannot in general tell on its own whether the space-time trade-off of doing this is beneficial or not.

Thus, your first program will do two recursive calls per iteration, making it O(2^n), while the second only does one per iteration, i.e. O(n). The difference between these is huge. At n = 25, the first program results in over 33 million recursive calls while the second only does 25.

So the moral of the story is that if you want sharing, you need to ask for it by using let or where.