I think bringing in the evaluator is important. It provides a really operational POV of purity. It breaks down a little bit though.

data Sigma
  = S String
  | P Sigma Sigma
  | E

eval1 :: Sigma -> IO String
eval1 (S s) = return s
eval1 (P s1 s2) = do { a <- eval1 s1; b <- eval1 s2; return (a ++ b) }
eval1 E = getLine

eval2 :: [String] -> Sigma -> String
eval2 ss (S s) = s
eval2 ss (P s1 s2) =
  let (ss1, ss2) = split ss
  in eval2 ss1 s1 ++ eval2 ss2 s2
eval2 (s:ss) E = s

split :: [a] -> ([a], [a])
split (a:b:rest) = let (as,bs) = split rest in (a:as, b:bs)

Here, Sigma is clearly not RT from the perspective of eval2, but there’s no way to define it because we can’t use Haskell’s let bindings. That said, eval2 is pure by anyone’s definition unlike eval1.

I’m also not completely sure I like this definition of purity. It’s silly to argue differences of definition, but defining purity as “preserves RT” doesn’t seem terrifically interesting. I’ve been a fan of “a function is pure if its entire effect is carried by its result”. Formally, given

trivial :: a -> ()
trivial x = x `seq` ()

a function f is pure iff trivial = trivial . f. This feels a bit finer. It, for instance, would let you talk about a pure function which isn’t referentially transparent as being one that reads from a global mutable variable. Its effect is indistinguishable from trivial if you throw away its result, but its result is not RT. Then we can talk about a function which is both RT-preserving and pure.