# Questions tagged [abstract-data-types]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
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 ...
• 101
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 ...
• 121
1 vote
38 views

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 ...
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 ...
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 ...
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): ...
• 113
1 vote
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 ...
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 ...
1 vote
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 ...
1 vote
108 views

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....
• 276
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) ...
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. ...
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 ...
• 123
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 ...
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 ...
• 51
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 ...
• 29.2k
1 vote
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 ...
1 vote
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)?
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 : ...
• 21
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, ...
• 133
1 vote
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 ...
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 ...
1 vote
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.
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, ...
• 227
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 ...
• 545
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 ...
• 101
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
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 ...
• 378
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
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 ...
• 163
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?
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 ...
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 ...
• 1,189
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. ...
• 301
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 ...
• 203
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 ...
• 209
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?
• 167
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 ...
• 1,189
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 ...
• 103
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 ...
• 33
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 ...
• 2,837
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 ...
• 1
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 ...