Although equal? treats the two as the *same*, they're different lists because if we modify one (e.g by set-car!) the other won't be affected.
So here comes another question: when we say a function always give the same output for the same input, what the *same* means here? ídentity or equality?
If you don't have set-car!, then identity and equality are impossible to differentiate. And haskell doesn't have set-car!. However, as was noted, it does have something like mutable pointers via IORef, and sure enough, you can do pointer comparisons with them: h <- newIORef 12 h' <- newIORef 12 print $ h == h --> True print $ h == h' --> False Since they're pointers, to compare by value you have to explicitly derefence them: print =<< liftM2 (==) (readIORef h) (readIORef h') --> True If you're wondering about the implementation of "(1:[], 1:[])", ghc might be smart enough to do CSE in this case and hence use the same memory for both lists, but in general CSE doesn't happen to avoid accidental recomputation. There's some stuff in the ghc manual about lambda and let lifting that describes when CSE will and won't happen. I wouldn't count on it in general, but I don't read core well enough to tell. Maybe someone who knows more about core can help me here: a = \ (eta_azv :: State# RealWorld) -> case a24 stdout lvl7 eta_azv of wild_aFu { (# new_s_aFw, a103_aFx #) -> $wa13 stdout '\n' new_s_aFw } There are lots of apparently undefined variables, like the function 'a24'. But it looks like the pair should come from 'lvl7', which is chained all the way down to 'lvl' like so: lvl :: Integer lvl = S# 1 lvl1 :: [Integer] lvl1 = : @ Integer lvl ([] @ Integer) lvl2 :: ShowS lvl2 = showList lvl1 lvl3 :: [ShowS] lvl3 = : @ ShowS lvl2 ([] @ ShowS) lvl4 :: [ShowS] lvl4 = : @ ShowS lvl2 lvl3 lvl5 :: [Char] lvl5 = : @ Char a2 ([] @ Char) lvl6 :: String lvl6 = foldr1 @ (String -> String) lvl16 lvl4 lvl5 lvl7 :: [Char] lvl7 = : @ Char a lvl6 So it *looks* like there's only one list created in 'lvl1', but I can't see where it's turning into a tuple, and I don't understand the ' = : ' stuff, as in 'lvl5 = : @ Char a2 ([] @ Char)'. 'lvl5' is a Char resulting from the application of 'a2' to ""? The code, btw, was 'main = print (1:[], 1:[])'.