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.
14 questions
7
votes
0
answers
299
views
Are there languages having multiple level fine control over deep and shallow copy?
A reference or level-0 copy is the same object as the original, only accessed differently.
A level-1 shallow copy is a new object, with every member a reference to the member under the same name in ...
- 2,840
20
votes
6
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, ...
- 406
6
votes
2
answers
356
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 ...
- 163
2
votes
1
answer
255
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.
...
- 921
9
votes
0
answers
262
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 ...
- 20.8k
15
votes
3
answers
894
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 ...
- 2,597
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 ...
- 9,143
8
votes
2
answers
1k
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 ...
- 1,668
-2
votes
1
answer
203
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 ...
- 2,874
8
votes
9
answers
1k
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:
...
- 9,143
8
votes
7
answers
1k
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 ...
- 9,143
1
vote
2
answers
187
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 ...
- 1,835
7
votes
1
answer
101
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 ...
- 2,649
26
votes
5
answers
875
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 ...
- 4,572