Stack Overflow
Stack Overflow

Questions tagged [graph-reduction]

8 questions
13
votes
1 answer

How to reason about space complexity in Haskell

I'm trying to find a formal way to think about the space complexity in haskell. I have found this article about the Graph Reduction (GR) technique which seems to me as a way to go. But I'm having problems applying it in some cases. Consider the…
Peter Jankuliak
  • 3,464
  • 1
  • 29
  • 40
10
votes
2 answers

Haskell implemented without a stack?

from How does a stackless language work? Haskell (as commonly implemented) does not have a call stack; evaluation is based on graph reduction. Really? That's interesting, because while I've never experienced it myself, I've read that if you don't…
TheIronKnuckle
  • 7,224
  • 4
  • 33
  • 56
6
votes
1 answer

Reduce cyclic graph to tree (dependency graph-->tree)

I'm analyzing some code for its dependencies. Let's say there are some interwoven dependencies, like so: F A /| | / | | / | V < V B<--->C--->E \ / | > <…
corsiKa
  • 81,495
  • 25
  • 153
  • 204
4
votes
0 answers

Efficient Transitive Reduction of Adjacency List DAG

I have a large directed acyclic graph, and I'd like to compute the transitive reduction of that graph. I'm currently computing the transitive reduction using a naive depth-first search, but that algorithm is too slow for my use case. However, the…
IanPudney
  • 5,941
  • 1
  • 24
  • 39
3
votes
1 answer

Graph reduction / Tricky space leak example

I'm wondering about an example for a space leak I read about on this page (sadly it was not explained there): https://en.wikibooks.org/wiki/Haskell/Graph_reduction Tricky space leak example: (\xs -> head xs + last xs) [1..n] (\xs -> last xs + head…
road42
  • 77
  • 5
3
votes
2 answers

Semi-explicit parallelism in Haskell

I am reading semi-explicit parallelism in Haskell, and get some confusion. par :: a -> b -> b People say that this approach allows us to make automatically parallelization by evaluating every sub-expression of a Haskell program in parallel.…
chipbk10
  • 5,783
  • 12
  • 49
  • 85
2
votes
1 answer

Algorithm to simplify/reduce graph

Is there an algorithm that shortens paths (and removes nodes) based on edge cost? I can't put it into words too well so I hope these images sum it up well enough:
AlexT
  • 589
  • 2
  • 9
  • 23
1
vote
1 answer

Tree or Graph contraction

I am currently using Python to solve a "tree summarization" problem. My tree consists of nodes which have weights and children. An example Node( name: "Parent", weight: 20, children: {[ Node(name: "Child 1" weight: 10, children: {[]}, …
Arnob
  • 467
  • 1
  • 4
  • 13