Questions tagged [abstract-data-types]
The abstract-data-types tag has no usage guidance.
45
questions
-2
votes
1
answer
42
views
Is it true to say that machine languages have some degree of abstraction?
I think anyone would agree that assembly languages ("threshold languages") have some very little abstraction but is it true to say that also machine languages have some degree of abstraction?...
- 1
2
votes
0
answers
208
views
What's the difference between the two abstract data types collection vs container?
From abstract data types in wiki, I'm reading about two types: collection and container. Can anyone supply a better detailed difference between the difference between the two?
https://en.wikipedia.org/...
- 123
0
votes
4
answers
193
views
Are integers an abstract data type?
I'm trying to understand whether integers are an abstract data type.
The Wikipedia article starts out by saying that integers are not an ADT:
In practice, many common data types are not ADTs, as the ...
- 123
2
votes
0
answers
54
views
Differences between a computation model and an abstract data type
I am wondering about the difference between an abstract data type (ADT) and a computation model.
As I understand them:
A computation model defines the basic unit of computation, that is, what can be ...
- 121
1
vote
2
answers
114
views
Is there a data structure for lazy-loading time-series data?
I am writing a UI that needs to display a chat log, similar to Slack and Discord. In addition to being able to scroll and lazy-fetch additional pages in either direction, I need to be able to jump to ...
0
votes
0
answers
36
views
Are arrays “more abstract” than stacks or queues?
It seems to me that an array can be used as a stack or a queue and for various other things.
In my mind this makes an array a higher order abstraction compared to those other two.
Is this an ...
- 111
0
votes
0
answers
98
views
Find a bipartition of points using blackbox
Suppose given $n$ pair of points $P=\{(p_1,q_1),\dots,(p_n,q_n)\}$ in the plane that each pair $(p_i,q_i)\in \mathbb{R}^2$ can't belong to the same group. We want to partition points into $K$ groups ...
user146750
-1
votes
1
answer
47
views
Can a data abstraction use a class as a field, parameter, or return type?
I think that everyone will agree that the following class achieves data abstraction (hiding of its internal representation):
...
- 113
1
vote
0
answers
104
views
Textbook on Abstract Data Types
I'm looking for a textbook or reference material to learn about the theory of abstract data types, the ways in which they are specified (axiomatic specification vs abstract model), imperative vs ...
user132513
2
votes
1
answer
82
views
Is a system of equations derived from mutually recursive ADTs always uniquely solvable?
After looking at Can a computer determine whether a mathematical statement is true or not? for a while, I worry we may be into incompleteness/halting problem territory with this question, so an answer ...
- 645
1
vote
1
answer
74
views
write adt for stack operations
Ok, I dont understand whats the difference between:
write code for stack operations and write adt for stack operations?
lets say the operation is push() and pop(). So what different code is to be ...
- 13
2
votes
1
answer
171
views
How do type classes make ad-hoc polymorphism less ad hoc?
The title of the paper that introduced type classes is "How to make ad-hoc polymorphism less ad hoc".
It seems the type classes approach is being compared to how OOP does ad-hoc polymorphism....
- 346
0
votes
0
answers
620
views
Monotone priority queues
I'm a little confused about how monotone priority queues work.
As far as I understand:
A queue is a FIFO data structure
A priority queue is a queue where the current element of highest (or lowest) ...
0
votes
3
answers
423
views
Formal definition of the Dynamic Array - what is the Dynamic Array
I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points.
...
0
votes
0
answers
49
views
What is the difference between a Type and an Abstract Type?
In my data structures course we are given definitions for Type and Abstract Type but they confuse me.
A type is a set of values and the operations you can do on them. The set of operations is ...
- 123
0
votes
0
answers
156
views
Was there an attempt to create a programming language aimed for maximal abstraction?
I am trying to understand if a programming language can have totally or almost totally the abstraction level shared between generally all human languages so that it would allow a human to code a ...
user109446
2
votes
0
answers
17
views
Abstract data types (model, principle of no junk)
I have the following abstract data structure
Now i have to find a model that satisfies the principle of no junk and proof that
Could someone advise me to get to a solution and to understand the ...
- 51
2
votes
0
answers
97
views
Simulating extensible sums with dependent types?
ML-style languages have a concept of "extensible" or "open" sum types, where variants can be declared at any point, and there's not a fixed number of constructors for the type. They're usually used to ...
- 29.7k
1
vote
1
answer
29
views
Where is the original literature for the specification of an Associative Array ADT?
I'm looking for the formal specification for the Abstract Data Type Algebra for the Associative Array, Associative List (AKA multimap), and other similar ADT to cite for use in a data specification ...
1
vote
1
answer
41
views
What is the specific name for basic data types?
What is the specific name for data types such as integer, string, real (the basic ones)?
2
votes
0
answers
26
views
Metrics for measuring and scoring automated “code analysis”?
I am writing various "program analysis" (aka static code analysis) algorithms.
I am looking for ideas for metrics to measure how well my algorithms "understand the code".
Some ideas i have so far :
...
- 21
2
votes
0
answers
53
views
What is the difference between ADTs and ASDLs?
ASDL stands for Abstract Syntax Description Language (ASDL), whereby ADT stands for Algebraic data type.
By looking at Python.asdl it appears to me to be the same thingy, just with different names, ...
- 133
1
vote
1
answer
96
views
Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?
If not (because I assume not) is there some kind of reference or book that provides some theoretical foundation to these concepts? I've been learning about data structures and abstract data types for ...
- 135
2
votes
0
answers
52
views
Abstract Data Type
I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
- 131
1
vote
1
answer
40
views
Abstract Data Types and their Implementation [closed]
I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.
- 131
4
votes
1
answer
3k
views
What is the use case for multi-type-parameter generics?
In C#, one can define a class/method/function with multiple type parameters. For example,
...
- 227
2
votes
1
answer
67
views
Restrictions needed on ADT for totality
In the paper Total Functional Programming by D.A. Turner three rules are given for a programming language to remain total:
complete case analysis
covariant type recursion (type constructor should not ...
- 565
0
votes
0
answers
90
views
What data structure would be best for a code cross referencer?
I want to write a JavaScript cross referencer (in Python) that will build a cross-reference of JavaScript functions for a given input file. I am trying to think of what Abstract Data Type would work ...
- 101
1
vote
1
answer
2k
views
Is a BST considered a data structure or abstract data type
and why?
It seem abstract in that it is and idea created and implemented with nodes arranged a certain way.
But it did not show up in the text here:
https://en.wikipedia.org/wiki/...
1
vote
0
answers
31
views
Program Transformation to Disintermediate Isomorphic Representation Transforms
Given two representations of the same abstract data type, any optimal program that incorporates one representation has a corresponding optimal program that incorporates the other.
What is the field ...
- 386
23
votes
8
answers
3k
views
Does every data type just boil down to nodes with pointers?
An array or vector is just a sequence of values. They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node.
Stacks and queues are two abstract ...
- 341
2
votes
0
answers
79
views
Functional Core Language representation of tuples
I am writing a compiler for a simple subset of standard ML (just for fun) and I am stuck on how to represent the core language (I should mention that I write it in Haskell probably).
Basically what I ...
- 163
0
votes
0
answers
634
views
Are floats abstract data types?
Source:https://en.wikipedia.org/wiki/Abstract_data_type
Can we say that float data types (or all primitive data types or only integer) are abstract data types?
4
votes
1
answer
290
views
Are numbers types and what is "Number"?
I was pondering about what are the numbers. It seems like a number is data type. I mean, like Maybe in Haskell. Because, for instance, one on its own means nothing for me. However, one apple tells me ...
- 143
2
votes
1
answer
213
views
Is there an implementation of higher kinded types in typed lambda calculus?
I can see that we can do higher kinded types ( * -> *) -> * in Scala and Haskell and other languages. I'm looking for a simpler vanilla implementation of just ...
- 1,199
13
votes
3
answers
8k
views
What is the difference between Abstract Data Types and objects?
An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying
Objects behave like a characteristic function over the values of a type, rather than as an algebra. ...
- 321
3
votes
2
answers
331
views
Second order function formalization
I need to work on a optimizer for a language whose operator are second order functions.
They are the well known ones filter, map, reduce, fold, foreach etc. etc.
I need to formalize as much as ...
- 203
2
votes
2
answers
202
views
Understanding constraint formula concept in Java
JLS defined a concept called "constraint formula". There is a formal definition:
Constraint formulas are assertions of compatibility or subtyping that
may involve inference variables. The ...
- 209
3
votes
1
answer
4k
views
Are dictionaries and associative arrays the same thing?
With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?
- 167
0
votes
1
answer
55
views
Are Algebraic types just the combination of case classes and pattern matching?
On this page describing the precursor to the Scala language - the pizza language - they refer to it having both case classes and pattern matching - and then imply that these taken together provide ...
- 1,199
0
votes
1
answer
81
views
Looking for cheat sheet to J.C. Reynolds symbols
Most specifically, his use of small epsilon introduced at the end of section 1 of "Types, Abstraction and Parametric Polymorphism" is throwing me, but in general I would like references to symbols in ...
- 103
3
votes
3
answers
295
views
"OOD allows ADTs to be created and used."
I just had a CS mid-term and one of the questions was:
OOD allows ADTs to be created and used.
True
False
I answered false, but my answer was marked as incorrect. I suspect what the ...
- 33
6
votes
2
answers
14k
views
Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?
In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of ...
- 2,957
19
votes
2
answers
17k
views
What is the difference between abstract and concrete data structures?
I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that
For dictionaries with very small numbers of bindings, it may make
...
- 4,845
15
votes
3
answers
4k
views
An efficient data structure supporting Insert, Delete, and MostFrequent
Assume that we have a set $D$ and each member of $D$ is a data and key pair. We want a data structure that would support the following operations:
Insert $(d,k)$ into $D$,
Delete member $e$, (no need ...
- 22.2k