-1
$\begingroup$
  1. 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.
  2. 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?
  3. 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?

$\endgroup$

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.

  • 1
    $\begingroup$ What do you mean by implementability? What makes you think that people consider the implementability of an algorithm? Actually, I can't tell what you are talking about or what you are asking. Why don't you tell us where you ran across the term "implementability", what you mean by it (give us a definition and/or example), and what research you have done? Every data structure I've ever seen can be implemented: its specification comes with pseudocode that tells you how to implement it. $\endgroup$ – D.W. Aug 15 '14 at 0:36
  • 1
    $\begingroup$ What do you define as implementability? Also, have you considered that the operations of a data structure/type are algorithms? $\endgroup$ – ZeroUltimax Aug 15 '14 at 0:36
  • $\begingroup$ @D.W. I'm assuming by implementability Tim means how easy would it be to implement this into a programming language: such as in the sense that linked-list are easier to implement than Red-Black Trees. But obliviously what would depend on what features XYZ language has. $\endgroup$ – Spencer Wieczorek Aug 15 '14 at 0:43
  • 1
    $\begingroup$ You have been asking for long enough to have learned by now: only one question per post, please. I count seven question in this post. (Also, I wonder when you'll pick up on me editing away your "thanks" clause. It's unncessary and generally discouraged on SE; just upvote and accept to show your thanks.) $\endgroup$ – Raphael Aug 15 '14 at 9:08
  • 1
    $\begingroup$ On a real computer, almost nothing can be implemented since they are finite automata. If you virtually extend them to be Turing-equivalent, you are left with the usual notion of computability. Hardness of implementation is a subjective criterion. So I truly don't get where this question can possibly lead. $\endgroup$ – Raphael Aug 15 '14 at 9:09
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. (1) What I mean by "implementability" is whether an ADT can be implemented or not. i do not assume it can be implemented, and therefore I didn't ask the complexity of implementing it although I am also interested in it. (2) In the sense of "implementability" in (1), I wonder if a imperative langauge and a functional language can implement the same set of ADTs? $\endgroup$ – Tim Aug 15 '14 at 2:00
  • $\begingroup$ Well, I would define implementability as computability. Efficient computability would then be implementability plus low space and time complexities of its operations and data. Both general purpose imperative and functional programming languages are Turing-complete so they can carry the same computations, just in a different way. $\endgroup$ – bellpeace Aug 15 '14 at 2:09
  • $\begingroup$ Then i would wonder why some data structures are called "functional data structures", and even there are some books for it (e.g. 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? $\endgroup$ – Tim Aug 15 '14 at 2:19
  • $\begingroup$ This book basically gives you the answer to your last bullet. Among some other things, he shows how to implement common ADTs with a functional programming language, and especially if one has lazy evaluation on his disposal. That is where the terminology comes from. Also, I would differentiate between ADT and functional/imperative data structure: note the "abstract" in ADT. $\endgroup$ – bellpeace Aug 15 '14 at 4:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.