Questions tagged [abstract-data-types]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
14 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
1answer
28 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
0answers
22 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 : ...
2
votes
0answers
34 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, ...
1
vote
1answer
63 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 ...
2
votes
0answers
41 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
1answer
29 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.
4
votes
1answer
733 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, ...
2
votes
1answer
47 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 ...
0
votes
0answers
39 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 ...
0
votes
1answer
639 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
0answers
27 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 ...
20
votes
8answers
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 ...
2
votes
0answers
56 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 ...
0
votes
0answers
337 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
1answer
273 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 ...
2
votes
1answer
129 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 ...
11
votes
3answers
4k 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. ...
2
votes
2answers
289 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 ...
2
votes
2answers
156 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 ...
2
votes
1answer
1k 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?
0
votes
1answer
51 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 ...
0
votes
1answer
76 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 ...
3
votes
3answers
240 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 ...
6
votes
2answers
11k 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 ...
16
votes
2answers
11k 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 ...
14
votes
3answers
3k 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 ...