- Do people consider the implementability of a (abstract) data structure or a data type, just like people do for implementability/computability of an algorithm? By implementability, I mean if a (abstract) data structure/type can be implemented on a real computer or abstract computer model.
Does the implementability of a (abstract) data structure/type depend on and only on
- the computability of each of its operations implemented as algorithms, and
- whether the space it requires to store each value is limited?
Does the implementability of a (abstract) data structure/type depend on in which programming language it is implemented?
Does it matter if a programming language in which it is planned to be implemented is a imperative or functional language? In other words, are the (abstract) data structures/types that can be implemented by an imperative programming language and the (abstract) data structures/types that can be implemented by a functional languages the same?
why some data structures are called "functional data structures", and even there are some books for it (e.g. https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf). Are "functional data structures" not implemented or introduced in imperative languages? Why need to distinguish between (imperative?) data structures and functional data structures?
closed as unclear what you're asking by D.W.♦, David Richerby, Raphael♦ Aug 15 '14 at 9:09
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
As I am really not sure how you define implementability, I will guess that you think of complexity of an ADT. And when I say complexity I mean time and space complexity of its operations and space complexity of the values it stores during its lifetime.
People do care that the operations are computable and preferably with low time and space overhead. Usually, there is not a single best implementation of an ADT; take a look at various implementations of a queue in a multithreaded setting. You end up with the one you assume will work best for your particular problem.
The design of a programming language can significantly influence the way ADT is implemented. For example, support for infinite streams comes built-in in Haskell, but in, say Java, you have to implement such an ADT on top of the primitives Java provides, which can be time consuming and slower than in Haskell performance wise.