The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

17

Some use cases for multiple type arguments include maps/dictionaries Map<K,V>, where you have one key parameter and one value parameter product types Pair<A,B> sum types, AKA variants Variant<A,B>, which represent a value which might be either of type A or of type B Function-like types Func<A,B> representing a function from A to B "...

17

The abstract data type (ADT) is essentially an API, and a concrete data structure provides an implementation of that API. For a given ADT, there are often several different choices of concrete data structures which support the query and update operations described by the ADT. Every concrete data structure for a given ADT must support all the operations ...

15

Well, that is basically what all data structures boil down to. Data with connections. The nodes are all artificial - they don't actually exist physically. This is where the binary part comes in. You should create a few data structures in C++ and check out where your objects land in memory. It can be very interesting to learn about how the data is laid out ...

13

It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node. Oh, dear no. You are hurting me. Like I tried to explain elsewhere ("What's the difference between a binary search tree and a binary heap?") even for a fixed data structure there are several levels to understand it. Like the priority queue ...

11

In a single linked list, every element has a pointer to the next element. If you have an additional pointer to the tail element, it takes you a constant number og operations to add to the list at the tail: get the tail pointer, add an element after the tail, put this new element as new tail. Removing from the head also takes a constant number of ...

10

Here's a counter-example: in λ-calculus, every data type boils down to functions. λ-calculus doesn't have nodes or pointers, the only thing it has are functions, therefore everything must be implemented using functions. This is an example of encoding booleans as functions, written in ECMAScript: const T = (thn, _ ) => thn, F = (_ , els) =>...

10

Let's make an analogy with mathematics. Consider the following sentence: "$f:\mathbb{R} \rightarrow \mathbb{R}$ is a continuous function". Functions are really defined in terms of relations, which are defined in terms of sets. The set of real numbers is the unique complete totally ordered field: all of these concepts have definitions in simpler terms. In ...

8

Google brought up a similar question with an answer that I think is very good. I've quoted it below. There's another distinction lurking here that is explained in the Cook essay I linked. Objects are not the only way to implement abstraction. Not everything is an object. Objects implement something which some people call procedural data ...

8

So, you have to be very careful to distinguish values, and the types of those values. We say $v : T$ when $v$ is a value with type $T$. The type Number When people say "Number" is a type, usually they're referring to the type of natural numbers. But each number isn't a type, it's a value, and $Number$ is their type. So we can say $1 : Number$, $2 : Number$...

8

Abstract data type describes what operations are available and what laws they obey. E.g. a dictionary allows you to store a value under a given key and to retrieve a value for a key, and promises that if you first store a value and then retrieve it with the same key, you will get the value you stored back. A stack has push and pop operations. Concrete data ...

7

In the comparison-based model of computation, you may implement the priority queue using a Fibonacci heap instead of an ordinary heap. This will give you the following bounds: $\mathcal{O}(1)$ amortized time for insert and $\mathcal{O}(\log n)$ amortized time for deletion operations. If you depart from the comparison-based model and adopt the RAM model ...

7

First, if this is exactly the sentence on the exam and not your translation, it's ambiguous. It could mean that OOD is one possible way to create and use ADT, or that creating and using ADTs requires OOD. Furthermore, ADT can mean two things: abstract data type or algebraic data type. The two concepts are completely different but are often confused. An ...

5

As far as I can tell, associative array is a newer term, maybe emerging from popular use in dynamic programming languages. In algorithms as an academic field, it seems to denote a generalisation of the dictionary but one usually works with dictionaries (probably because most resource characteristics carry over so one does not need to complicate notation). ...

4

I good starting point is Benjamin Pierce's Types and programming languages (popularly referred to as "TAPL").

4

Removing from the head and inserting at the tail are both constant time operations with a singly linked list, assuming head and tail pointers. Inserting at the tail is also constant time. But removing from the tail means moving the tail pointer toward the head, and since you don't have a back pointer you can't do that without traversing the whole list to ...

4

Many (most?) data structures are built of nodes and pointers. Arrays are another critical element of some data structures. Ultimately, every data structure is just a bunch of words in memory, or just a bunch of bits. It's how they are structured and how we interpret and use them that matters.

3

I doubt you find mainstream languages with HKTs simpler than Scala and Haskell. And even those don't implement HKTs fully. Tim Sheard's Ωmega and some interactive proof assistants have HKTs too. Chapters 29 and 30 of Types and Programming Languages show exactly how HKTs are added to a typing-system and how to do type-checking with HKTs. Why not ...

3

If you look at the ADT proponents, they consider an ADT to be what OOP would call a class (internal, private state; a limited set of operations allowed), but no relation between classes (no inheritance, basically) is considered. The point being instead that the same behaviour can be obtained with different implementations. E.g. a set can be implemented as a ...

3

They are called primitive data types. (This is a pretty basic find in Wikipedia's article on data types.)

2

You aren't going to find a list of all notations ever used. Apart from a few standard notations, each paper will define the notation that it uses. This paper is from the dark ages of typewriter typesetting, so the typographic quality is subpar. The character ε stands for $\in$, which is the standard mathematical notation for set membership.

2

I always understood it this way: An ADT is an interface: it is just a collection of methods, their type-signatures, possibly with pre-and-post conditions. A class can implement one or more ADTs, by giving actual implementations for the methods specified in the ADT. An object is an instance of a class, with its own copy of any non-static variables. It's ...

2

You may want to have a look at the Coq proof assistant. Its type system allows to express types as in other functional languages (e.g. filter is a function from [A] to [A]) and much more. You can easily add arbitrary properties. Here is the definition of filter, taken from the list module of the standard library: Fixpoint filter (l:list A) : list A := ...

2

You may not be able to completely specify formally in a tractable way the semantics of your functions, depending on what they are. But doing some of the work, even incompletely may help you significantly with optimizing your programs, since it may be enough to establish whatever properties are needed for optimization. The first thing you want to do is to ...

2

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. An array or a vector can be implemented with a linked list, but almost never should be. That's because accessing the $n$-th element in a linked list requires traversing a chain of $n$ pointers, ...

2

First, not all of the constraint formulas work with types, some of them work with expressions, or other objects. For example, what would be the set for the formula ‹1+1 → Integer›? Second, a formula might contain zero, one (at either position) or two inference variables (denoted by Greek letters). What would be the set for ‹String → Object›, ‹α → Object›, ‹...

2

Implementation of data structures always boils down to nodes and pointers, yes. But why stop there? Implementation of nodes and pointers boils down to bits. Implementation of bits boils down to electrical signals, magnetic storage, perhaps fiberoptic cables, etc. (In a word, physics.) This is the reductio ad absurdum of the statement, "All data ...

2

The constraint covariant type recursion (type constructor should not appear in negative position in a constructor argument) excludes this data Bad r = Bad (r -> r) ^ ^--- positive position ^-------- negative position Indeed, all the occurrences of r must appear in positive position. Should all type ...

1

I would say Algorithms by Robert Sedgewick and Kevin Wayne is a classic book which explains quite well the basics of these concepts. However you could also find a lot of resources on the web for free.

1

A binary search tree is a data structure. The interface it supports (the list of operations you can perform on it and their semantics) is an abstract data type. See https://en.wikipedia.org/wiki/Abstract_data_type for explanation of the difference between an ADT and a data structure.

1

If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers? Because that's not what "data" means. You are conflating abstract ideas with implementations. "Data" is a highly abstract idea: It's just another name for "information." A bunch of linked nodes with pointers (a.k.a., a "linked data structure") is a much ...

Only top voted, non community-wiki answers of a minimum length are eligible