Abstract Data Structures

[Robert Will]

hi,

Abstract Data Types plus Data Structures gives Abstract Data Structures.

Divide by Conquer is a technique that every Computer Science Undergraduate
learns: to sort a listm sort each of its halves then merge.  This is what
I call "Computational Divide and Conquer" and it is an important algorithm
design strategy.  Algorithm Design and Programming were once considerd the
same and they were the heart of Computer Science.

Nowadays, we get our algorithms from libraries and are instead faced with
the complexity of programming applications.  It is essential that we
divide our programs into smaller parts and specify the contracts between
those parts.  This is what I call "Informational Divide and Conquer".

(The words "informational" vs "calculational" go back to Dijkstra who said
that a refinement step is good if it makes either "computational or
informational progress".  The former meaning decrease a loop or recursion
variant, the latter meaning to get simpler assertions.  I believe that the
Art or Science or whatnot of Programming will make a leap forward, when it
learns to profit from Dijkstras heritage.)

-- Abstraction in Programming firmly rests on the separation
-- of Specification and Implementation.  Implementations in functional
-- languages have always been on a "higher level", many of them
-- serving as their own specifications.  (Just take a look into
-- Haskell's Prelude and try to specify one of the functions.)  Due to
-- take higher-level of built-in abstraction, they have resisted for a
-- long time the use of programmer-defined abstraction, that is, the
-- separation of Specification and Implementation.  (Which is by the
-- way also the basis of well-used polymorphism.)  The main data
-- structure of the Haskell programmer is still the same as the one
-- from the first functional language in 1958.  This file might
-- convince the reader that a good functional language should have
-- more to offer.
http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/AlgebraBasic.hs


I have always considered it an advantage that almost all of the Prelude
functions are there own specifications.  If you had a question, just go
ask the code.  This approach, however, doesn't scale.  If we want to
include other data structures than functional stacks into a library (or
how did you call that structure with the basic axioms
   head (x : xs) = x         tail (x : xs) = xs        ?)
we must also include abstraction.

I don't know why I write such philosphical stuff, actually I only wanted
to annouce my little project and ask for comments:
http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/

Anyway, it doesn't hurt to remind every now and then.  I would especially
like interested people to have a look at AlgebraBasic.hs which I think is
quite evolved and even already contains the words "standard proposal".

Robert