# 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 "...

14

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 ...

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$...

6

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

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.

4

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 ...

4

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

3

The initial assumption about such types having at most countably many elements is false. We can use inductive types to define a non-countable type, namely the countably branching trees: (* Countably branching trees. *) Inductive Tree : Type := | Leaf : Tree | Node : (nat -> Tree) -> Tree. Lemma nocycle (t : Tree) : forall (f : nat -> Tree), t = ...

3

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

3

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 ...

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 ...

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

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

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 ...

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

Sounds subjective to me. Data abstraction is not a black-and-white binary property; it is a matter of shades of grey. Any abstraction hides some information and reveals others. Another way to put it is that these two classes expose a different amount of functionality and make a different set of promises. So, what do you want the client to be aware of, and ...

1

I'm not sure what you mean by this: I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array. There are many examples of dynamic arrays in mainstream programming languages: Python: list C++: std::vector Java: ArrayList Rust: Vec OCaml (Batteries ...

1

The consensus from the available information I've found points to SNOBOL4, released in 1967, as the earliest implementation of "associative arrays". This post on the Software Engineering community is very similar to your question and has some great info. Chicago University - Intro to TCL course: Associative Arrays Associative arrays were first used in ...

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 ...

1

Constraint formulas are assertions: they are either true or false (given a context where they are valid). For example, ‹byte → int› is true (in any valid context) because it is an instance of a widening primitive conversion which is a loose invocation context for the destination type. C1 is a subclass of C2, then ‹C1 <: C2› is true. On the other hand, ‹...

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