Skip to main content

Questions tagged [data-structures]

For questions about the implementation or design of data structures as specifically relevant to programming language design or implementation. Generic data structure questions are off-topic.

Filter by
Sorted by
Tagged with
19 votes
5 answers
4k views

Why is array access not an infix operator?

The typical syntax for accessing an array (or list, map and similar data structures) at a specific index is a[i]. I believe C first introduced it as syntax sugar, ...
linux_user36's user avatar
6 votes
2 answers
322 views

Representing multiple alternative ASTs in one structure

Sometime during the past year I read (possibly on SO/SE) about a topic that sounded interesting. Now I would like to pick it up but I can't find it again. My memory is somewhat vague, I'm afraid. I ...
Mankka's user avatar
  • 163
2 votes
1 answer
238 views

Is it practical to use binary trees as a sequential container?

Contiguous arrays do not mix with lazy evaluation. That's why Haskell doesn't have contiguous arrays as a primitive type, and why even GHC has a poor API for them. As such, I sought for a workaround. ...
Dannyu NDos's user avatar
9 votes
0 answers
236 views

How can a compiler optimise persistent data structures to use mutable data structures "under the hood"?

Consider for a motivating example a copy-on-write array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a reference counter can be used to avoid the ...
kaya3's user avatar
  • 20k
15 votes
3 answers
832 views

Towards a better default listlike datastructure for functional languages

In most functional languages I know of, linked lists are the default datastructure of choice for many operations. The benefits are clear - they're clearly encoded with ADTs, and can be utilised easily ...
blueberry's user avatar
  • 2,577
8 votes
7 answers
2k views

Distinguishing classes from structures

Some languages have a concept of classes separately than structs. In C++ the only difference is whether the members are public or private by default. This seems redundant. Why have a separate ...
CPlus's user avatar
  • 8,503
6 votes
2 answers
929 views

What are the downsides of having no syntactic sugar for data collections?

For example, Python has lists, sets and dictionaries as language-level primitives that can be constructed using syntactic sugar [1,2,3], {'a': 1, 'b': 2} while Java ...
kouta-kun's user avatar
  • 1,459
-2 votes
1 answer
189 views

Why are type theorhetic data structures rarer (than sets) if they are fundamental? [closed]

Set theorhetical structures and operations are quite fundamental and typically are either part of a languages standard library or built into it. Given that types are fundamental to programming why do ...
Bruce Adams's user avatar
  • 2,853
8 votes
9 answers
852 views

Would a structure ever require padding beyond what is required to align the members?

In C a structure can have an arbitrary amount of padding. In theory this implementation conforms to the C standard: ...
CPlus's user avatar
  • 8,503
6 votes
7 answers
714 views

What are the implications of a 'packed' keyword/feature?

I am bothered by the fact that, in C, struct types can be arbitrarily large. We have no control over their memory layout except for the fact that the first member ...
CPlus's user avatar
  • 8,503
1 vote
2 answers
176 views

What are the pros and cons of having a unique type for generators?

For languages that allow generators (iterables where elements are determined by a function), what are the pros and cons of having a unique type for generators? For example, languages like python have ...
lyxal's user avatar
  • 1,825
7 votes
1 answer
97 views

Should functions like filter and map be members of a class or top-level functions?

In python, the filter and map functions (among others) are top-level (i.e. global) functions which take an iterable as an ...
Ginger's user avatar
  • 2,629
25 votes
5 answers
776 views

Can "no cyclic data structures" be enforced at compile time?

When using reference counting for garbage collection, memory leaks can occur when cyclic structures are created (an object which contains a pointer to itself, or a pointer to an object with a pointer ...
Rydwolf Programs's user avatar