CODEWITHSUNDEEP
haskellghc
nedned
nedned

Reputation: 3707

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

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

Upvotes: 3

Views: 579

Answers (2)

phimuemue
phimuemue

Reputation: 35973

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.

Upvotes: 0

Don Stewart
Don Stewart

Reputation: 137937

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.

Upvotes: 12

Related Questions