[Haskell-cafe] wanted: Function to break circular data dependencies

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Sat May 24 20:54:25 UTC 2014

Job Vranish wrote:

> Is a function like the following possible?:
> avoidCircularDataDependency :: a -> a -> a
> avoidCircularDataDependency a b = ?

For one, it breaks purity. If we have

  let x = avoidCircularDataDependency y True
      y = avoidCircularDataDependency x False

then whether x and y are True or False depends on which of them is
evaluated first. Note that x and y might be evaluated in parallel
by different threads.

Secondly, an implementation of avoidCircularDataDependencies in a
threaded runtime system requires cycle detection on the heap, because
running into a black hole does not reliably indicate a data dependency
cycle. GHC currently only does this when things have already gone wrong;
cycles are detected during garbage collection and the threads involved
receive NonTermination exceptions as a result. To make
avoidCircularDataDependencies useful, you'd need a more efficient way of
detecting cycles, which looks like a hard problem to me.

> I've often found myself wanting a function like this. It would make certain
> kinds of knot-tying/cycle detection _much_ easier.

Actually I'd be interested in seeing an example for this.



More information about the Haskell-Cafe mailing list