そもそもスタックって概念には副作用とかないような気がするんだが。
xとxsを引数にとって結合する関数ってpushしてるとは言えない？
(x:xs)からxとxsを返す関数ってpopしてるとは言えない？

副作用があるように実装している言語が多いだけのように思えるんだが。