Questions tagged [abstract-data-types]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
3 answers
37 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 ...
user avatar
  • 101
2 votes
0 answers
50 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 ...
user avatar
  • 121
1 vote
1 answer
38 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 ...
user avatar
0 votes
0 answers
34 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 ...
user avatar
0 votes
0 answers
95 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 ...
user avatar
-1 votes
1 answer
46 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): ...
user avatar
  • 113
1 vote
0 answers
53 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 ...
user avatar
2 votes
1 answer
71 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 ...
user avatar
1 vote
1 answer
32 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 ...
user avatar
1 vote
0 answers
108 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....
user avatar
0 votes
0 answers
461 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) ...
user avatar
0 votes
3 answers
275 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. ...
user avatar
0 votes
0 answers
47 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 ...
user avatar
0 votes
0 answers
155 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 ...
user avatar
2 votes
0 answers
16 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 ...
user avatar
  • 51
2 votes
0 answers
74 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 ...
user avatar
  • 29.2k
1 vote
1 answer
22 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 ...
user avatar
1 vote
1 answer
35 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)?
user avatar
2 votes
0 answers
25 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 : ...
user avatar
  • 21
2 votes
0 answers
44 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, ...
user avatar
  • 133
1 vote
1 answer
88 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 ...
user avatar
2 votes
0 answers
49 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 ...
user avatar
1 vote
1 answer
36 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.
user avatar
4 votes
1 answer
2k 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, ...
user avatar
2 votes
1 answer
60 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 ...
user avatar
  • 545
0 votes
0 answers
79 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 ...
user avatar
  • 101
0 votes
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/...
user avatar
1 vote
0 answers
30 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 ...
user avatar
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 ...
user avatar
2 votes
0 answers
75 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 ...
user avatar
  • 163
0 votes
0 answers
604 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?
user avatar
4 votes
1 answer
285 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 ...
user avatar
2 votes
1 answer
191 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 ...
user avatar
  • 1,189
12 votes
3 answers
7k 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. ...
user avatar
  • 301
3 votes
2 answers
315 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 ...
user avatar
  • 203
2 votes
2 answers
192 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 ...
user avatar
3 votes
1 answer
3k 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?
user avatar
  • 167
0 votes
1 answer
53 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 ...
user avatar
  • 1,189
0 votes
1 answer
80 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 ...
user avatar
  • 103
3 votes
3 answers
278 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 ...
user avatar
  • 33
6 votes
2 answers
13k 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 ...
user avatar
  • 2,837
19 votes
2 answers
16k 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 ...
user avatar
  • 1
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 ...
user avatar
  • 21.7k