algorithms and ADTs (was Re: efficient idiomatic queue?)

[Quinn Dunkan]

On Wed, 16 Jan 2002 09:26:33 +0100, Alex Martelli <aleax at aleax.it> wrote:
>"Aahz Maruch" <aahz at panix.com> wrote in message
>news:a22rj5$bs6$1 at panix3.panix.com...
>> In article <a20osj$78u$1 at serv1.iunet.it>, Alex Martelli <aleax at aleax.it>
>wrote:
>> >
>> > [...]
>>
>> Um, what's an ADT?
>
>Sorry -- I should not have used a three-letter-acronym (TLA) without
>expanding it at least once, no matter how well-known I could assume
>it to be to the specific poster I was responding to.
>
>ADT = "Abstract Data Type".  When teaching algorithms and data
>structures, one approach is to "implement" an algorithm in terms
>of abstract operations on some underlying data type, each operation
>defined in terms of its just-as-abstract semantics and performance
>characteristics.  The issue of *implementing* an ADT in concrete
>terms is then neatly separated from that of *using* it.  As far as
>I know the original idea came from abstract algebra, where one
>does much the same with abstract structures -- one separates the
>issue of "what can I prove about a monoid" (the latter being
>abstractly defined in terms of its axioms) from the issue of
>proving whether a given algebraic structure is indeed a monoid.
>
>Of course, ADT's also mesh well with the concept of separation
>between interface and implementation as used in actual software
>design.  Performance characteristics are rarely specified in
>the latter case, but there are important exceptions (for example,
>C++'s Standard Library does have O(N) performance specs for
>various operations as part of its overall specifications).

Aha!  I always thought ADT stood for "Algebraic Data Type" and assumed people
were talking about haskell / ML-ish types, although I never had a very clear
idea of what they were supposed to exactly be (value semantics?).  And fp
advocates would say things like "behold the power of adts, blah blah".  And
then Limbo goes and has an adt keyword in an imperative context...

Thanks for the description!