Sorry newb question here, but how does Haskell know not to apply referential transparency to e.g. readLn or when putStrLn-ing a same string twice? Is it because IO is involved? IOW, will not the compiler apply referential transparency to functions returning IO?
The IO type is defined as:
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))
Notice is very similar to the State Monad where the state is the state of the real world, so imho you can think of IO as referentially transparent and pure, what's impure is the Haskell runtime (interpreter) that runs your IO actions (the algebra).
Take a look at the Haskell wiki, it explains IO in greater detail: IO Inside