Purely functional data structures are often represented in a different way than their [[imperative programming|imperative]] counterparts.<ref>[http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/purely-functional-data-structures ''Purely functional data structures''] by [[Chris Okasaki]], [[Cambridge University Press]], 1998, {{ISBN|0-521-66350-4}}</ref> For example, an [[array data structure|array]] with constant-time access and update is a basic component of most imperative languages. Many imperative data structures, such as the [[hash table]] and [[binary heap]], are based on arrays. An array can be replaced by a [[Map (computer science)|map]], ora random access list, or a tree, which admits a purely functional implementation, but access and update operations may run in [[logarithmic time]]. Purely[[Persistent functionaldata structure|Persistent data structures]] canhave bethe implementedproperty inof imperativekeeping andprevious object-orientedversions languages,of butthemselves their timeunmodified, and/orspaceare performanceused mayas befunctional inferioralternatives to thattheir ofimperial data structures lacking purely functional propertiescounterparts.{{cn|date=July 2017}}
==Ensuring that a data structure is purely functional==
