A recursive datastructure is a datastructure (e.g. a struct or class) that contains one or several references to instances of the same datastructure as a member.
Questions tagged [recursive-datastructures]
524 questions
427
votes
19 answers
What do I use for a max-heap implementation in Python?
Python includes the heapq module for min-heaps, but I need a max-heap. What should I use for a max-heap implementation in Python?
Douglas Mayle
- 21,063
- 9
- 42
- 57
53
votes
6 answers
Mastering Recursive Programming
I am having trouble in thinking/solving the problem in terms of recursion. I really appreciate the concept and I can understand them like creating base case, exit case & the recursive calls etc. I can solve simple problems like writing factorial or…
Hunter
- 2,370
- 2
- 20
- 24
48
votes
4 answers
What does Python mean by printing "[...]" for an object reference?
I'm printing a value of a what I thought was a list, but the output that I get is:
[...]
What does this represent? How do I test for it? I've tried:
myVar.__repr__() != '[...]'
and
myVar.__repr_() != Ellipsis
but no dice...
Here's a cutdown of…
Dycey
- 4,767
- 5
- 47
- 86
31
votes
1 answer
What is the difference between Fix, Mu and Nu in Ed Kmett's recursion scheme package
In Ed Kmett's recursion-scheme package, there are three declarations:
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
data Nu f where
Nu :: (a -> f a) -> a -> Nu f
What is the difference between those three data…
hgiesel
- 5,430
- 2
- 29
- 56
26
votes
8 answers
populate treeview from a list of path
I'm trying to populate a treeview from a list of folder path, for…
Eric
23
votes
1 answer
Create recursive dataclass with self-referential type hints
I want to write a dataclass definition in Python, but can't refer to that same class inside the declaration.
Mainly what I want to achieve is the typing of this nested structure, as illustrated below:
@dataclass
class Category:
title: str
…
RomanGodMode
- 325
- 3
- 11
17
votes
9 answers
Confusing [...] List in Python: What is it?
So I was writing up a simple binary tree in Python and came across [...]
I don't believe this to be related to the Ellipsis object, more it seems to have something to do with an infinity loop (due to Python's shallow copy?). The source of this…
Demur Rumed
- 351
- 3
- 9
16
votes
3 answers
scalacheck Arbitrary implicits and recursive generators
I'm seeing what seems to be a very obvious bug with scalacheck, such that if it's really there I can't see how people use it for recursive data structures.
This program fails with a StackOverflowError before scalacheck takes over, while constructing…
Daniel Martin
- 23,083
- 6
- 50
- 70
16
votes
2 answers
Why inductive datatypes forbid types like `data Bad a = C (Bad a -> a)` where the type recursion occurs in front of ->?
Agda manual on Inductive Data Types and Pattern Matching states:
To ensure normalisation, inductive occurrences must appear in strictly positive positions. For instance, the following datatype is not allowed:
data Bad : Set where
bad : (Bad →…
Petr
- 62,528
- 13
- 153
- 317
16
votes
2 answers
Initializing circular data in C. Is this valid C code according to any standard?
I wanted to see if I could initialize a global variable to point to itself:
#include
struct foo { struct foo *a, *b; } x = { &x, &x };
int main()
{
printf("&x = %p, x.a = %p, x.b = %p\n", &x, x.a, x.b);
return 0;
}
This code…
Matt
- 21,026
- 18
- 63
- 115
15
votes
1 answer
How can I dynamically allocate cyclic data?
For the sake of example let's define a toy automaton type:
data Automaton =
Auto
{ success ::
Automaton
, failure ::
Automaton
}
This structure is designed to by cyclic, we can imagine each Automaton as a state with…
Wheat Wizard
- 3,982
- 14
- 34
14
votes
1 answer
Understanding recursion without base case in Julia
This snippet is from the implementation of Rational Numbers in Julia:
# Rational.jl
# ...
Rational{T<:Integer}(n::T, d::T) = Rational{T}(n,d)
Rational(n::Integer, d::Integer) = Rational(promote(n,d)...)
Rational(n::Integer) =…
dopatraman
- 13,416
- 29
- 90
- 154
14
votes
4 answers
How CSS and DOM is implemented in the browser?
This is a pretty academic question. I'm wondering how the browser is implemented as in what data structure or algorithm is used to map a CSS selector to a particular DOM element. Is it accomplished through a hash table? How does DOM child node…
Jlam
- 1,932
- 1
- 21
- 26
13
votes
2 answers
Python hangs indefinitely trying to delete deeply recursive object
I wrote a ternary search tree in Python and I've noticed that when the tree gets very deep, attempting to delete it causes Python to hang indefinitely. Here is a stripped version of the code that produces this behaviour:
import random
import…
Christian Adam
- 196
- 9
10
votes
1 answer
Writing generic instances for Fix/Mu in F-algebras
After reading Milewski's F-algebra article, I tried to implement it and use for a real-world problem. However, I can't seem to figure out how to write instances for Fix,
newtype Fix f = Fx { unFix :: f (Fix f) }
cata :: Functor f => (f a -> a) ->…
Rufflewind
- 8,545
- 2
- 35
- 55