trace :: String -> a -> a

この関数は参照透明ではありません。
型情報ではこの関数は純粋関数であると表明されていますが、トレース文字列の出力という副作用を有しています。
> The function is not referentially transparent:
> its type indicates that it is a pure function but it has the side effect of outputting the trace message.
http://www.haskell.org/ghc/docs/7.6-latest/html/libraries/base-4.6.0.1/Debug-Trace.html#v:trace