You mean Lisp isn't purely functional, as it has rarely used functions which destructively modify cons cells and lists. The cons function itself has no side effects, so is purely functional. As long as you avoid list-modifying functions, the cons data structure and any lists built from it are purely functional data structures (i.e. their contents never change), just like in Prolog and Haskell.