AbstractDataTypes
Abstract Data Types
Abstract Data type (ADT) is a type (or class) for objects whose behavior
is defined by a set of value and a set of operations.
The definition of ADT only mentions what operations are to be performed
but not how these operations will be implemented. It does not specify how data
will be organized in memory and what algorithms will be used for implementing
the operations. It is called “abstract” because it gives an implementation
independent view. The process of providing only
the essentials and hiding the details is known as abstraction.
You can see that these definitions do not specify how these ADTs will be
represented and how the operations will be carried out. There can be different
ways to implement an ADT, for example, the List ADT can be implemented using
singly linked list or doubly linked list. Similarly, stack ADT and Queue ADT
can be implemented using lists.
Data abstraction replicate how we think about the world. For example,
when you want to drive a car, you don’t need to know how the engine was built
or what kind of material the tires are made of. You just have to know how to
turn the wheel and press the gas pedal. To facilitate data abstraction,
you will need to create two types of functions: constructors and selectors.
Constructors are functions that build the abstract data type. Selectors
are functions that retrieve information from the data type.
For example, say you have an abstract data type called city. This city
object will hold the city’s name, and its latitude and longitude. To create a
city object, you’d use a function like
city = makecity (name, lat, lon)
To extract the information of a city object, you would use functions
like
· getname(city)
· getlat(city)
· getlon(city)
The following pseudo code will compute the distance between two city
objects:
distance(city1, city2):
lt1, lg1 := getlat(city1), getlon(city1)
lt2, lg2 := getlat(city2), getlon(city2)
return ((lt1 - lt2)**2 + (lg1 - lg2)**2))1/2
In the above code read distance(), getlat() and getlon() as functions
and read lt as latitude and lg longitude. Read := as “assigned as” or “becomes”
lt1, lg1 := getlat(city1), getlon(city1)
is read as lt1 becomes the value of getlat(city1) and lg1 becomes the
value of getlont(city1).
Notice that you don’t need to know how these functions were implemented.
You are assuming that someone else has defined them for us.
It’s okay if the end user doesn’t know how functions were implemented.
However, the functions still have to be defined by someone.
Let us identify the constructors and selectors in the above code
As you already know that Constructors are functions that build the
abstract data type. In the above pseudo code the function which creates the
object of the city is the constructor.
city = makecity (name, lat, lon)
Here makecity (name, lat, lon) is the constructor which creates the
object city.
Selectors are nothing but the functions that retrieve information from
the data type. Therefore in the above code
· getname(city)
· getlat(city)
· getlon(city)
are the selectors because these functions extract the information of the
city object
Now let us consider one more example to identify the constructor and
selector for a slope.Read - - as comments.
- constructor
makepoint(x, y):
return x, y
- selector
xcoord(point):
return point[0]
-selector
ycoord(point):
return point[1]
Representation of Abstract datatype using Rational numbers
The basic idea of data abstraction is to structure programs so that they
operate on abstract data. That is, our programs should use data in such a way,
as to make as few assumptions about the data as possible. At the same time, a
concrete data representation is defined as an independent part of the program.
Note
In concrete data representation, a definition for each function is known
Any program consist of two parts. The two parts of a program
are, the part that operates on abstract data and the part that defines a
concrete representation, is connected by a small set of
functions that implement abstract data in terms of the concrete representation.
To illustrate this technique, let us consider an example to design a set of
functions for manipulating rational numbers.
Example
A rational number is a ratio of integers, and rational numbers
constitute an important sub-class of real numbers. A rational number such as
8/3 or 19/23 is typically written as:
<numerator>/<denominator>
where both the <numerator> and <denominator> are
placeholders for integer values. Both parts are needed to exactly characterize
the value of the rational number. Actually dividing integers produces a float
approximation, losing the exact precision of integers.
8/3 =2.6666666666666665
However, you can create an exact representation for rational numbers by
combining together the numerator and denominator.
As we know from using functional abstractions, we can start programming
productively before you have an implementation of some parts of our program.
Let us begin by assuming that you already have a way of constructing a rational
number from a numerator and a denominator. You also assume that, given a
rational number, you have a way of selecting its numerator and its denominator
component. Let us further assume that the constructor and selectors are also
available.
We are using here a powerful strategy for designing programs: 'wishful
thinking'. We haven't yet said how a rational number is represented, or how
the constructor and selectors should be implemented.
Note
Wishful Thinking is the formation of beliefs and making decisions
according to what might be pleasing to imagine instead of by appealing to
reality.
Example: An ADT for rational numbers
- constructor
- constructs a rational number with numerator n, denominator d
rational(n, d)
- selector
numer(x) → returns the numerator of rational number x
denom(y) → returns the denominator of rational number y
Now you have the operations on rational numbers defined in terms of the
selector functions numer and denom, and the constructor function rational, but
you haven't yet defined these functions. What you need is some way to glue
together a numerator and a denominator into a compound value.
The pseudo code for the representation of the rational number using the
above constructor and selector is
x,y:=8,3
rational(n,d)
numer(x)/numer(y)
- - output : 2.6666666666666665
Ref: https://www.brainkart.com/article/Representation-of-Abstract-datatype-using-Rational-numbers_37203/