How does the Haskell compiler handle the 'where' statement?

Question

In the following function, I'm wondering if the compiler is clever enough to work out that x is going to remain constant, or will it compute the head of the list for every item in the list? (I'm using GHC)

allSame :: Eq a => [a] -> Bool 
allSame xs = all (==x) xs  where x = head xs

Answer 1

I think Haskell will just evaluate what's needed: So it's looking for x and finds it in the where-clause. Then I think it computes x once and does the all.

If you want to test it, you could write a function myall that does a recursion like in all (==x), but essentially just prints out the comparing element. So you'll see, if you get a new argument each time or if it stays just the same each time.

Edit:

Here's a little function to test this: myall just collects the first arguments and puts it in a list.

myall x [] = [x]
myall x xs =  x:(myall x (tail xs))

test xs = myall (x) xs where x = head xs

If you call test [1,2,3], you will see that the result is [1,1,1,1], i.e. first x is evaluated to 1, after that myall is evaluated.

Answer 2

The semantics of 'where' in GHC is that a single closure will be allocated for 'x' and shared amongst all uses. A new closure, for the function (== 'x') will be generated, and the optimizer will float it out, so that it is only generated once per traversal.

To see exactly what code is generated, check the Core (e.g. via ghc-core). GHC optimizes the code to:

M.allSame a eq xs =
    all
      (let 
         ds =
           case xs of 
             []   -> error "bad head"
             x : _-> x
            in
          \y -> x == y
         ) xs

If performance is a concern, consider using vectors, as the separate traversals will fuse, removing recursion.